From: Dan Zwell <dzwell@...>
Date: 2007-04-30T11:55:27+09:00
Subject: Re: sorting by rand?

Peter Seebach wrote:
> l = a.length
> a.each_index { |x| a[x] = a[rand(l)] }
> 
> I'm pretty sure I got the generic shuffle algorithm right (Knuth FTW),
> and if so, it produces quality random results in about 1/4 the time.
> 
> -s
> 
> 

The above probably has a typo or something.

This one's from Cormen, Leiserson, Rivest, and Stein. It swaps each 
element with a random element in the rest of the list (allowing it to be 
swapped with itself sometimes). I don't have the book in front of me, 
but I think it's something like:

   def randomize!(ary)
     for i in 0...(ary.length)
       j = i+rand(ary.length - i)
       # swap ary[i] and ary[j]
       tmp = ary[i]
       ary[i] = ary[j]
       ary[j] = tmp
     end
     ary
   end

I think I can prove that it's a valid sort, but I don't trust my own 
logic that much. I tested it with 1000 items and it seemed to have the 
right number of each item.

 >> a = [0, 1, 2, 3, 4]
=> [0, 1, 2, 3, 4]
 >> randomized = []
=> []
 >> 1000.times do randomized << randomize!(a.dup)
 >> end
=> 1000
 >> count = 0
=> 0
 >> randomized.each {|ary| count += 1 if ary == [3, 1, 2, 0, 4]}
 >> count
=> 8


So for one of the 120 permutations of [0, 1, 2, 3, 4], I counted the 
occurrences of one of them. There were 8. On average, if there are 120 
permutations, there will be 8 of each:

 >> 1000/120
=> 8

Good enough for me, unless I was just really lucky. That happens with 
random numbers, you know.

Dan