Re: Array of random, non-repeating numbers

FROM : Rob Ross
DATE : Fri Jul 14 04:11:02 2006

On Jul 13, 2006, at 5:50 PM, Nir Soffer wrote:

>
> On 13/07/2006, at 19:39, Michael Ash wrote:
>

>> On 7/13/06, Bobby B <<email_removed>> 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]
>>
>> Transforming this into real code is left as an exercise for the 
>> reader.

>
> Here:
>
> @interface NSMutableArray (Shuffling)
> - (void)shuffle;
> - (void)swapObjectAtIndex:(unsiged)a withObjectAtIndex:(unsiged)b;
> @end
>
> @implementation NSMutableArray (Shuffling)
> - (void)shuffle
> {
>     int max = [self count] -1;


random() % max returns 0 through (max -1), so you're never going to 
get a random value for the last array position. This line should be:

int max = [self count];

>     int i;
>     for (i = 0; i < max; i++) {
>         int choice = random() % max;


You actually need to pick a random number between i (inclusive) and 
max, so this line would be

         int choice = i + (random() % (max - i ));

Also, the last time through the loop, the last array element can only 
exchange places with itself, so as an optimization you would write the
for loop as:

for (i = 0; i < max - 1; i++)



>         [self swapObjectAtIndex:i withObjectAtIndex:choice];
>     }
> }
> - (void)swapObjectAtIndex:(unsiged)a withObjectAtIndex:(unsiged)b
> {
>     id temp = [self objectAtIndex:a];
>     [self replaceObjectAtIndex:a withObject:[self objectAtIndex:b]];
>     [self replaceObjectAtIndex:b withObject:temp];
> }
> @end
>
>
> Best Regards,
>
> Nir Soffer


Rob Ross