6
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I can read your long note more, but at this point: my code is not any different from Fisher-Yates to shuffle the whole array and take what is needed. But jus that "when the other numbers are not needed, why keep on shuffling them"? My code is exactly this: place 1,000,000 cards out in pile 1, now take 6 cards out randomly from this pile 1, and place it in pile 2. And these are the winners. This procedure is perfect, evenly distributed. And I am doing exactly that, but just that I don't shrink pile 1, but just move the card some where, and that's it. My pile 2 is at the tail of the array. \$\endgroup\$ – deeper-understanding Nov 8 at 13:09
  • \$\begingroup\$ to put it simply, once Fisher-Yates has decided a card at the tail, it is never touched. So we could shuffle 1,000,000 cards, or we could shuffle 9, and the last 9 is never touched anyways, so why shuffle more than 9? \$\endgroup\$ – deeper-understanding Nov 21 at 14:00
  • \$\begingroup\$ Oops, you're right. What was throwing me was frequently seeing contiguous sequences like 22 23 24 25, but that's not a result of a failure to randomly select, but a byproduct of having a large ratio of picks from available options, in combination with the sorting afterwards. \$\endgroup\$ – CertainPerformance Nov 21 at 19:24
3
\$\begingroup\$

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);
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This method will not scale that well. If there is a high number of participants then splice will be an expensive operation. \$\endgroup\$ – Ted Brownlow Nov 2 at 0:21
  • \$\begingroup\$ You said "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" but then if you even remove 1 element, you could be possibly dealing with O(N) where N is 1,000,000, and then when you remove another again, then another 1,000,000 steps, then why not just shuffle it once? Fisher-Yates is good because it doesn't "shrink" the array \$\endgroup\$ – deeper-understanding Nov 2 at 1:16
  • \$\begingroup\$ I forgot that splicing out an element was O(N) because even though the index is known (finding it should be O(1)), everything after it needs to get shifted back by 1. \$\endgroup\$ – Daniel W. R. Hart Nov 2 at 4:28
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ hm, I have read most of your answer, not all, but one thing: creating an array of 1,000,000 is cheap. It is O(n), and is considered "not a big deal". For your method, if it is 1 million and we draw out 6 or 30, then it is ok... but for situation such as, when the company or boss decided, "ok, 500,000 people shall still get something, like 1 coin". Well, then, your algorithm could be running again and again, often finding numbers that are already generated. \$\endgroup\$ – deeper-understanding Nov 8 at 13:04
  • \$\begingroup\$ @deeper-understanding O(n) does not mean cheap. Big O represents complexity as n approaches infinity. Cheap (efficiency) is a comparison between available and required resources for which big O gives no insight. The method you use will depend on requirements of the function. If you need 500K of 1000K then you can use a partial Fisher-Yates shuffle. That is create the full array (1000K) and shuffle (as per Fisher-Yates) to the 500,000th item (no need to continue past draws required) returning the 500K as the winners \$\endgroup\$ – Blindman67 Nov 8 at 15:36
  • \$\begingroup\$ You said "O(n) does not mean cheap. Big O represents complexity as n approaches infinity" Do you even know what you are talking about? Do you understand what O(n) is. It is true that if the requirement is to draw 10 numbers from 1,000,000 numbers, maybe we don't have to go O(1,000,000) or 1,000,000 steps. But as soon as the boss or manager said, let's draw 500,000 out of 1,000,000 then the "try and see already picked" method is not good any more. We don't want to write programs that works well "draw 3 out of 100 and it works well and now draw 50 out of 100 and it doesn't work well". \$\endgroup\$ – deeper-understanding Nov 11 at 14:37
  • \$\begingroup\$ O(n) is one of the cheapest solution already. If we could go O(1) or O(log n) of course it is even better, but O(n) is considered to be usually a viable solution \$\endgroup\$ – deeper-understanding Nov 11 at 14:38
  • \$\begingroup\$ @deeper-understanding Big O is written as a limit. Specifically in CS it represents an asymptotic analysis of a function, There is only one asymptote (n = Infinity). This is why O(n) is equivalent to O(n * m) m = is ANY value > 0.and insignificant as n approaches infinity. Two functions, one needing n * m steps (where m=1) and another n * m (where m = 42 trillion zillion bigillion) have exactly the same complexity O(n). The SAME complexity, one done in a blink of an eye and the other is done some time around the heat death of the universe. Again!! O(n) does not mean cheap \$\endgroup\$ – Blindman67 Nov 11 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.