Re: Random number generator without duplicates?
Re: Random number generator without duplicates?
- Subject: Re: Random number generator without duplicates?
- From: Brennan Young <email@hidden>
- Date: Tue, 17 Apr 2001 23:39:05 +0200
- Organization: Magic Lantern
Nigel Smith <email@hidden> wrote
>
(though I'm sure someone will come up with something better!)
You bet! Nobody did it in a way which does not involve checking to see
whether the item is already there (and which is a performance bottleneck
proportional to the number of items being added in all the attempts so far).
My handler goes through exactly as many iterations as there are items to
add, (actually one less), so I'd be willing to bet it's faster in almost
every case.
The chief optimisation is to use a random number to specify the *index*,
rather than the value you are adding. After all, you know that the
values you are adding are integers from 1 to n, so they do not need to
be random.
Check this out...
on randomiseIntegersFromOneTo(n)
set l to {1}
repeat with i from 2 to n
set r to (random number from 1 to i)
set afterInsertion to {} -- default
set beforeInsertion to items 1 thru (r - 1) of l
try -- if this fails, we just use {} instead
set afterInsertion to items r thru (count l) of l
end try
set l to beforeInsertion & i & afterInsertion
end repeat
end randomiseIntegersFromOneTo
Another trick in use here and worth mentioning;
I'm setting 'afterInsertion' to an empty list as a default, so that if
you are trying to insert an item at the end, (r thru (count l)) will
cause an exception because r is greater than (count l). The assignment
will fail, leaving the default value of afterInsertion : {}, so the last
assignment in the loop is always meaningful.
With a couple of extra if tests, you could avoid this, but I think the
'exception' approach is more elegant, and certainly uses less code.
If we had a 'insertAt' command for lists, the body of this handler could
be boiled down to four lines;
on randomiseIntegersFromOneTo(n)
set l to {1}
repeat with i from 2 to n
insertAt(l,(random number from 1 to i), i)
end repeat
end randomiseIntegersFromOneTo
(I have a generic 'insertAt' handler if anyone is interested).
--
_____________
Brennan Young
Artist, Composer and Multimedia programmer
mailto:email@hidden
"Software gets slower faster than hardware gets faster."
-Nikolas Wirth