如何在Scheme中重复生成一定大小的所有排列? [英] How do I generate all permutations of certain size with repetitions in Scheme?

问题描述

我正在学习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}.

问题在于我不知道如何选择4次"a"，并且记住我已经选择了4次，然后再选择"a" 3次，选择"b"一次，并记住所有这些，所以我不再选择它.

我知道使用递归算法可以最好地解决这类问题，但这只会使所有事情变得更加复杂，例如，我如何在递归中记忆，我选择了哪些元素.

我根本不知道如何解决这个问题.如果有人写下解决这个问题的思考过程，我将感到非常高兴.非常感谢！

请帮助我.

感谢Boda Cydo.

解决方案

从过程的界面和预期的结果开始是很好的.您的过程将被称为(permutations size elements)，并期望返回ELEMENTS中项目的排列列表，每个排列的长度为SIZE个项目.该图将以列表形式表示排列".因此，如果您呼叫(permutations 1 '(a b c))，则期望输出为((a) (b) (c)).

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

要回答递归步骤，您必须弄清楚对大小为N-1的结果执行什么操作才能得到大小为N的结果.为此，可以帮助写出一些较小的N和预期的结果.看看是否可以辨别出一种模式:

ELEMENTS = (a b)
SIZE   (PERMUTATIONS SIZE ELEMENTS)
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)，您可以通过获取R中的每个置换P来获得(permutations (+ n 1) elements)，然后对于ELEMENTS中的每个元素E，将E附加到P上以创建一个新的排列，并收集它们的列表.我们可以使用嵌套MAP来做到这一点:

(define (permutations size elements)
  (if (zero? size)
      '(())
      (flatmap (lambda (p)            ; For each permutation we already have:
                 (map (lambda (e)     ;   For each element in the set:
                        (cons e p))   ;     Add the element to the perm'n.
                      elements))
               (permutations (- size 1) elements))))

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

当然，所有这些假设都是您知道的，并且能很好地处理MAP等序列操作.如果您不这样做，那么像我在这里所做的那样，想出一个优雅的解决方案真的很困难.

I am learning Scheme and I am trying to generate permutations with repetitions of certain size.

For example, given n=4 and set S = {a, b, c, d, e, f}, I'd like to generate all possible permutations: {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}.

The trouble is that I can't understand how to pick 'a' 4 times, and remember that i had picked it 4 times, then pick 'a' 3 times, and 'b' one time, and remember all this, so I don't pick it again.

I know that these kinds of problems are best solved with recursive algorithms, but it just makes everything more complicated, like, how do I remember in the recursion, what elements have I picked.

I don't know how to approach this problem at all. I would be very glad if someone wrote out the thought process of solving this problem. I'd appreciate it very much!

Please help me.

Thanks, Boda Cydo.

解决方案

It's good to start from the procedure's interface and expected results. Your procedure is going to be called (permutations size elements) and is expected to return a list of permutations of the items in ELEMENTS, each permutation being SIZE items long. Figure you're going to represent a "permutation" as a list. So if you called (permutations 1 '(a b c)) you'd expect an output of ((a) (b) (c)).

So the trick about recursive procedures, is you have to figure out what the base condition is that you can answer easily, and the recursive step which you can answer by modifying the solution of a simpler problem. For PERMUTATIONS, figure the recursive step is going to involve decreasing SIZE, so the base step is going to be when SIZE is 0, and the answer is a list of a zero-length permutation, i. e. (()).

To answer the recursive step, you have to figure out what to do to the result for size N - 1 to get a result for size N. To do this, it can help to write out some expected results for small N and see if you can discern a pattern:

ELEMENTS = (a b)
SIZE   (PERMUTATIONS SIZE ELEMENTS)
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) ... )

So basically what you want to do is, given R = (permutations n elements), you can get (permutations (+ n 1) elements) by taking each permutation P in R, and then for each element E in ELEMENTS, adjoin E to P to create a new permutation, and collect a list of them. And we can do this with nested MAPs:

(define (permutations size elements)
  (if (zero? size)
      '(())
      (flatmap (lambda (p)            ; For each permutation we already have:
                 (map (lambda (e)     ;   For each element in the set:
                        (cons e p))   ;     Add the element to the perm'n.
                      elements))
               (permutations (- size 1) elements))))

I'm using FLATMAP for the outer mapping, because the inner MAP creates lists of new permutations, and we have to append those lists together to create the one big flat list of permutations that we want.

Of course, this is all assuming you know about and have a good handle on sequence operations like MAP. If you don't it'd be real difficult to come up with an elegant solution like I just did here.

这篇关于如何在Scheme中重复生成一定大小的所有排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！