Генерация перестановок в Лиспе без картографических функций
Я хочу сгенерировать в Лиспе список всех перестановок набора. Вот что я пробовал:
(defun ins(e n l)
(cond
((equal n 1) (cons e l))
(T (cons (car l) (ins e (1- n) (cdr l))))
)
)
;; (print (ins '1 1 '(2 3)))
;; (print (ins '1 2 '(2 3)))
;; (print (ins '1 3 '(2 3)))
(defun insert(e n l)
(cond
((equal n 0) nil)
(T (cons (ins e n l) (insert e (1- n) l) ))
)
)
;; (print (insert '1 3 '(2 3)))
(defun inserare(e l)
(insert e (1+ (length l)) l)
)
;(print (inserare '1 '(2 3))) -> ((2 3 1) (2 1 3) (1 2 3))
И отсюда я просто не могу заставить работать окончательные перестановки. Я пробовал что-то вроде этого:
(defun perm(L)
(cond
((null L) nil)
(T (append (perm (cdr L)) (inserare (car L) L)))
)
)
Но это не лучший подход
Понятно, но я хотел сделать это чисто рекурсивно, без циклов. И это также выглядит как очень профессиональный код на Лиспе, который для меня сложен.
Ответы 1
Вот один из способов.
Прежде всего, если у вас есть список, подобный (x . y), и у вас есть перестановки y, вам нужно будет создать из них перестановки (x . y). Хорошо рассмотрим одну из этих перестановок p, и пусть это будет (p1 p2 ...). Из этого вам нужно будет сделать кучу перестановок, в том числе x: (x p1 p2 ...), (p1 x p2 ...), (p1 p2 x ...)... (p1 p2 ... x).
Итак, давайте напишем функцию для этого: функция, которая получает некоторый объект и список, будет «пропускать» объект через список, создавая кучу новых списков с объектом, вставленным в каждую точку. По причинам, которые станут ясны позже, эта функция будет принимать дополнительный аргумент, представляющий собой список элементов, к которым будут присоединены новые перестановки. Он также будет использовать небольшую локальную функцию для выполнения реальной работы.
Вот:
(defun thread-element-through-list (e l onto)
(labels ((tetl-loop (erofeb after into)
(if (null after)
(cons (nreverse (cons e erofeb)) into)
(tetl-loop (cons (first after) erofeb)
(rest after)
(cons (revappend (cons e erofeb) after) into)))))
(tetl-loop '() l onto)))
Я не буду объяснять детали этой функции, но есть несколько вещей, которые стоит знать:
tetl-loopестьthread-element-through-list-loop;erofeb— этоbeforeв обратном порядке, потому что элементы на нем расположены в обратном порядке;nreverse— это просто бесполезный взлом, потому что в этот моментerofebв противном случае мертв — в этой функции фактически нет мутации.
И мы можем проверить это:
> (thread-element-through-list 1 '(2 3) '())
((2 3 1) (2 1 3) (1 2 3))
Итак, хорошо, на самом деле у нас есть не просто одна перестановка y, у нас есть их список. И нам нужно пропустить x через каждый из них, используя `thread-element-through-list. Итак, нам нужна функция, чтобы сделать это.
(defun thread-element-through-lists (e ls onto)
(if (null ls)
onto
(thread-element-through-lists
e (rest ls)
(thread-element-through-list e (first ls) onto))))
У этого также есть аргумент, который определяет, к чему он добавляет свои результаты, и вы можете видеть, как этот список onto теперь передается для построения списка.
И мы можем проверить это
> (thread-element-through-lists '1 '((2 3) (3 2)) '())
((3 2 1) (3 1 2) (1 3 2) (2 3 1) (2 1 3) (1 2 3))
Посмотрите на это внимательно. Я дал thread-element-through-lists, 1 и список перестановок (2 3), и получились у меня перестановки (1 2 3). Итак, что вам сейчас нужно сделать (чего я за вас делать не собираюсь), так это написать функцию, которая:
- знает перестановки
()(то есть()и одноэлементного списка (который представляет собой список, содержащий этот список)`; - использует
thread-elements-through-listsвместе с рекурсивным вызовом самого себя для вычисления перестановок любого более длинного списка.
или мы могли бы вывернуть его наизнанку и много снимать, вместо того, чтобы кончать. :) каждая перестановка будет доступна отдельно, в свою очередь; мы могли бы скопировать их в список результатов или просто обработать их одну за другой.
@WillNess: да, это то, что я бы сделал в реальной жизни или что-то в этом роде.
См. код вокруг sourceforge.net/p/clocc/hg/ci/default/tree/src/cllib/…