Re: Best way to get a non-repeating random number?
Re: Best way to get a non-repeating random number?
- Subject: Re: Best way to get a non-repeating random number?
- From: Michael Ash <email@hidden>
- Date: Mon, 13 Apr 2009 21:02:01 -0400
On Mon, Apr 13, 2009 at 8:46 PM, Uli Kusterer
<email@hidden> wrote:
> On 14.04.2009, at 02:36, Michael Ash wrote:
>>
>> Note that writing a
>> proper shuffling algorithm is harder than it sounds. More properly,
>> it's easy, but figuring out whether you got the correct one or one of
>> the zillions of ones that look correct but aren't is difficult.
>
> Curious which ones look correct but aren't. Have any examples or a link to
> an article?
The most obvious one is this:
for i in 0, length(array):
swap(array[i], array[random(length(array))])
It's probably the first thing you think of when you think "shuffle an
array", but it will produce biased results.
This can be seen if you look at the number of permutations. For
example, a 3-element array has 6 possible orderings. This algorithm
has 27 possible run sequences on a 3-element array (3**3). Since 27 is
not evenly divisible by 6, it's clear that some orderings will appear
more frequently than others.
Wikipedia has a decent discussion of both the proper way and why the
improper ways are improper here:
http://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms
Mike
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden