Generiere alle Permutationen der Liste [1, 1, 2, 2, ..., n, n], wobei die Anzahl der Elemente zwischen jedem Paar gerade in Prolog ist

Ich habe vor kurzem angefangen, Prolog zu lernen, und ich habe eine Aufgabe bekommen, ein Prädikat list(N, L) zu schreiben, das Listen L erzeugt, so dass:

• L hat die Länge 2N,
• jede Zahl zwischen 1 und N kommt genau zweimal in L vor,
• zwischen jedem Paar desselben Elements gibt es eine gerade Anzahl anderer Elemente,
• die ersten Vorkommen jeder Zahl sind in aufsteigender Reihenfolge.

Der Autor gibt an, dass es N gibt! solche Listen.

Zum Beispiel sind für N = 3 alle Lösungen:

Meine aktuelle Lösung sieht folgendermaßen aus:

Es tut zwei Dinge:

• Wenn das aktuelle Maximum kleiner als N ist, fügen Sie diese Nummer zur Liste hinzu, fügen Sie sie in die Liste der Duplikate ein und aktualisieren Sie das Maximum;
• Wählen Sie einige Duplikate aus, prüfen Sie, ob eine gerade Anzahl von Elementen zwischen der Zahl und der Nummer in der Liste vorhanden ist (dh diese Zahl befindet sich an einer ungeraden Position), fügen Sie sie der Liste hinzu und entfernen Sie sie aus den Duplikaten.

Es funktioniert, aber es ist langsam und sieht nicht wirklich gut aus.

Der Autor dieser Übung zeigt, dass für N & lt; 12, seine Lösung erzeugt eine einzige Liste mit durchschnittlich ~ 11 Schlussfolgerungen (mit time/1 und Dividieren des Ergebnisses durch N!). Mit meiner Lösung wächst es auf ~ 60.

Ich habe zwei Fragen:

1. Wie kann man diesen Algorithmus verbessern?
2. Kann dieses Problem auf ein anderes bekanntes verallgemeinert werden? Ich kenne ähnliche Probleme anhand der Multiset [1, 1, 2, 2, ..., n, n] (zB Langford Paarung), konnte aber so etwas nicht finden.

Ich frage, weil das ursprüngliche Problem die Aufzählung von Schnittpunkten in einer sich selbst schneidenden geschlossenen Kurve ist. Du zeichnest eine solche Kurve, wählst einen Punkt und eine Richtung und folgst der Kurve, zählst jede Kreuzung auf, wenn du sie zum ersten Mal triffst, und wiederholst die Nummer auf der zweiten Besprechung: Beispiel (mit der Antwort [1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8] ).

Der Autor stellt fest, dass jede solche Kurve das Prädikat list erfüllt, aber nicht jede Liste einer Kurve entspricht.