From: Daniel Martin <martin@...>
Date: 2007-04-23T14:17:53+09:00
Subject: Re: Shuffle Method

Ari Brown <ari@aribrown.com> writes:

> I've been writing my own shuffling method, and I end up getting
> doubles in it.

The problem is that you don't clear out helper_array between cycles of
the while loop.  It's still got junk left in it from the previous time
through the loop.  Moving one line fixes this problem:  (I've left the
indentation the same so that you can more easily find the line that I
moved around)

 def recurssive_shuffle some_array
   n = some_array.length
   new_array = []
   while n != 0
     r = rand(n)
   helper_array = []
     while some_array.length != (r + 1)
       helper_array.push some_array.pop
     end
     new_array.push some_array.pop
     n = (n - 1)
     helper_array.each do |item|
       some_array.push item
     end
   end
   puts new_array
 end

However, it occurs to me that this algorithm is easier to express as:

 # "recursive" only has one "s"
 def recursive_shuffle some_array
   new_array = []
   while ! some_array.empty?
     r = rand(some_array.length)
     new_array.push some_array.delete_at(r)
     helper_array = some_array.slice!(r..-1)
     helper_array.reverse!
     some_array.concat helper_array
   end
   puts new_array
 end

It took me a while to realize that you were reversing the bits you'd
pulled off.

I'll also note that the reversing doesn't affect the randomness of
your shuffle at all.  The last three lines of that while loop
(everything dealing with helper_array) could be dropped without
affecting anything.  The sort_by { rand } method is almost certainly
faster, or you could go and implement a standard Fisher-Yates in-place
shuffle:

# shuffles some_array in-place
def shuffle some_array
  2.upto(some_array.length) do |n|
    r = rand(n)
    some_array[n-1],some_array[r] = some_array[r],some_array[n-1]
  end
  some_array
end

(or open up Array, and add this method as shuffle!)

-- 
s=%q(  Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]