Kombinatorik - Generator von Kombinationen

Kombinatorik - Generator von Kombinationen aus M von N

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
C_{n}^m=\frac{n!}{m!(n-m)!}

Die Beschreibung des Algorithmus-Generators ist unter dem Rechner

PLANETCALC, Kombinatorik - Generator von Kombinationen

Kombinatorik - Generator von Kombinationen

Reihe

Wert
Elemente pro Seite:

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

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.

URL zum Clipboard kopiert
PLANETCALC, Kombinatorik - Generator von Kombinationen

Kommentare