Find all the possible permutations using Ruby and recursion

Question

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])
    end
  end

  return result  
end

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

cacbc
cbabc
cbcac
cbca
cacb
cbab
cba

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 1

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.

Next

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])
  end
end

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])
end

which is:

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

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"

so:

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])
  end
  result << perm + chr
end

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)
  end
end

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) }
end

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) }
  end
end

Let's try it:

permutation("ab")
  #=> ["ab", "ba"]
permutation("abc")
  #=> ["abc", "bac", "bca", "acb", "cab", "cba"]
permutation("abcd")
  #=> ["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?