Koepf's Editions – Computer Projects – Schnelle kombinatorische Algorithmen in C
English

Schnelle kombinatorische Algorithmen in C

Siegfried Koepf, 2009-2013

1. Einführung

Dies ist keine Einführung in die Funktionsweise oder Analyse kombinatorischer Algorithmen, ein Gegenstand, der von kompetenter Seite ausführlich erforscht und beschrieben wurde. Es gibt wirklich großartige Literatur zu diesem Thema und am Ende dieser Seite habe ich eine kleine Auswahl zum Teil frei erhältlicher Titel zusammengestellt. Auch die hier veröffentlichten Programme wurden durch diese Lektüre in hohem Maße beeinflusst.

Der Zweck dieser Seite ist es, einige kombinatorische Algorithmen in Form von C-Programmen zur allgemeinen Verfügung zu stellen. Diese entstanden im Verlauf der letzten Jahre im Kontext meiner kompositorischen und musiktheoretischen Arbeit und haben sich in meiner Praxis als extrem schnelle und hilfreiche Werkzeuge erwiesen.

Bei diesen Programmen geht es darum, klassische kombinatorische Figurenmengen vollständig und in einer wohldefinierten Reihenfolge zu erzeugen. Sie arbeiten alle nach dem gleichen Prinzip: Die gesuchten Figuren werden eine nach der anderen generiert und dem aufrufenden Programm zur weiteren Verarbeitung zur Verfügung gestellt. Zunächst wird eine Funktion

gen_xxx_init(...)

aufgerufen (dabei steht xxx für ein Kürzel des englischen Namens der betreffenden kombinatorischen Figurenmenge). Hier werden die Argumente auf mögliche Spezialfälle hin untersucht und ein zuvor deklariertes Array mit der ersten Figur der zu generierenden Figurenmenge initialisiert. Nach Auswertung des Rückgabewerts wird in einer Schleife die Funktion

gen_xxx_next(...)

aufgerufen und mit ihr so lange der lexikographische Nachfolger berechnet, bis die Menge vollständig aufgezählt wurde.

"Allgemein kann man den lexikographischen Nachfolger einer beliebigen kombinatorischen Figur a1...an in drei Schritten erhalten:
1) Finde das größte j, so dass aj erhöht werden kann.
2) Erhöhe aj um den kleinstmöglichen Betrag.
3) Finde die lexikographisch kleinste Möglichkeit, das neue a1...aj zu einer vollständigen Figur zu erweitern"(1).

In den Kommentaren im Quellcode wird regelmäßig auf dieses Schema Bezug genommen. In einigen Fällen wird es aber variiert, indem die gesuchte Menge in umgekehrt lexikographischer Ordnung, in kolexikographischer Ordnung oder in umgekehrt kolexikographischer Ordnung aufgezählt wird.

Eine Ausnahme bildet das Programm zur Berechnung der Permutationen mit Wiederholungen. Hier wird das Array nicht durch die Funktion gen_perm_rep_lex_init initialisiert. Dies muss vom aufrufenden Programm erledigt werden. Will man die Menge aller Permutationen vollständig berechnen, müssen die Elemente zu Beginn in aufsteigender Folge angeordnet sein. Sind diese Elemente außerdem distinkt, erzeugt dieser Algorithmus übrigens die "gewöhnlichen" Permutationen ohne Wiederholungen.

2. Code

Die Programme arbeiten iterativ, in-place und sind in ANSI-C geschrieben. Zu jedem Algorithmus gehört eine Datei mit dem entsprechenden Programmcode und ein Programm als Beispiel für dessen Gebrauch. Zusätzlich muss jeweils die Headerdatei _generate.h eingebunden werden. Weitere Informationen und gegebenenfalls passende Literaturangaben finden sich in den einzelnen C-Dateien.

2.1. Kombinationen

2.1.1. Kombinationen ohne Wiederholungen, lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
comb_norep_lex.c
comb_norep_lex_example.c

Beispiel mit
n = 5, k = 3
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

2.1.2. Kombinationen ohne Wiederholungen, umgekehrt kolexikographisch geordnet

hinzugefügt am 10.07.2013
Quellcode:
comb_norep_revcolex.c
comb_norep_revcolex_example.c

Beispiel mit
n = 5, k = 3
2 3 4
1 3 4
0 3 4
1 2 4
0 2 4
0 1 4
1 2 3
0 2 3
0 1 3
0 1 2

2.1.3. Kombinationen mit Wiederholungen, lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
comb_rep_lex.c
comb_rep_lex_example.c

Beispiel mit
n = 3, k = 3
0 0 0
0 0 1
0 0 2
0 1 1
0 1 2
0 2 2
1 1 1
1 1 2
1 2 2
2 2 2

2.1.4. Kombinationen mit Wiederholungen, umgekehrt kolexikographisch geordnet

hinzugefügt am 10.07.2013
Quellcode:
comb_rep_revcolex.c
comb_rep_revcolex_example.c

Beispiel mit
n = 3, k = 3
2 2 2
1 2 2
0 2 2
1 1 2
0 1 2
0 0 2
1 1 1
0 1 1
0 0 1
0 0 0

2.2. Partitionen

2.2.1. Partitionen, umgekehrt lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
part_revlex.c
part_revlex_example.c

Beispiel mit
n = 6
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1

2.2.2. k-Partitionen, kolexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
k_part_colex.c
k_part_colex_example.c

Beispiel mit
n = 10, k = 4
7 1 1 1
6 2 1 1
5 3 1 1
4 4 1 1
5 2 2 1
4 3 2 1
3 3 3 1
4 2 2 2
3 3 2 2

2.2.3. k-Partitionen mit Berücksichtigung der Reihenfolge, kolexikographisch geordnet

hinzugefügt am 06.02.2012
Quellcode:
k_comp_colex.c
k_comp_colex_example.c

Beispiel mit
n = 7, k = 5
3 1 1 1 1
2 2 1 1 1
1 3 1 1 1
2 1 2 1 1
1 2 2 1 1
1 1 3 1 1
2 1 1 2 1
1 2 1 2 1
1 1 2 2 1
1 1 1 3 1
2 1 1 1 2
1 2 1 1 2
1 1 2 1 2
1 1 1 2 2
1 1 1 1 3

2.3. n-Tupel

2.3.1. Variationen mit Wiederholungen, lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
vari_rep_lex.c
vari_rep_lex_example.c

Beispiel mit
m = 2, n = 3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

2.3.2. Variationen mit Wiederholungen, kolexikographisch geordnet

hinzugefügt am 10.07.2013
Quellcode:
vari_rep_colex.c
vari_rep_colex_example.c

Beispiel mit
m = 2, n = 3
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1

2.3.3. Perlenketten, lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
neck_lex.c
neck_lex_example.c

Beispiel mit
m = 2, n = 6
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 1
0 0 1 0 0 1
0 0 1 0 1 1
0 0 1 1 0 1
0 0 1 1 1 1
0 1 0 1 0 1
0 1 0 1 1 1
0 1 1 0 1 1
0 1 1 1 1 1
1 1 1 1 1 1

2.4. Permutationen

2.4.1. Permutationen mit Wiederholungen, lexikographisch geordnet

hinzugefügt am 26.04.2009
Quellcode:
perm_rep_lex.c
perm_rep_lex_example.c

Beispiel mit
n = 4, {1, 2, 2, 3}
1 2 2 3
1 2 3 2
1 3 2 2
2 1 2 3
2 1 3 2
2 2 1 3
2 2 3 1
2 3 1 2
2 3 2 1
3 1 2 2
3 2 1 2
3 2 2 1

3. Änderungsprotokoll und Bugs

Hinweise auf Fehler im Code sind hier willkommen. Änderungsprotokoll, siehe CHANGELOG.

4. Download und Lizenz

Der auf dieser Seite veröffentlichte C-Code steht unter der GNU General Public License version 3, siehe COPYING.
Download

5. Weiterführende Literatur

Arndt, Jörg: Matters Computational: ideas, algorithms, source code. 2009. URL: www.jjj.de/fxt (26.04.2009).

Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 2. Generating All Tuples and Permutations. Upper Saddle River, NJ 2005.

Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 3. Generating All Combinations and Partitions. Upper Saddle River, NJ 2005.

Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 4. History of Combinatorial Generation. Upper Saddle River, NJ 2006.

Nijenhuis Albert/Wilf, Herbert: Combinatorial Algorithms. New York 1978. URL: www.math.upenn.edu/~wilf (02.02.2009).

Ruskey, Frank: Combinatorial Generation. Working Version 2003. URL: www.1stworks.com/ref/RuskeyCombGen.pdf (02.02.2009).

(1) Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 2. Generating All Tuples and Permutations. Upper Saddle River, NJ 2005, S. 40 (Übers. d. Verf.).

Last update: 20.10.2021