Permutations, Recursion

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开发者_StackOverflow中文版 code just a tip. this is what i got so far in thery i got nothing implemented.

Taking ABCD as an example:

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

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

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

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

.

. (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.

Here's some pseudocode:

 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

example of partial recursion tree

                      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'

---

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) 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) 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

---

Make a method that takes a string.

Pick a letter out of the string and output it.

Create a new string with the input string minus the letter you picked.

call the above method with the new string if it has at least 1 character

do this picking of one letter for each possible letter.