This week's giveaway is in the EJB and other Java EE Technologies forum.
We're giving away four copies of EJB 3 in Action and have Debu Panda, Reza Rahman, Ryan Cuprak, and Michael Remijan on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes Generating all the permutations nad combinations of the given alphabets Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Generating all the permutations nad combinations of the given alphabets" Watch "Generating all the permutations nad combinations of the given alphabets" New topic
Author

Generating all the permutations nad combinations of the given alphabets

Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Say there is a function which takes a String as its argument and returns a collection of all the permutations of that String.

Like if the input was "abc" the output will be a collection of all 6 Strings.


My Blog SCJP 5 SCWCD 5
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10908
    
  12

I've written one before as a recursive function. If i recall correctly, you pass in a string. if the length of the string is 1, you add it to a collection and return that. if the length is greater than one, you strip of one character and pass that shortened string into the method (thus the recursion). Once you get back the collection of permutations of the shorter string, you insert the one stripped off character at every position in each string in the collection.

so... if you pass in "abc", you'd strip off the 'a', and pass "bc" into the method. you'd then strip off the 'b', and pass the string "c" into the method. this has a length of 1, so you'd insert that into a collection, and return it.

you now back in the iteration where you stripped off the 'b'. So, read the first string in the returned collection, and loop through inserting in the 'b' in every position. This would generate "bc" and "cb". Both of these strings are inserted into a collection, and since there are no more in the collection this method got from it's call, we pass the newly generated one up to the 'a' version.

You'd read the first string, and insert in the 'a' in every possible position, giving "abc", "bac" and "bca". You then read the next string of "cb", and insert the character to give you "acb", "cab", and finally "cba".

It's kind of hard to explain, but it worked.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Thats cool.. It was given to me in one of my recent interviews.

Vivek Kr Singh
Ranch Hand

Joined: Oct 12, 2007
Posts: 56
Based on Fred's Algorithm



SCJP 1.4
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10908
    
  12

just for the record... I never claimed mine was the best or most efficient. I haven't bothered to search for anything better, or even to calculate how poorly it runs in big-O notation. It was something I needed for my Project Euler work, and was pretty simple to write.
Brandon Bernie
Greenhorn

Joined: Nov 02, 2007
Posts: 9
Do the permutations need to be in lexicographic order ? I used a version of the SEPA algorithm for one of the euler problems.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Generating all the permutations nad combinations of the given alphabets
 
Similar Threads
Finding Permutations
generatinf pattern strings
Permutations
Difference between Legal,Appropriate,Correct and Illegal when used in options in SCJP questions
permutation