Я пытаюсь написать функцию Common Lisp, которая даст мне все возможные перестановки списка, используя каждый элемент только один раз. Например, список '(1 2 3) даст вывод ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 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)))))))
Вот ответ, который допускает повторяющиеся элементы. Код еще более «шепелявый», поскольку он не использует цикл, но его недостаток заключается в том, что он менее понятен, чем решение Райнера Джосвига:
(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 используется для прокручивания списка вниз, вращения элементов списка перед входом в рекурсию.
Пройдитесь по списку, выбирая каждый элемент по очереди. Этот элемент будет первым элементом вашей текущей перестановки.
Минусы этого элемента для всех перестановок остальных элементов.
