Ich versuche gerade aus 24 Elementen 24 Kombinationen zu bilden, unter der Einschränkung, dass sich in keiner Kombination 2 mal die gleichen Elemente, auf der gleichen Seite, berühren dürfen. Rein rechnerisch müsste es funktionieren so auf genau 24 Varianten zu kommen.
Hier ein Beispiel für alle Kombinationen einer Lösung mit 4 Elementen:
1243
2314
3421
4132
Das war manuell noch halbwegs machbar - Aber wie stell ich das mit 24 Elementen an? Gibt’s da nen Algorithmus?
unter der Einschränkung, dass sich in keiner
Kombination 2 mal die gleichen Elemente, auf der gleichen
Seite, berühren dürfen.
Kannst du das noch mal umformulieren? Keine Ahnung, was du meinst.
Gruß
Kubi
Erklärungsversuch
Beispiel: Ich habe 4 verschiedene Elemente {1,2,3,4}. Diese sollen kombiniert werden. Bedingung: Es müssen in jeder Kombination unterschiedliche Elemente aufeinanderfolgen.
Kombination
1243
in dieser dürfen weder 12, 24 oder 43 vorkommen, da diese bereits in der 1. Kombination vorkommen.
2314
Auch in dieser dürfen 12, 24 oder 43 nicht vorkommen. Zusätzlich dürfen (wegen Kombination 2) auch nicht 23, 31, und 14 vorkommen.
3421
Hier dürfen zusätzlich nicht mehr verwendet werden: 34, 42, 21
Es bleiben: 13, 32 und 41
4132
Ob es wirklich genau 24 solche Kombinationen gibt hab ich nicht überprüft, aber unter der Annahme dass es 24 solche Kombination gibt habe ich einen Ansatz:
Erstelle einen gerichteten Graphen mit 24 Knoten in dem zwischen irgend 2 Knoten a und b genau eine Kante von a nach b und genau eine Kante von b nach a geht.
for i=1:24
Finde einen Weg durch den Graphen der jeden Knoten genau einmal durchläuft und entferne dabei alle benutzten Kanten. Die Kombination ist die Reihenfolge in der die Knoten durchlaufen werden.
end
Fraglich hierbei ist, ob man jeden dieser Wege (ich glaube man nennt sie eulersch) nehmen darf, oder ob es Einschränkungen gibt (man muss ja sicherstellen dass es nach dem Entfernen der Kanten noch einen solchen Weg gibt). Zum Finden solcher Wege gibt es bekannte Algorithmen (Hierholzer glaube ich). Probiere es doch einfach mal aus!
Fraglich hierbei ist, ob man jeden dieser Wege (ich glaube man
nennt sie eulersch) nehmen darf, oder ob es Einschränkungen
gibt (man muss ja sicherstellen dass es nach dem Entfernen der
Kanten noch einen solchen Weg gibt).
Hm… interessante Idee. Ich denke es muss definitiv irgendwelche Einschränkungen geben. Wenn man z.B. immer mit dem gleichen Knoten beginnt, so ist mit den letzten 5 Kanten kein Pfad mehr möglich.
Fatale Verwechslung:
Wenn jeder Knoten abgelaufen werden soll ist das ein Hamiltonpfad und so einen zu finden ist verdammt eckelhaft.
Ein Ergebnis lässt sich allerdings aus dem Verfahren ableiten: In jedem Schritt ändern sich die Ein- und Ausgangsgrade der Knoten folgendermaßen
Anfangspunkt: --Ausgangsgrad (AG)
Endpunkt: --Eingangsgrad (EG)
Andere: --EG und --AG
Am Anfang gilt für alle Punkte EG=AG=23
Damit 24 Schritte möglich sind muss also jeder Punkt genau einmal Anfangspunkt und genau einmal Endpunkt eines Hamiltonpfades gewesen sein.
–> Jedes Element ist ein mal erstes und einmal letztes Element einer Permutation.
Algorithmus für gerade n
Schritt 1: Schreibe die Zahlen von 1 bis n untereinander
1
2
3
4
5
...
n-4
n-3
n-2
n-1
n
Schritt 2: Erweitere zu einem Dreieck nach folgendem Muster:
1
2 +2
3 -2 +4
4 +2 -4 +6
5 -2 +4 -6 +8
... ... ... ... ...
n-4 +2 -4 +6 -8
n-3 -2 +4 -6
n-2 +2 -4
n-1 -2
n
(Btw: die untere Hälfte entsteht auch aus der oberen Hälfte durch Spiegelung und Bilden der Differenz zu n+1)
Schritt 3:Punktspiegelung des Dreiecks an der rechten Ecke
## ## ##
#### #### ####
###### ###### ######
########\_|\_ ergibt ################
######## | ################
###### ###### ######
#### #### ####
## ## ##
Schritt 4: Spiegeln an der Hauptdiagonalen
Fertig. Beweis der Korrektheit als Übung.
Bsp. für n=8
Schritt 1
1
2
3
4
5
6
7
8
Schritt 2
1
2 4
3 1 5
4 6 2 8
5 3 7 1
6 8 4
7 5
8
Schritt 3
1 8
2 4 5 7
3 1 5 4 8 6
4 6 2 8 1 7 3 5
5 3 7 1 8 2 6 4
6 8 4 5 1 3
7 5 4 2
8 1
Schritt 4
1 2 3 4 5 6 7 8
2 4 1 6 3 8 5 7
3 1 5 2 7 4 8 6
4 6 2 8 1 7 3 5
5 3 7 1 8 2 6 4
6 8 4 7 2 5 1 3
7 5 8 3 6 1 4 2
8 7 6 5 4 3 2 1
Fertig.
Das sieht sehr gut aus. Vielen Dank!