Every possible combination of the letters in a word?

[Icyculyr]

Hey,

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?

 

[Slapshot136]

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)

 

[Icyculyr]

Great, thanks.

 

[Slapshot136]

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)

 

[monoVertex]

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.

 

[SerraAvenger]

I uses the ruby.
"neo".permutation

EDIT:
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
  else
    array.each do |element|
      permutations(array.select() {|n| n != element}) \
      {|val| yield([element].concat val)}
    end
  end
end