Как я могу получить все возможные перестановки списка с Common Lisp?

Question

Я пытаюсь написать функцию Common Lisp, которая выдаст мне все возможные варианты списка, используя каждый элемент только один раз. Например, список '(1 2 3) даст вывод ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).

Я уже написал что-то подобное, но это неуклюже, это не всегда работает, и я даже не очень понимаю это. Я не прошу код, просто, может быть, некоторые рекомендации о том, как думать об этом. Я не очень разбираюсь в написании алгоритмов.

Спасибо, Джейсон

Answer 1

В качестве базового подхода «все перестановки» следуют этой рекурсивной схеме:

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

Если мы будем считать, что в вашем списке нет повторяющихся элементов, следует выполнить следующее:

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

Вот ответ, который позволяет повторять элементы.Код еще более «нецензурный», поскольку он не использует цикл, с тем недостатком, что он менее понятен, чем решение Райнера Йосвига:

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

Необязательный аргумент stay используется для cdring вниз по списку, вращаяэлементы списка перед входом в рекурсию.

Answer 3

Пройдите по вашему списку, выбирая каждый элемент по очереди. Этот элемент будет первым элементом вашей текущей перестановки.

Содержит этот элемент во всех перестановках остальных элементов.

Answer 4

Я не уверен, что ваш вопрос касается Common Lisp или алгоритма.

Здесь есть похожие проблемы (и решения) для других языков, например, Python . Python часто может быть переведен в Common Lisp практически строка за строкой, поэтому выберите один и перенесите его? : -)