Come posso ottenere tutte le possibili permutazioni di una lista con Common Lisp?

Question

Sto provando a scrivere una funzione Common Lisp che mi fornirà tutte le possibili permutazioni di una lista, usando ogni elemento una sola volta. Ad esempio, l'elenco '(1 2 3) fornirà l'output ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).

Ho già scritto qualcosa che funziona, ma è goffo, non sempre funziona e non lo capisco nemmeno veramente. Non sto chiedendo il codice, solo forse per qualche consiglio su come pensarci. Non so molto sulla scrittura degli algoritmi.

Grazie, Jason

Answer 1

non sono sicuro se la tua domanda è di circa Common Lisp, o circa l'algoritmo.

Ci sono problemi simili (e soluzioni) per altre lingue qui, ad es. Python. Python può spesso essere tradotto in Common Lisp virtualmente line-for-line, quindi sceglierne uno e portarlo? :-)

Answer 2

Come un approccio di base, "tutte le permutazioni" seguono questo schema ricorsivo:

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

Se prendiamo come dato di non avere elementi duplicati nel proprio elenco, il seguente dovrebbe fare:

 
(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))))))) 

Answer 3

Passeggiata nell'elenco, selezionando ogni elemento a turno. Quell'elemento sarà il primo elemento della tua permutazione corrente.

Contro questo elemento per tutte le permutazioni degli elementi rimanenti.

Answer 4

Ecco la risposta che consente elementi ripetuti. Il codice è ancora più "lispish" in quanto non utilizza loop, con lo svantaggio di essere meno comprensibili soluzione di Rainer Joswig:

(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)))))) 

l'opzionale rimangono argomento è usato per cdring l'elenco, ruotando la lista elementi prima di entrare nella ricorsione.