仅使用基本构造通过方案创建 n 大小的排列

Question

是否可以仅使用基本方案构造来生成列表的 n 大小排列？

Answer 1

使用define，你可以这样做（如果没有define，答案是否定的，因为你需要使用递归）：

首先定义一个函数，它接受一个列表列表和一个值，并返回一个列表列表，其中给定的项目已添加到原始列表列表中的每个列表中。

这可以通过编写一个简单的递归函数来完成，该函数使用 cons 将项目添加到第一个列表（使用 car 获取第一个列表），然后使用 cons 再次将扩展列表添加到在其他列表（即列表列表的cdr）上调用该函数的结果。如果列表为空（因此没有 car 和 cdr），则返回空列表。

您还需要一个从列表中删除给定项目的函数。这也可以通过定义一个接受项目和列表的简单递归函数来完成。在每一步中，如果给定列表的“car”不等于要删除的项目，则应将其添加到递归调用的结果之前。如果相等，则直接返回递归调用的结果。

此外，您还需要一个函数来连接列表。这也可以递归实现，不会太麻烦。

然后定义一个函数，给定一个列表列表和一个项目，以该项目和每个子列表作为其参数调用前一个函数。

现在定义创建 n 大小排列的函数。该函数应采用数字n 和一个列表。如果n是0，它应该返回空列表。否则，它应该为列表中的每个项目 x 递归调用自身，并使用 (- n 1) 作为 n 的新值以及以下结果：从列表中删除 x 作为列表的新值。然后应该连接递归调用的结果。

Answer 2

这是对 Rosetta 中代码的解释，不过，我更改了变量名称以提供帮助使其更具可读性，并添加了我对下面代码的解释。我确实检查了代码在 DrRacket 中是否有效，并且确实有效。

在定义permute之前，需要两个辅助函数，即seq和insert。

seq 构建一个包含数字序列的列表。例如(seq 0 3)-> (0 1 2 3)。
列表中的元素（数字）在insert函数中使用，以将carItem插入到“cdr<”中的各个位置。 /strong>' 列表。

(define (seq start end) 
  (if (= start end) 
      (list end)    ; if start and end are the same number, we are done
      (cons start (seq (+ start 1) end)) 
      )
  )

insert 生成一个列表，其中 carItem 插入到 cdrList 的第“n”个位置。例如，(insert '(bc) 0 'a) -> '(abc) 和 (插入 '(bc) 2 'a) -> '（BCA）。

(define (insert cdrList n carItem)
  (if (= 0 n)
      (cons carItem cdrList) ; if n is 0, prepend carItem to cdrList
      (cons (car cdrList)  
            (insert (cdr cdrList) (- n 1) carItem))))

最后，主函数permute，以递归的方式使用了insert和seq。
例如，当 plist = '(b,c) 时，lambda 的值如下：

; (map (lambda (n)
;    (insert '(b c) n 'a))
;    '(0 1 2)) -> output of seq function given n = 2, which is length of '(b c)
; '((a b c) (b a c) (b c a)) ---> will be the output

(define (permute mylist)
  (if (null? mylist)
      '(())
      (apply append (map (lambda (plist)
                           (map (lambda (n)
                                  (insert plist n (car mylist)))
                                (seq 0 (length plist))))
                         (permute (cdr mylist))))))

(permute '(a b c))

如果上面的嵌套 lambda 让你头晕（对我来说就是如此），请在下面找到，恕我直言，一个更具可读性的“定义”版本，感谢 Matthias Felleisen：

(define (permute mylist)
  (cond 
    [(null? mylist) '(())]
    [else 
      (define (genCombinationsFor plist)
      (define (combineAt n) (insert plist n (car mylist)))
        (map combineAt (seq 0 (length plist))))
        (apply append (map genCombinationsFor (permute (cdr mylist))))]))