生成列表的排列

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

將獲得：

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

這裏是一個函數，產生大小爲「大小」號的所有排列，它包括在列表中的元素的「項目」

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