Re: Array of random, non-repeating numbers
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
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.
Ah, you are right, I stand corrected! I'm not sure now what algorithm
I was thinking of. ;) Sorry.
Rob
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden