CODEWITHSUNDEEP
rubyrecursionconcatenationpermutation
bioball
bioball

Reputation: 1359

Why is my concatenation messing up when I pass in an array?

I wrote a method to permute an array (I realize Ruby comes with a permutation function, but I wanted to practice algorithms). I'm encountering a really weird error and have no idea why this is happening.

Here's my code:

def permute(arr)
  permutation(arr.sort)
end

def permutation(arr, result=[])
  k = nil
  result += [arr]
  (arr.length-1).times do |i|
    if arr[i] < arr[i+1]
      k = i
    end
  end
  if k.nil?
    return result
  else
    l = -1
    arr.length.times do |i|
      if arr[k] < arr[i]
        l = i
      end
      l = nil if l == -1
    end
    arr[k], arr[l] = arr[l], arr[k]
    arr = arr[0..k] + arr[k+1..-1].reverse
    return permutation(arr, result)
  end
end

The method is recursive, and on each successive call I concatenate arr to my result variable with result += [arr] because I want the method to return a nested array, e.g. [[1, 2, 3], [1, 3, 2]..]

However, when I call this method it gives me a completely weird result.

permute([1,2,3])
=> [[1, 3, 2], [2, 3, 1], [2, 3, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]

Why are last three results all [3,2,1]? And the other arrays aren't correct either. The really strange thing is that I can fix this by changing my concatenation to result += arr. With this change, I get the following:

permute([1,2,3])
=> [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]

#I know that I can get my desired nested array like so, but that's beside the point
[1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1].each_slice(3).to_a
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

I don't get the nested arrays that I want, but the output gives me the correct permutation. Why is it working correctly now, but not which I was using result += [arr]? Is this a Ruby bug, or am I missing something here?

Upvotes: 2

Views: 101

Answers (1)

David Ljung Madison Stellar
David Ljung Madison Stellar

Reputation: 3215

You're being bit by a common ruby mistake - you're modifying the original array since the 'arr' argument to permutation() is a reference to the array

Try changing:

result += [arr]

to:

result += [arr.dup]

And then presto!

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

(Incidentally, you're still monkeying with the original 'arr' values with this solution and should probably clean that up)

Upvotes: 5

Related Questions