Re: Random number generator
Re: Random number generator
- Subject: Re: Random number generator
- From: Philippe Mougin <email@hidden>
- Date: Mon, 8 Aug 2005 22:34:05 +0200
James DiPalma wrote:
> A suggestion: fill an NSMutable array or an NSMutableIndexSet with
> a set of unique values that will be randomly selected (or randomly
> ordered which seems like our ultimate goal). During each cycle
> randomly choose one of these values and remove it from this set.
> By maintaining a set of unchosen unique values, each cycle will
> always use one call to srandomdev() or similar to generate an
> unchosen unique value. Your code has no need to validate this unique
> value since it was pre-validated by being in your unchosen set.
You can do even better (smaller, faster) by removing the need to
generate all possible values:
NSArray *randomIntegersWithoutDuplicates(int n, int m)
{
// Returns n random integers chosen between 0 and m-1, randomly
ordered, without duplicates.
// Note: m must be greater or equal to n
// Note: returns nil if not enough memory to proceed.
// We put n black balls and m-n white balls into a container.
// Then we randomly extract balls and put them away until the n
black balls are out of the container.
// Note that the "container" is purely conceptual: no memory is
actually used.
NSMutableArray *result = [[[NSMutableArray alloc]
initWithCapacity:n] autorelease];
if (nil == result) return nil;
double blackBallCount = n;
double whiteBallCount = m-n;
int i = 0;
while (blackBallCount > 0)
{
if (drand48() <= blackBallCount / (blackBallCount + whiteBallCount))
{
blackBallCount--;
[result addObject:[NSNumber numberWithInt:i]];
}
else whiteBallCount--;
i++;
}
// Now we shuffle the result
if (n == 0) return result;
for (unsigned j = n-1; j != 0; j--) [result exchangeObjectAtIndex:j
withObjectAtIndex:(random() % (j+1))];
return result;
}
Best,
-- Philippe Mougin
F-Script: The open source scripting language for Cocoa
http://www.fscript.org
_______________________________________________
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