scheme - 如何在 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' 一次，并且记住了所有这些，所以我不要再挑了。

我知道这类问题最好用递归算法解决，但它只会让一切变得更加复杂，比如，我如何在递归中记住我选择了哪些元素。

我根本不知道如何解决这个问题。如果有人写出解决这个问题的思路，我会很高兴。我将不胜感激!

请帮我。

谢谢，博达·西多。

Answer 1

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

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

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

元素 = (a b)
大小(排列大小元素)
0 ( () )
1 ( (a) (b) )
2 ( (a a) (a b) (b a) (b b) )
3 ( (a a a) (a a b) (a b a) (a b b) (b a a) ... )

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

(定义(排列大小元素)
(如果(零？大小)
'(())
(flatmap (lambda (p) ; 对于我们已经有的每个排列:
(map (lambda (e) ; 对于集合中的每个元素:
(cons e p)) ;将元素添加到 perm'n。
元素))
(排列(-大小1)元素))))

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

当然，这一切都假设您了解并很好地处理了 MAP 等序列操作。如果你不这样做，像我刚刚在这里做的那样想出一个优雅的解决方案真的很困难。