0. N := 0;
1. NewValue := RandomRange(0, Max+1)
2. Loop through each value in the list: is it the same as NewValue?
3. If so, then repeat 1..2 until you come up with a value that is not in the array yet
4. Add NewValue to array
5. Inc(N)
6. If (N = NRequired) then STOP
Thaddy, wow, that's fantastic!!! I knew there should have been a more efficient way to!
When you google you will often find the same sources. Note that I found a direct link to the C++ sourcecode for the class that I translated. But indeed, after a few clicks on molly's links you finally arrive at the same spot.
And that reaction by Eugene was about the sattoro code, which is different from Molly's links.
[edit] Ah I see, Molly links to Fisher Yates. Sattoro is not Fisher Yates...It is an improvement on Fisher Yates (just one cycle) . Same answer:independent.
No, that answer on stackoverflow is a naive implementation of the same (Sattoro) optimization if I read it correctly.
He actually initializes a whole array for the range needed + 1. (1001)
Thus it wastes space for one element.
Sattoro uses space exactly as is needed. (1000)
So, yes, he came up with a solution that in effect is like Sattoro's, but his implementation is not optimal (one may say wrong, but that doesn't do him justice).
My implementation is EXACT Sattoro and allocates space for the EXACT number of elements.
"Decrement max by 1 and continue. When max is 0, set max back to the size of the array - 1"
Is the wrong order. element zero will never be processed... N=1000... as the comments tell you.
After 11 iterations, all numbers in the array have been selected, max == 0, and the array elements are shuffled:
+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
At this point, max can be reset to 10 and the process can continue.
Code: Pascal [Select]
for i := High(Values) downto 1 do
QuoteCode: Pascal [Select]
for i := High(Values) downto 1 do
Shouldn't that be:Code: Pascal [Select]
for i := High(Values) downto Low(Values)+1 do
LINE 8: j := Random(i);
j ← random integer such that 0 ≤ j ≤ i
Random returns a random number larger or equal to 0 and strictly less than argument L
I would recommend a Sattolo cycle instead of Fisher-Yates. That is a specialized Fisher Yates that is more efficient.
In fact, as described below, it is quite easy to accidentally implement Sattolo's algorithm when the ordinary Fisher–Yates shuffle is intended. This will bias the results by causing the permutations to be picked from the smaller set of (n−1)! cycles of length N, instead of from the full set of all n! possible permutations.
For your Sattolo implementation, you have an error that requires an extra loop iteration. When i = 0 then j = 0, so you are swapping a[0] with a[0]. Therefore:That is not true. You will introduce a fixed member in that case, so it is no longer random over the population.
Line 12: while i > 0 do
should be
Line 12: while i > 1 do
For reference, bugs have been reported:Fixed in LGenerics. :-[
https://bugs.freepascal.org/view.php?id=36696
and
https://github.com/avk959/LGenerics/issues/3