Kombinatorik - Generator von Kombinationen

Dieser Rechner produziert alle möglichen Kombinationen von m-Elementen aus einem Satz von Elementen mit der Größe N. Die Anzahl von möglichen Kombinationen sind wie gezeigt in Kombinatorik - Kombinationen, Anordnungen und Permutationen

Die Beschreibung des Algorithmus-Generators ist unter dem Rechner

Kombinatorik - Generator von Kombinationen



Reihe

	Wert
		

Kombinationsgröße M

berechnen

Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.

Download 

 Link  Abspeichern  Widget

Algorithmus

Kombinationen werden in lexikographischer Ordnung erstellt. Algorithmen nutzen die Indizes aus der Reihe von Elementen.
Anhand eines Beispiels wird gezeigt, wie dies funktioniert:
Nehmen wir mal an, wir haben einen Satz von 5 Elementen mit Indizes 1 2 3 4 5 (beginnend mit 1) und wir müssen alle Kombination für die Größe m=3 erstellen.

Zuerst initialisieren wir die erste Kombination der Größe M – Indizes in aufsteigender Reihenfolge.
1 2 3
Wir beginnen mit dem Überprüfen des letzten Elements (z.B. i = 3). Wenn der Wert niedriger ist als n - m + I, erhöht er sich um 1.
1 2 4
Dann überprüfen wir das letzte Element erneut, und da der Wert immer noch niedriger als n - m + i ist, wird er ums 1 erhöht.
1 2 5
Nun ist der höchst erlaubte Wert: n - m + i = 5 - 3 + 3 = 5, daher gehen wir nun zum vorigen Element über.
Wenn der Wert niedriger ist als n - m + i, wird er um 1 erhöht, und alle folgenden Elemente werden zum Wert des vorherigen Wertes plus 1 eingestellt.
1 (2+1)3 (3+1)4 = 1 3 4
Dann starten wir wieder mit dem letzten Element i = 3
1 3 5
Zurück zu i = 2
1 4 5
Nun ist es gleich n - m + i = 5 - 3 + 2 = 4, so dass wir zum ersten Element übergehen können (i = 1)
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Und dann,
2 3 5
2 4 5
3 4 5 - dies ist die letzte Kombination, da alle Werte den größtmöglichen Wert von n - m + i. erreicht hat.