Re: Re: Array of random, non-repeating numbers

• Subject: Re: Re: Array of random, non-repeating numbers
• From: "Michael Ash" <email@hidden>
• Date: Thu, 13 Jul 2006 18:00:12 -0400
• Delivered-to: email@hidden
• Delivered-to: email@hidden
• Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ls5w8RHgVhmcFQBucMev6T40k6BczHRbQzrX0rhHKcPpnbJM7mvZ3YRCmrl9MqGVlgZqOM1cQBzTEp2AbWOMhQYWPaUmSGvfpmft+fPiaK17RilS2P+PAPFnU4VzlvDg/bhpP+uztoWUX7/qfFIrPq+z4hs5F3DT7sJB9tqw5WM=

On Jul 13, 2006, at 9:39 AM, Michael Ash wrote:

> On 7/13/06, Bobby B <email@hidden> wrote:
>> Hey guys,
>>
>> I'm trying to write a way to generate a random array of X numbers,
>> and
>> the numbers need to be between 0 and X, and not be repeating (its for
>> generating a random playlist.)
>
> Just generate the random playlist directly, don't bother with indexes.
> Put the tracks into an array, then use the canonical shuffle algorithm
> which, in pseudocode, is:
>
> for i from 0 to array_length - 2
>   random_index = random in [i, array_length - 1]
>   swap array[i] with array[random_index]

I did a lot of research on this at one time, long ago...

Your method is *almost* the best way of doing this :)

You can find papers someplace if you search online that show to
maximize "randomness" it is sufficient (and necessary) to only loop
over the first half of the array.

Statistically speaking, the shuffle is "more" random if you only loop

for i from 0 to array_length / 2

than if you loop over the entire array, and it takes half the time of
the full loop as well.

This is not the case. Perhaps you're thinking of some other shuffle
algorithm which is biased?

As I stated, this is the canonical shuffle algorithm. It's known as
the Knuth shuffle or the Fisher-Yates shuffle, and it is
mathematically proven to produce an unbiased, perfectly random
permutation (assuming an unbiased, perfectly random source of random
numbers, of course). Since this provides perfect results, it's
impossible for your halfway case to do better. In addition, your
halfway case can only provide n!/(n/2)! different permutations. Since
there are n! possible permutations, clearly there are many
permutations that it will not be able to produce, making it biased.

For more information, see the "Shuffling algorithms" section of
http://en.wikipedia.org/wiki/Shuffling .

Mike
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list      (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/email@hidden

• Follow-Ups:
  • Re: Array of random, non-repeating numbers
    • From: Rob Ross <email@hidden>

• Prev by Date: RE: parameter passing from cocoa to AS
• Next by Date: [Moderator] Re: OT: Itunes PC SDK
• Previous by thread: Re: Array of random, non-repeating numbers
• Next by thread: Re: Array of random, non-repeating numbers
• Index(es):
  • Date
  • Thread