Eki Eqbal Eki Eqbal - 8 months ago 38
Ruby Question

Find all the possible permutations using Ruby and recursion

I've been trying to solve a simple quiz question to find all the possible permutation of a string using Ruby and recursion.

I have the following Ruby code:

def permutation(string)
return [string] if string.size < 2

chr = string.chars.first
perms = permutation(string[1..-1])

result = []

for perm in perms
for i in (0..perm.size)
result << (perm[0..i] + chr + perm[i..-1])

return result

Whenever I try to test the code with puts permutation("abc") I get the following output:


Theoretically speaking it's supposed to be a very simple and straightforward problem, but I'm sure I'm doing something wrong. Most probably it's something with the ranges of the loops. And I know that Ruby Array class has instance method permutation to do that but I'm trying to solve it for practising.

Please note that the complexity is O(N!) for the current implementation. Is there anyway to enhance the performance further?

Answer Source

To see what the difficulty may be, let's try it with an even simpler example:

string = "ab"

Your desired result is ["ab", "ba"]. Let's see what you get:

string.size #=> 2

so we don't return when

return [string] if string.size < 2
  #=> return ["ab"] if "ab".size < 2

is executed.

Next we calculate:

chr = string.chars.first #=> "a"

Notice that a more direct way of making this calculation is as follows:

chr = string[0]  #=> "a"

or, better, using String#chr,

chr = string.chr #=> "a"

The latter illustrates why chr is not the best choice for the variable name.


perms = permutation(string[1..-1])
  #=> = permutation("b")

I will now indent the return values to emphasize that we are calling permutation a second time. permuation's argument is:

  string #=> "b"

Now when we execute:

  return [string] if string.size < 2
  #=> return ["b"] if "b".size < 2

we return ["b"], so (back to original call to permutation):

perms = ["b"]

to go with chr => "a", calculated earlier. Next:

result = []

for perm in perms
  for i in (0..perm.size)
    result << (perm[0..i] + chr + perm[i..-1])

As perms contains only the single element "b", the two for loops simplify to:

for i in (0.."b".size)
  result << ("b"[0..i] + "a" + "b"[i..-1])

which is:

for i in (0..1)
  result << ("b"[0..i] + "a" + "b"[i..-1])

Notice that "b"[0..0], "b"[0..1] and "b"[0..-1] all equal "b"[0], which is just "b", and "b"[1..-1] #=> ''. Therefore, when i => 0, we execute:

result << ("b"[0..0] + "a" + "b"[0..-1])
  #=> result << ("b" + "a" + "b")
  #=> result << "bab"

and when i => 1:

result << ("b"[0..1] + "a" + "b"[1..-1])
  #=> result << ("b" + "a" + "")
  #=> result << "ba"


result => ["bab" + "ba"]

which clearly is not what you want.

What you need to do is is change the double for loops to:

for perm in perms
  result << chr + perm
  for i in (1..perm.size-1)
    result << (perm[0..i-1] + chr + perm[i..-1])
  result << perm + chr

which could be written more compactly by employing the method String#insert:

for perm in perms
  for i in (0..perm.size)
    result << perm.dup.insert(i,chr)

which you would normally see written like this:

perms.each_with_object([]) do |perm, result|
  (0..perm.size).each { |i| result << perm.dup.insert(i,chr) }

Notice that we have to .dup the string before sending insert, as insert modifies the string.

Doing it like this, you don't need result = []. Neither do you need return result, as parms.each_with_object returns result and if there is no return statement, the method returns the last quantity calculated. Also, you don't need the temporary variable perms (or ch, if desired).

Putting this altogether, we have:

def permutation(string)
  return [string] if string.size < 2
  ch = string[0]
  permutation(string[1..-1]).each_with_object([]) do |perm, result|
    (0..perm.size).each { |i| result << perm.dup.insert(i,ch) }

Let's try it:

  #=> ["ab", "ba"]
  #=> ["abc", "bac", "bca", "acb", "cab", "cba"]
  #=> ["abcd", "bacd", "bcad", "bcda", "acbd", "cabd",
  #    "cbad", "cbda", "acdb", "cadb", "cdab", "cdba",
  #    "abdc", "badc", "bdac", "bdca", "adbc", "dabc",
  #    "dbac", "dbca", "adcb", "dacb", "dcab", "dcba"]

Eki, which one are you in the picture?