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

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

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

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

Ответы

Ответ 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)))))))

Ответ 2

Вот ответ, который позволяет повторять элементы. Код еще более "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 в списке, вращая элементы списка перед входом в рекурсию.

Ответ 3

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

Мигает этот элемент ко всем перестановкам остальных элементов.

Ответ 4

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

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