Я пытаюсь написать функцию 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)))))))
Вот ответ, который позволяет повторять элементы. Код еще более "lispish", поскольку он не использует цикл, причем недостатком является менее понятное, чем решение 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))))))
Необязательный аргумент останова используется для cdring в списке, вращая элементы списка перед входом в рекурсию.
Пройдитесь по списку, выбирая каждый элемент по очереди. Этот элемент будет первым элементом вашей текущей перестановки.
Мигает этот элемент ко всем перестановкам остальных элементов.
Я не уверен, что ваш вопрос об Common Lisp, или об алгоритме.
Здесь существуют похожие проблемы (и решения) для других языков, например Python. Python часто может быть переведен в Common Lisp виртуально для линии, поэтому выберите один и поместите его?: -)