Eki Eqbal - 1 year ago 47

Ruby 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

`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

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.

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?