Ruby recursive shuffle with rand

Question

I am quite new to Ruby and programming in general, and I am currently trying to study with Chris Pine's book. In chapter 10 there is a task that requires you to return a shuffled version of an array.

I tried the following code for the shuffle method itself, and it worked:

def shuffle array
  recursive_shuffle array, []   
end

def recursive_shuffle unshuffled, shuffled
  if unshuffled.length == 1
    shuffled.push unshuffled[0]
    shuffled.pop                      
    return shuffled
  end

  rand_index = rand(unshuffled.length - 1)
  shuffled.push unshuffled[rand_index]
  unshuffled.delete_at(rand_index)
  recursive_shuffle(unshuffled, shuffled)
end

puts(shuffle(array))

I'm wondering about two things.

First I tried doing it without shuffled.pop and with rand_index = rand(unshuffled.length) instead of length - 1.

However, in the answer the element before the last one was always blank, otherwise it was shuffled and no elements were missing. Then I thought the problem should be in the rand and added the - 1.

At this point the array was, again, shuffled properly, but this time there was always one blank last element of the shuffled array. That's why I added shuffled.pop.

It works fine like this, but I don't understand why it adds a blank element in the first two instances.

Also, if I have an array of 2 elements, its length should be 2 and rand_index should be rand(1), but isn't rand(1) supposed to always be 0? The aforementioned code nevertheless shuffles properly arrays with 2 elements.

I looked at various other topics on Ruby, shuffle, and rand, and couldn't find a similar problem.

Answer 1

If your goal to get the array shuffled you should use the builtin shuffle method, it's both correct and faster than anything you'll write.

If your goal is to implement your own version, this is not well-suited to recursion and you should implement a Fisher-Yates shuffle to avoid bias:

def fy_shuffle(arr)
  a_copy = arr.dup  # don't mutate original array!
  a_copy.each_index do |i|
    j = i + rand(a_copy.length - i)
    a_copy[i], a_copy[j] = a_copy[j], a_copy[i] if i != j
  end
end

If your goal is to learn about recursion, dinjas' answer fixes the problems in your original implementation and works as long as the arrays aren't large enough to blow out the stack.