Re: Array of random, non-repeating numbers

• Subject: Re: Array of random, non-repeating numbers
• From: Rob Ross <email@hidden>
• Date: Thu, 13 Jul 2006 15:40:46 -0700
• Delivered-to: email@hidden
• Delivered-to: email@hidden

On Jul 13, 2006, at 3:00 PM, Michael Ash wrote:

On 7/13/06, Rob Ross <email@hidden> wrote:

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]

...<snip>...

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.

Rob

_______________________________________________
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

• Prev by Date: Re: NSEvent -keyCode decoder ring?
• Next by Date: Re: Brightness/contrast in NSMovieView?
• Previous by thread: Re: Re: Array of random, non-repeating numbers
• Next by thread: Re: Array of random, non-repeating numbers
• Index(es):
  • Date
  • Thread