Bug in Ruby code for permutations algorithm?

Question

I altered some code I found on the web, but my version assigns the last lexicographic permutation in the set to all elements of the set. Can anyone tell me why that is? Here's my code:

$permutations = []

def perms(array)  
  $permutations.push array

  #handle the case when the length of 'array' is one or less
  if array.length <= 1
    return $permuations
  end

  #find the first element less than the one following it
  i = (array.length - 2)
  until array[i] < array[i+1]
    i = (i - 1)    
  end

  #if the array is in descending order, we've finished 
  if i < 0
    return $permutations
  end

  #identify the first element larger than 'i'
  j = (array.length - 1)
  until array[j] > array[i]
    j = (j - 1)
  end

  #swap the 'ith' and 'jth' elements
  array[i], array[j] = array[j], array[i]

  #reverse the list from 'i + 1' to the end
  i = (i + 1)
  j = (array.length - 1)
  until j < i
    array[i], array[j] = array[j], array[i]
    i += 1
    j -= 1
  end

  #run the method again, with the newest permutation as the seed
  perms(array)
end

#test the method 
perms([0, 1, 2])
print $permutations

The output I'm getting is: [[2, 1, 0], [2, 1, 0], [2, 1, 0], [2, 1, 0], [2, 1, 0], [2, 1, 0]]

Thanks in advance for any help!

You are re-using the same array object each time. Change `$permutations.push array` to `$permutations.push array.clone` — Neil Slater, Jun 09 '14 at 07:52
thanks! that fixed it. I a noob obviously, and I can't understand why that worked. can you illuminate? — Ice101781, Jun 09 '14 at 08:00
in other words, I would've expected the program to output [[0, 1, 2],...,[0, 1, 2]] if I was re-using the same array object each time; namely array = [0, 1, 2]. but the program did run its course...why did it push the correct number of permutations, but all [2, 1, 0] ? — Ice101781, Jun 09 '14 at 08:06
@Ice101781: Because you modify the object when you do `array[i], array[j] = array[j], array[i]` - that affects *the* one Array object that you have pointed `array` to, and pushed multiple times into the other Array (in `$permutations`) — Neil Slater, Jun 09 '14 at 09:10
@quetzalcoatl: This has been asked in many guises, many times though. I'd direct OP o e.g. http://stackoverflow.com/questions/2635156/object-assignment-and-pointers for more expanded answers, as the specific bug in this permutations code is unlikely to be be a search term. Another possibility: http://stackoverflow.com/questions/1872110/is-ruby-pass-by-reference-or-by-value — Neil Slater, Jun 09 '14 at 09:12

score 0 · Accepted Answer · answered Jun 10 '14 at 02:15

can you illuminate?

Let me try.

Imagine you want to have a catalogue of various funny body positions. So you get this model, Cindy, and ask her to stand on one leg. Then you ask her puff her cheeks and put hands under her chin. Then, another dozen or so positions. At last, you ask her to take a bow.

In the end, you do not have 15 different Cindys, each in her different pose. You have just the one, currently taking a bow.

However, if you snapped an image of Cindy at every pose, you now have a gallery of different Cindy poses.

clone should give you a very lifelike image of Cindy. That way, even if the original Cindy takes another pose, you still have the cloned Cindy to show the previous pose.

Your array is a Cindy. You add that same array many times to $permutations, and change it in between; but every entry in $permutations is that same poor array. Whichever permutation you look at, it will just be whatever pose array is in at the end. You need a number of different arrays, and clone will make them for you - taking a snapshot of whatever array was at the time of cloning, leaving array to go to the next pose without losing record of the previous ones.

EXCELLENT ANSWER. Thanks so much. As I thought more about the problem, I figured your explanation must be the cause. — Ice101781, Jun 10 '14 at 03:34

Bug in Ruby code for permutations algorithm?

1 Answers1