生成列表的排列

Question

我正在编写一个函数，它接受一个列表并返回参数的排列列表。

我知道如何通过使用删除元素的函数，然后递归地使用该函数来生成所有排列来做到这一点。我现在遇到一个问题，我想使用以下函数：

(define (insert-everywhere item lst)
  (define (helper item L1 L2)
    (if (null? L2) (cons (append L1 (cons item '())) '())
        (cons (append L1 (cons item L2)) 
              (helper item (append L1 (cons (car L2) '())) (cdr L2)))))
  (helper item '() lst))

该函数会将项目插入到列表的每个可能的位置，如下所示：

(insert-everywhere 1 '(a b)) 

will get:

'((1 a b) (a 1 b) (a b 1))

我将如何使用此函数来获取列表的所有排列？

我现在有：

(define (permutations lst)
  (if (null? lst) 
      '()
      (insert-helper (car lst) (permutations (cdr lst)))))

(define (insert-helper item lst)
  (cond ((null? lst) '())
        (else (append (insert-everywhere item (car lst)) 
                    (insert-helper item (cdr lst))))))

但是执行 (permutations '(1 2 3)) 只是返回空列表 '()。

Answer 1

首先，构建一系列相关示例：

(permutations      '()) = ???
(permutations     '(z)) = ???
(permutations   '(y z)) = ???
(permutations '(x y z)) = ???

弄清楚每个答案与其前面的答案之间的关系。也就是说，给定前一个答案（列表尾部）和列表头部的新元素，如何计算每个答案？

Answer 2

这是一个函数，它生成大小为 'size' 的数字的所有排列，它由列表 'items' 中的元素组成

(define (generate-permutations items size)
  (if (zero? size)
      '(())
      (for/list ([tail (in-list (generate-permutations items (- size 1)))]
                 #:when #t
                 [i (in-list items)]
                 #:unless (member i tail))
        (cons i tail))))