Out of N number of participants, draw out M winners

Question

It could be a simple Fisher-Yates, but then if the number of participants is 1,000,000 and the number of winner is only 3, then we really don't need to shuffle the whole 1,000,000 numbers, so the following is to reduce the number of steps, written as a simpler case of drawing 9 winners out of 30 participants:

The following is to consider 30 participants, each numbered from 1 to 30, and take out 9 winners. One will be Grand Prize, and two will be Second Prizes, and 6 Third Prizes.

const NUM_PARTICIPANTS = 30;
const NUM_DRAWN = 9;

console.log(`run: ${NUM_PARTICIPANTS} draw ${NUM_DRAWN}`);

const arr = Array.from(new Array(NUM_PARTICIPANTS), (e, i) => i + 1);

for (let i = arr.length - 1; i >= NUM_PARTICIPANTS - NUM_DRAWN; --i) {
  const j = Math.floor(Math.random() * (i + 1));
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

const results = arr.slice(NUM_PARTICIPANTS - NUM_DRAWN)

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  ")}`);

Answer 1

To pick m from a collection of size n, there are at least a couple of approaches:

• Randomly shuffle an array of numbers (O(n)), then pick the top few (O(m)), resulting in an overall complexity of O(n + m). This is what you're doing currently, though it requires creating an array.

• Repeatedly pick a random number from 0 to n. If a duplicate number is picked, pick again. Repeat m times. This has an overall complexity of around O(m * C), where C is the average number of picks before finding a non-duplicate. It'll range from close to 1 (when n is significantly larger than m) to infinity (when n is equal to m).

If m is close to n, the first approach, that you're doing currently, is quickest, because the other approach results in lots of collisions. If m is significantly smaller than n, the second approach is quickest, because the collision chance C is low. So, where's the break-even point? It'll depend on the engine running the code, but we can do some basic performance tests. I'll use Blindman67's code since it's pretty much exactly what I had in mind.

The below tests aren't 100% reliable, but they'll give you an OK idea of the time required:

// Array sort method:

// Wait for the iframe to load completely
setTimeout(() => {
  
  const NUM_PARTICIPANTS = 1e7;
  const NUM_DRAWN = 3e6;

  const t0 = performance.now();
  // Make the array 0-indexed rather than 1-indexed
  // to avoid unnecessary addition for every element
  const arr = Array.from({ length: NUM_PARTICIPANTS }, (_, i) => i);
  const lowerLimit = NUM_PARTICIPANTS - NUM_DRAWN;
  for (let i = arr.length - 1; i >= lowerLimit; --i) {
    const j = Math.floor(Math.random() * (i + 1));
    // Use a temp variable instead of the destructuring trick, it's probably a bit faster:
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  // Then slice the array and calculate the results
  console.log('Time taken:', performance.now() - t0);
}, 1000);

// Picking random numbers until enough non-duplicates are found:

// Wait for the iframe to load completely
setTimeout(() => {
  
  const NUM_PARTICIPANTS = 1e7;
  const NUM_DRAWN = 3e6;

  const randomInt = range => Math.floor(Math.random() * range);
  const results = createWinners();      

  function createWinners() {
       const t0 = performance.now();
       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);
       }
       // Then slice the array and calculate the results
       console.log('Time taken:', performance.now() - t0);
       return [...winners.values()];
  }
}, 1000);

I tried a few different combinations of NUM_PARTICIPANTS and NUM_DRAWN numbers, and the ratio used above, 10 to 3, seems to be pretty close to the break-even point, when the numbers are large, at least on V8. (If the code runs in a different environment, the ideal ratio to use will likely be different.) At that point, both methods look to take a pretty similar amount of runtime. If you don't have a large number of participants, either approach will work just fine, since it won't take any noticeable amount of time to run the script regardless. But if you have a large number, check the ratio of participants to winners, then choose the appropriate method depending on the ratio.

const createWinners = (numParticipants, numWinners) => (
  numWinners / numParticipants < 0.3
    ? createWinnersWithSetPicking(numParticipants, numWinners)
    : createWinnersWithArraySort(numParticipants, numWinners)
);

If you change the code, you might want to run a performance test again to see what works better, and you might want to adjust the magic ratio. Take into consideration the environment the code runs (or is most likely to run) on too - Node? Chrome? Firefox? Safari?

That said, if your numbers are large enough that performance is an issue, this should almost certainly be done on the server (in Node), not on the client, so as not to be unrunnable on low-end devices.

Answer 2

You could use a loop to cycle through the total number of winners desired, then individually select a random winner and remove it from the array of participants. If you don't want to modify the original array of participants, you can create a copy to work with. This is a way to generate the results array that should scale better with a high number of participants with few winners. How you select the 1st place, 2nd place, and so on, works the same after this code snippet.

const participants = [...arr];
let results = [];

for (let i = 0; i < NUM_DRAWN; i++) {
    const choice = Math.floor(Math.random() * participants.length);
    results.push(participants[choice]);
    participants.splice(choice, 1);
}

Edit: arr.length is now participants.length, since you want the upper range of the random number to match the adjusted size of participants as it loses people.

Edit: Changed the temporary array into a set so that removing elements becomes O(1) instead of O(N). This works best when there are many more participants than winners (3/1,000,000 hell yea!, but 9/30 is not so great). Otherwise the while loop can end up doing many wasted iterations looking for participants not already in results. Notice that now I am dealing directly with the values of the participants, and not array indices. This wouldn't work as well if arr was filled with name strings instead of [1,2,3...,N].

const participants = new Set(arr);
const results = [];

while (results.length < NUM_DRAWN)
    const choice = Math.ceil(Math.random() * NUM_PARTICIPANTS);
    if (participants.has(choice) {
        results.push(choice);
        participants.delete(choice);
    }
}

Answer 3

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()];
}