如何在Scheme中重复生成一定大小的所有排列？

Question

我正在学习Scheme,我正在努力生成重复一定大小的排列.

例如,给定n = 4并设置S = {a,b,c,d,e,f},我想生成所有可能的排列:{a,a,a,a},{a,a, A,b},...,{A,A,A,F},{A,A,b,A},{A,A,b,b},...,{A,A,b, F},... {F,A,A,A},{F,A,A,b} ...,{F,A,A,F},... {F,F,F,F }.

问题是我无法理解如何选择'a'4次,并记住我已经选择了4次,然后选择'a'3次,'b'一次,并记住所有这些,所以我不要再挑选了.

我知道,这类问题最好用递归算法解决,但它只是让一切更加复杂,比如,我怎么记得在递归,有什么因素我挑.

我根本不知道如何处理这个问题.如果有人写出解决这个问题的思考过程,我会很高兴.我非常感激!

请帮我.

谢谢,Boda Cydo.

Answer 1

最好从程序的界面和预期结果开始。您的过程将被调用(permutations size elements)，并预计返回 ELEMENTS 中项目的排列列表，每个排列的长度为 SIZE 项目。假设您要将“排列”表示为列表。因此，如果您调用，(permutations 1 '(a b c))您会期望输出((a) (b) (c)).

因此，递归过程的技巧是，你必须弄清楚你可以轻松回答的基本条件是什么，以及你可以通过修改更简单问题的解决方案来回答的递归步骤。对于排列，计算出递归步骤将涉及减小 SIZE，因此基本步骤将是当 SIZE 为 0 时，答案是零长度排列的列表，即(())。

要回答递归步骤，您必须弄清楚如何处理大小 N - 1 的结果才能获得大小 N 的结果。为此，它可以帮助写出小 N 的一些预期结果，看看您是否可以可以辨别一种模式：

元素 = (ab)
大小（排列大小元素）
0 ( () )
1（（一）（二））
2 ( (aa) (ab) (ba) (bb) )
3 ( (aaa) (aab) (aba) (abb) (baa) ... )

所以基本上你想要做的是，给定 R = (permutations n elements)，你可以(permutations (+ n 1) elements)通过获取 R 中的每个排列 P ，然后对于 ELEMENTS 中的每个元素 E ，将 E 与 P 相邻以创建一个新的排列，并收集它们的列表。我们可以使用嵌套 MAP 来做到这一点：

（定义（排列大小元素）
  （如果（零？大小）
      '(())
      (flatmap (lambda (p) ；对于每个排列，我们已经有了：
                 (map (lambda (e) ; 对于集合中的每个元素：
                        （缺点 ep））；将元素添加到 perm'n。
                      元素））
               （排列（- 大小 1）元素））））

我使用 FLATMAP 进行外部映射，因为内部 MAP 创建新排列列表，并且我们必须将这些列表附加在一起以创建我们想要的一个大平面排列列表。

当然，这一切都假设您了解并能很好地掌握 MAP 等序列操作。如果你不这样做，那么就很难像我刚才所做的那样提出一个优雅的解决方案。