时间戳

首页 > 解决方案 > 在没有映射函数的 Lisp 中生成排列

algorithm - 在没有映射函数的 Lisp 中生成排列

问题描述

我想在 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)))  
    )
)

但这不是好方法

标签： algorithmrecursionfunctional-programminglisp

解决方案

这是一种方法。

首先，如果您有一个类似的列表(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只是一个无端的hack，因为在那个时候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)。所以你现在需要做的（我不会为你做的）是编写一个函数：

  • 知道()(which is ()and of a single-element list (which is a list contains the list)`的排列；
  • thread-elements-through-lists与对自身的递归调用一起使用来计算任何更长列表的排列。

推荐阅读