Kombinationsindizes

Kombinationsindizes bezeichnen die Indizes eines Elementesets, die angeben, welche Elemente in einer k-elementigen Kombination aus einem n-elementigen Vorrat ausgewählt wurden. Häufige Darstellung ist eine streng steigende Folge i1 < i2 < ... < ik mit 1 <= i_j <= n. Die Anzahl solcher Indizes entspricht dem Binomialkoeffizienten C(n, k).

Darstellungen und Ordnungen unterscheiden sich je nach Anwendung. Üblich sind lexikografische oder kolexikografische Reihenfolgen. In der Informatik werden oft Null-basierte Indizes verwendet (0 <= i1 < i2 < ... < ik <= n-1). Ein einfaches Beispiel: Aus dem Set {1,2,3,4,5} mit n=5 und k=3 erhält man die Indizesfolge (2,4,5), die die Elemente 2, 4 und 5 bezeichnet.

Eine zentrale Eigenschaft ist die Bijektion zwischen Indizesfolgen und Ganzzahlen mittels der Rang- und Unrang-Funktionen, oft mithilfe des kombinatorischen Zahlensystems. Der Rang ordnet jeder Indizesfolge eine eindeutige Zahl r im Bereich 0 bis C(n,k)-1 zu. Für die 1-basierten Indizes gilt zum Beispiel rank(i1,...,ik) = C(i1-1,1) + C(i2-1,2) + ... + C(ik-1,k). Umgekehrt lässt sich aus r die Indizesfolge rekonstruiert (Unrang).

Anwendungen finden sich in Enumerationsalgorithmen, bei der Indexierung von Teilmengen, in Stichprobentechniken ohne Zurücklegen sowie in Codierungstheorie und Datenstrukturen, etwa beim Umgang mit Bitmasken, bei denen eine Kombination durch die Stellung von Einsen codiert wird.

Zusammengefasst dienen Kombinationsindizes dazu, jede k-elementige Teilmenge eines n-Elemente-Sets eindeutig zu beschreiben, zu ordnen und effizient zu enumerieren.