用映射函数生成Lisp中的排列

Question

我想在Lisp中生成集合的所有排列的列表。这就是我尝试的：

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

但这不是的好方法

Answer 1

这里有一种方法。

首先，如果你有一个像(x . y)这样的列表，并且你有y的排列，你需要从中创建(x . y)的排列。我们考虑这些排列中的一个p，并使其为(p1 p2 ...)。由此，您需要进行一系列排列，包括x:(x p1 p2 ...)、(p1 x p2 ...)、(p1 p2 x ...)。。。CCD_ 10。

因此，让我们编写一个函数来实现这一点：一个给定某个对象和一个列表的函数将通过列表"线程"该对象，创建一组新的列表，在每个点插入对象。由于显而易见的原因，这个函数将需要一个额外的参数，即将新排列附加到前面的事物列表。它还将使用一个小的局部函数来完成真正的工作。

这是：

(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，因为元素在其上的顺序相反
• CCD_ 15只是一个无端的破解，因为在这一点上CCD_

我们可以测试它：

> (thread-element-through-list 1 '(2 3) '())
((2 3 1) (2 1 3) (1 2 3))

现在，好的，我们实际拥有的不仅仅是y的一个置换，我们有一个它们的列表。我们需要使用`thread-element-through-list将x线程化通过它们中的每一个。所以我们需要一个函数来做到这一点。

(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)的排列。所以你现在需要做的(我不会为你做(是写一个函数：

• 知道()(其为()(和单个元素列表(其为包含该列表的列表(的排列`
• 使用CCD_ 26以及对其自身的递归调用来计算任何更长列表的排列