¿Cómo puedo obtener todas las permutaciones posibles de una lista con Common Lisp?

Estoy tratando de escribir una función Common Lisp que me dé todas las permutaciones posibles de una lista, usando cada elemento solo una vez. Por ejemplo, la lista '(1 2 3) dará la salida ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).¿Cómo puedo obtener todas las permutaciones posibles de una lista con Common Lisp?

Ya escribí algo que funciona, pero es torpe, no siempre funciona y ni siquiera lo entiendo. No estoy pidiendo el código, solo tal vez para obtener orientación sobre cómo pensarlo. No sé mucho sobre escribir algoritmos.

Gracias, Jason

Fuente

2010-01-18 Jason

por lo general es una buena idea publicar el código que ha escrito hasta ahora. De esta forma, podemos ver en qué dirección está pensando ... –

Si esto es tarea, por favor marque como tal. –

Esto no es tarea. A propósito omití el código que tengo hasta ahora. No quiero manchar las respuestas con mi idea errónea. – Jason

-2

no estoy seguro de si su pregunta se refiere a Common Lisp, o sobre el algoritmo.

Existen problemas (y soluciones) similares para otros idiomas aquí, por ejemplo, Python. Python a menudo se puede traducir a Common Lisp virtualmente línea por línea, así que elija uno y póngalo en el puerto? :-)

Fuente

2010-01-18 17:02:46 Ken

Como criterio básico, "todas las permutaciones" siguen este patrón recursivo:

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

Si tomamos como dado que no tiene elementos duplicados en su lista, el siguiente debe hacer:

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

Fuente

2010-01-18 17:09:00 Vatine

¡Gracias! Esto es algo así como lo que tuve, pero con algunas pequeñas e importantes diferencias. El único problema que veo con esto es que (todas las permutaciones '(1 2 3)) y (todas las permutaciones' (1 1 2 3)) dan el mismo resultado, pero eso debería ser lo suficientemente fácil de cambiar. (Mi objetivo final aquí es mezclar palabras.) – Jason

Si tiene elementos indistinguibles, se vuelve un poco más complicado, tendrá que hacer un preprocesamiento para evitar generar "la misma" permutación más de una vez. Sin embargo, en lugar de utilizar una lista como la anterior, usar un vector de (SÍMBOLO CONTAR) como la estructura de datos que transfiere y disminuir el recuento (en una copia) en lugar de eliminar también debe ocuparse de eso. – Vatine

(permutaciones defun() (etiquetas ((do-permutaciones (artículos) (si los artículos (mapcan (lambda (x) (mapcar (lambda (y) (cons xy)) (do-permutaciones (quitar x items)))) '(())))) (do-permutations' ("Guy" "Man" "Dude")))) –

Examine su lista, seleccionando cada elemento sucesivamente. Ese elemento será el primer elemento de tu permutación actual.

Convierte ese elemento en todas las permutaciones de los elementos restantes.

Fuente

2010-01-18 17:09:16

Aquí está la respuesta que permite elementos repetidos. El código es aún más "lispish", ya que no utiliza bucle, con la desventaja de ser menos comprensible que la solución de 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))))))

El opcional permanecen argumento se utiliza para cdring abajo en la lista, la rotación de la lista elementos antes de entrar en la recursión.

Fuente

2011-12-09 16:31:34

podría envolver el cond en remove-duplicates si las permutaciones únicas necesario – mcheema

¿Cómo puedo obtener todas las permutaciones posibles de una lista con Common Lisp?

Respuesta

Cuestiones relacionadas