Eki Eqbal - 1 year ago 61

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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?

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**