Wie bekomme ich alle möglichen Permutationen einer Liste mit Common Lisp?

Ich versuche, eine Common Lisp-Funktion zu schreiben, die mir alle möglichen Permutationen einer Liste gibt, wobei jedes Element nur einmal verwendet wird. Zum Beispiel gibt die Liste '(1 2 3) die Ausgabe ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).Wie bekomme ich alle möglichen Permutationen einer Liste mit Common Lisp?

Ich habe schon etwas geschrieben, das funktioniert, aber es ist klobig, es funktioniert nicht immer und ich verstehe es nicht einmal wirklich. Ich frage nicht nach Code, sondern vielleicht nach einer Anleitung, wie ich darüber nachdenken soll. Ich weiß nicht viel über das Schreiben von Algorithmen.

Danke, Jason

Quelle

2010-01-18 Jason

Normalerweise ist es eine gute Idee, den Code, den Sie bisher geschrieben haben, zu posten. So können wir sehen, wie Sie denken ... –

Wenn dies Hausaufgaben sind, bitte markieren Sie es als solches. –

Das sind keine Hausaufgaben. Ich habe absichtlich den Code weggelassen, den ich bisher habe. Ich möchte die Antworten nicht mit meiner fehlerhaften Idee beschönigen. – Jason

-2

Ich bin mir nicht sicher, ob Ihre Frage zu Common Lisp, oder über den Algorithmus ist.

Es gibt ähnliche Probleme (und Lösungen) für andere Sprachen hier, z. B. Python. Python kann oft virtuell Zeile für Zeile in Common Lisp übersetzt werden, also wählen Sie eine und portieren Sie sie? :-)

Quelle

2010-01-18 17:02:46 Ken

Als Grundansatz „alle Permutationen“ dieses rekursiven Muster folgen:

 
    all permutations of a list L is: 
    for each element E in L: 
     that element prepended to all permutations of [ L with E removed ]

Wenn wir als gegeben annehmen, dass Sie keine doppelte Elemente in Ihrer Liste haben, gehen Sie wie folgt sollten:

 
(defun all-permutations (list) 
    (cond ((null list) nil) 
     ((null (cdr list)) (list list)) 
     (t (loop for element in list 
      append (mapcar (lambda (l) (cons element l)) 
          (all-permutations (remove element list)))))))

Quelle

2010-01-18 17:09:00 Vatine

Vielen Dank! Das ist irgendwie wie das, was ich hatte, aber mit einigen kleinen und wichtigen Unterschieden. Das einzige Problem, das ich damit sehe, ist, dass (All-Permutationen '(1 2 3)) und (All-Permutationen' (1 1 2 3)) dasselbe Ergebnis liefern, aber das sollte leicht genug sein, um geändert zu werden. (Mein ultimatives Ziel ist hier, Wörter zu verwürfeln.) – Jason

Wenn Sie nicht unterscheidbare Elemente haben, wird es ein wenig komplizierter, Sie müssen einige Vorverarbeitungen vornehmen, um zu vermeiden, dass "dieselbe" Permutation mehr als einmal erzeugt wird. Anstatt jedoch eine Liste wie oben zu verwenden, sollte die Verwendung eines Vektors von (SYMBOL. COUNT) als die Datenstruktur, die Sie weitergeben, und das Dekrementieren der Zählung (auf einer Kopie!) Anstelle des Löschens auch dafür sorgen. – Vatine

(defun Permutationen() (Etiketten ((DO-Permutationen (items) (wenn Artikel (mapcan (lambda (x) (mapcar (lambda (y) (cons xy)) (DO-Permutationen (entfernen x Elemente)))) Elemente) '(())))) (Do-Permutationen' ("Guy" "Man" "Dude")))) –

Gehen Sie durch Ihre Liste und wählen Sie jedes Element der Reihe nach aus. Dieses Element wird das erste Element Ihrer aktuellen Permutation sein.

Schließe dieses Element an alle Permutationen der verbleibenden Elemente an.

Quelle

2010-01-18 17:09:16

Hier ist die Antwort, die wiederholte Elemente ermöglicht. Der Code ist noch mehr „lispish“, da sie nicht-Schleife ist, mit dem Nachteil, dass sie weniger verständlich, als Rainer Joswig Lösung:

(defun all-permutations (lst &optional (remain lst)) 
    (cond ((null remain) nil) 
     ((null (rest lst)) (list lst)) 
     (t (append 
      (mapcar (lambda (l) (cons (first lst) l)) 
        (all-permutations (rest lst))) 
      (all-permutations (append (rest lst) (list (first lst))) (rest remain))))))

Das optionale bleiben Argument für cdring Sie in der Liste verwendet wird, Drehen der Liste Elemente vor dem Eintritt in die Rekursion.

Quelle

2011-12-09 16:31:34

könnte die Cond in Remove-Duplikate, wenn einzigartige Permutationen erforderlich – mcheema

Wie bekomme ich alle möglichen Permutationen einer Liste mit Common Lisp?

Antwort

Verwandte Themen