• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

Generating all the permutations nad combinations of the given alphabets

 
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
lowercase baba
Posts: 13019
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thats cool.. It was given to me in one of my recent interviews.

 
Ranch Hand
Posts: 56
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Based on Fred's Algorithm

 
fred rosenberger
lowercase baba
Posts: 13019
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Do the permutations need to be in lexicographic order ? I used a version of the SEPA algorithm for one of the euler problems.
 
reply
    Bookmark Topic Watch Topic
  • New Topic