在没有映射函数的列表中生成排列

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 ...) ... (p1 p2 ... x).

因此，让我们编写一个函数来执行此操作：给定一些对象和列表的函数将 'thread' 对象遍历列表，创建一堆新列表，并在每个点插入对象。出于将变得清晰的原因，此函数将采用一个额外的参数，该参数是将新排列附加到其前面的事物列表。它还将使用一些本地函数来完成实际工作。

这里是：

(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 只是一个无端的 hack，因为那时 erofeb 已经死了——这个函数实际上没有变化。

我们可以测试一下：

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

知道 ()（即 () 和单元素列表（包含该列表的列表）的排列`;
使用 thread-elements-through-lists 和对自身的递归调用来计算任何更长列表的排列。

在没有映射函数的列表中生成排列

Generating permutations in Lisp withous map functions

lisp

algorithm

recursion

functional-programming