Dan Zwell
4/30/2007 2:55:00 AM
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