Every possible combination of the letters in a word?

Discussion in 'General Programming Support' started by Icyculyr, Jun 24, 2010.

  1. Icyculyr

    Icyculyr I'm a Mac

    +67 / 0 / -0

    I'm trying to figure out how to write a program to create every possible combination of the letters in a word.

    So, for example, "one" would produce, "one, oen, eon, eno, noe, neo". After I get it working, I'll replace "one" with a longer word.

    Any thoughts on how I'd do this?
  2. Slapshot136

    Slapshot136 Divide et impera

    +483 / 2 / -0
    have a recursive loop that picks 1 letter for the first letter for each possible letter (check for doubles and only call those once) and then calls itself with the rest of the letters - once it's called with only 1 unique letter it should end since there are no more possible alternations on that route

    so like the function is called with One

    then it calls itself with On, ne, and eO

    then On calls itself with O and n
    ne calls itself with n and e
    eO calls itself with e and O

    but when called with O, n, or e, it stops since there's only 1 possible combination

    (this function would return an array of strings)
  3. Icyculyr

    Icyculyr I'm a Mac

    +67 / 0 / -0
    Great, thanks.
  4. Slapshot136

    Slapshot136 Divide et impera

    +483 / 2 / -0
    1 more thing I forgot - your function should know how many strings it receives when it calls itself, you find it like this:

    (# of letters)! divided by ((# of O's)! * (# of n's)! * (# of e's)! )

    (! stands for factorial, 5! = 5*4*3*2*1)
  5. monoVertex

    monoVertex I'm back!

    +458 / 0 / -0
    In general, where you have a problem similar to this one (you need to obtain all the solutions to a problem), you use Backtracking (which is what Slapshot described). Higher speeds for backtracking could be achieved by using recursive functions.

    Another thing you should be aware of, the larger the word, the longer you'll wait. A word with 5 letters has 5! possible combinations, which is 120. 6! is 720 and 7! is already 5040. Although, of course, with computers more and more advanced this day, this might not be an issue for you, depending on what you use this for.
  6. SerraAvenger

    SerraAvenger Cuz I can

    +235 / 0 / -0
    I uses the ruby.

    This would be another ruby way, if you want to see how it could be done internally:
    def permutations array
      if array.size < 2
        yield array
        array.each do |element|
          permutations(array.select() {|n| n != element}) \
          {|val| yield([element].concat val)}

Share This Page