排列、递归

Question

我有一个作业：用户输入一个字符串，例如 ABCD，程序必须给出所有排列。 我不想要整个代码只是一个提示。这就是我到目前为止所得到的，我没有任何实施。

以ABCD为例：

获取字符串长度的阶乘，本例为4！ = 24.

24/4 = 6 所以第一个字母必须在 6 之后改变。到目前为止一切顺利。

比得到剩余字母的阶乘，即三个 3！ = 6.

6/3 =2 每个字母 2 个位置。从这里开始我不知道它如何能够继续填补24个位置。

通过这个算法，我将拥有的是

ABCD

ABD

AC

AC

AD

AD

B

B

B

B

B

B

。

。 （继续 6 C 和 6 D）

我认为我的问题是我在递归问题上没有很多经验，所以谁可以建议一些程序来编程以帮助我更好地了解递归，请这样做。

谢谢！如果有不清楚的地方请指出。

Answer 1

你是对的，递归是要走的路。你通过一点数学计算得出的例子是完全正确的，但有点间接。

这是一些伪代码：

 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse

部分递归树的示例

                      permute({A,B,C}, '')
                   /           |           \
 permute({B,C}, 'A')  permute({A,C}, 'B')   permute({A,B}, 'C')   
                          /          \
               permute({A}, 'BC')    permute({C}, 'BA')
                       |
               permute({}, 'BCA')<---BASE CASE, print 'BCA'

---

编辑

处理重复的字符而不重复任何排列。令 unique 为一个函数，用于从集合（或通过索引被视为有序字符集合的字符串）中删除任何重复元素。

1) 存储结果（包括重复项），然后将其过滤掉

 def permuteRec(charSet, soFar):
     if charSet is empty: tempResults.add(soFar) //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse

 global tempResults[]

 def permute(inString):
     permuteRec(inString, '')
     return unique(tempResults)

 print permute(inString)

2) 首先避免生成重复项

 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of unique(charSet):
         permute(charSet without e, soFar + e)  //recurse

Answer 2

创建一个接受字符串的方法。

从字符串中挑选一个字母并输出。

使用输入字符串减去您选择的字母创建一个新字符串。

如果新字符串至少有 1 个字符，则使用新字符串调用上述方法，

为每个可能的字母选择一个字母。