Simulating Random sequences
In games of chance we use random numbers not to simulate random outcomes, but rather to obscure results so that they can not be easily known in advance.
Why bother with random
As any sequence of independent random values is just as likely as any other we don't need to use a (pseudo) random number generator to simulate the generation the sequence.
We can hard code it as follows
const NUM_DRAWN = 9;
const results = [1,2,3,4,5,6,7,8,9];
console.log(`Grand prize: ${results[0]}`);
console.log(`Second prize: ${results.slice(1,3).sort((a, b) => a - b).join(" ")}`);
console.log(`Other winners:\n ${results.slice(3).sort((a, b) => a - b).join("\n ")}`)
It would be statistically as robust as any other method (There are no logical or physical proofs of randomness). That does not mean it is random, it is not at all random, it is just statistically consistent with any other selection method.
However we don't want people to cheat by knowing the outcome ahead of time
Non Trivial Determinism
Computers are deterministic and it is possible to know all winners ahead of time no matter what code you write.
What we want is to make finding out who the winners will be ahead of time as non trivial as possible.
JavaScript's pseudo random is seeded with the system clock. The pseudo random value is a Double (64 bit floating point). Checking if you guessed the correct seed and finding the correct spot in the sequence would require too much work to be worth the effort.
Only the winners
Rather than create an array of 30 (or 1,000,000) people, we need only the array for the winners.
We pick a numbered person and check if that person is in the winning set or not. If not add the person to the set of winners. Do this until you have found all the winners.
const NUM_PARTICIPANTS = 30, NUM_DRAWN = 9;
const randomInt = range => Math.floor(Math.random() * range);
const results = createWinners();
console.log(`Draw ${NUM_DRAWN} from ${NUM_PARTICIPANTS}`);
console.log(`Grand prize: ${results[0]}`);
console.log(`Second prize: ${results.slice(1,3).sort((a, b) => a - b).join(" ")}`);
console.log(`Other winners:\n ${results.slice(3).sort((a, b) => a - b).join("\n ")}`);
function createWinners() {
var draw = randomInt(NUM_PARTICIPANTS);
const winners = new Set([draw]);
while (winners.size < NUM_DRAWN) {
do {
draw = randomInt(NUM_PARTICIPANTS);
} while (winners.has(draw));
winners.add(draw);
}
return [...winners.values()];
}
Notes
To reduce the cost of checking if a winner has already been selected we use Set.
Set
uses a hash table when inserting Set.add and searching Set.has, Set.get. This reduces the seach complexity to \$O(1)\$ rather than \$O(n)\$ for searches like Array.find, Array.findIndex, Array.includes etc...
Halting problem Unfortunately whether this algorithm will finish is "undecidable" [*]. That is, we can not know in advance if the inner loop will exit (assuming Math.random
is truly random or is "undecidable" ).
Care must be taken to ensure you only use this method when selecting A of B (where A is draws B is participants) such that A < B and A / B is small as the complexity is as bad as it can get \$O(2^{2^n})\$ where n represents A (closer to \$1 / (B / A)\$) and the second 2 represents B. Luckily for most real world uses, \$2^{2^n}\$ is very close to \$n\$ and not worth the concern.
[*] Close to "undecidable" as Math.random()
's full sequence is knowable, just not practically accessible
For a given number of winners the algorithms performance increases as the number of participants increases. On average the results of the snippet bellow, 9 of 1 million, requires less work than the snippet above, 9 of 30.
const NUM_PARTICIPANTS = 1e6;
const NUM_DRAWN = 9;
const randomInt = range => Math.floor(Math.random() * range);
const results = createWinners();
console.log(`Draw ${NUM_DRAWN} from ${NUM_PARTICIPANTS}`);
console.log(`Grand prize: ${results[0]}`);
console.log(`Second prize: ${results.slice(1,3).sort((a, b) => a - b).join(" ")}`);
console.log(`Other winners:\n ${results.slice(3).sort((a, b) => a - b).join("\n ")}`);
function createWinners() {
var draw = randomInt(NUM_PARTICIPANTS);
const winners = new Set([draw]);
while (winners.size < NUM_DRAWN) {
do {
draw = randomInt(NUM_PARTICIPANTS);
} while (winners.has(draw));
winners.add(draw);
}
return [...winners.values()];
}