排列，递归 [英] Permutations, Recursion

问题描述

我有一个分配:用户输入一个字符串，例如ABCD，程序必须给出alll排列. 我不希望整个代码只是一个提示.这是我到目前为止在理论上没有实现的一切.

I have an assignment: User enters a String, example ABCD and the program has to give out alll the permutations. I don't want the whole code just a tip. this is what i got so far in thery i got nothing implemented.

以ABCD为例:

在这种情况下获得String长度的阶乘4！ = 24.

get factorial of length of String in this case 4! = 24.

24/4 = 6因此，到目前为止，第一个字母必须在6之后更改.

24/4 = 6 So first letter has to change after 6. so far so good.

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

than get factorial of remaining letters which are three 3! = 6.

6/3 = 2每个字母2个位置.从这里开始，我不知道它将如何继续填补24个地方.

6/3 =2 2 places for each letter. from here i don't know how it can continue to fill 24 places.

使用这种算法，我所拥有的就是

With this algorithm all i will have is

ABCD

ABD

AC

AC

AD

AD

B

B

B

B

B

B

.

. (连续有6个C和6个D)

. (continues with 6 C's and 6 D's)

我认为我的问题是我没有很多递归问题的经验，所以谁可以建议一些程序来帮助我更好地了解递归.

I think my problem is i do not have alot of experience with recursive problems so who can suggest some programs to program to help me get to know recursion better please do.

谢谢！如果不清楚，请指出.

Thanks! If somethings aren't clear please point out.

推荐答案

您说对了，递归是正确的做法.您通过一点点数学工作的示例都是正确的，但是有点间接.

You are right that recursion is the way to go. The example you worked thru w/ the little bit of math was all correct, but kind of indirect.

这是一些伪代码:

 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是从集合(或通过索引被视为有序字符集合的字符串)中删除所有重复元素的函数.

---

EDIT

To handle repeated characters without duplicating any permutations. Let unique be a function to remove any repeated elements from a collection (or string that is being treated like an ordered character collection thru indexing).

1)存储结果(包括重复数据)，然后将其过滤掉

1) Store results (including dupes), filter them out afterwards

 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)避免首先生成重复项

2) Avoid generating duplicates in the first place

 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

这篇关于排列，递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！