java - 排列、递归

Question

我有一个作业:用户输入一个字符串，例如 ABCD，程序必须给出所有排列。 我不希望整个代码只是一个提示。这是我到目前为止在他们那里得到的，我没有得到任何实现。

以ABCD为例:

在本例中获取字符串长度的阶乘 4! = 24.

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

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

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

有了这个算法我就拥有了

ABCD

ABD

空调

空调

广告

广告

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