Select a random element out of an object/array based on the percent chance of it showing up

Question

I have an object that looks like this:

"rarity": {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    ...
    "Legendary": "0.01",
    "Mythical": "0.001",
}

The object is set up as 'Name': '% chance', so Common has a 60% chance of showing up, whereas Mythical has a 1 in 100,000 chance of showing up (0.001%)

I want to be able to (Quickly) select a random element based on the percentage chance of it showing up, but I have zero ideas where to begin.

If this is in the wrong StackExchange please let me know, it's programming-related but heavily math-based.

Answer 1

Let's start by taking a random number between 0 and 100000:

const rnd = Math.random() * 100000;

Now, you need to divide the number by 1000 since you want to take into account up to 3 decimals after comma for "Mythical": "0.001"

const percent = rnd / 1000;

Last, just take the key of the number that contains the percent variable.

Example

const rarity = {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    "More rare": "4.989",  // to fill the rest of percentage
    "Legendary": "0.01",
    "Mythical": "0.001"
}

const rnd = Math.random() * 100000;

const percent = rnd / 1000;

let result = null, acc = 0;

Object.keys(rarity).forEach(key => {
  if (result === null && percent > 100 - rarity[key] - acc)
    result = key;
  acc += parseFloat(rarity[key]);
});

console.log(percent + " %", result);

Here you can test how many times each possibility appears in a 100000 loop

const rarity = {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    "More rare": "4.989",  // to fill the rest of percentage
    "Legendary": "0.01",
    "Mythical": "0.001"
}


let testNumber = 100000;
const testResults = {};

while (0 < testNumber--) {

  const rnd = Math.random() * 100000;

  const percent = rnd / 1000;

  let result = null, acc = 0;

  Object.keys(rarity).forEach(key => {
    if (result === null && percent > 100 - rarity[key] - acc)
      result = key;
    acc += parseFloat(rarity[key]);
  });
  
  if (!testResults[result])
    testResults[result] = 0;
    
  testResults[result]++;

}

console.log(testResults);

Answer 2

You can achieve that by:

1. dividing the 0 to 1 segment into sections for each element based on their probability (For example, an element with probability 60% will take 60% of the segment).
2. generating a random number and check in which segment it lands.

STEP 1

make a prefix sum array for the probability array, each value in it will signify where its corresponding section ends.

For example: If we have probabilities: 60% (0.6), 30%, 5%, 3%, 2%. the prefix sum array will be: [0.6,0.9,0.95,0.98,1]

so we will have a segment divided like this (approximately): [ | | ||]

STEP 2

generate a random number between 0 and 1, and find it's lower bound in the prefix sum array. the index you'll find is the index of the segment that the random number landed in

Here's how you can implement this method:

let obj = {
    "Common": "60",
    "Uncommon": "25",
    "Rare": "10",
    "Legendary": "0.01",
    "Mythical": "0.001"
}
// turning object into array and creating the prefix sum array:
let sums = [0]; // prefix sums;
let keys = [];
for(let key in obj) {
    keys.push(key);
    sums.push(sums[sums.length-1] + parseFloat(obj[key])/100);
}
sums.push(1);
keys.push('NONE');
// Step 2:
function lowerBound(target, low = 0, high = sums.length - 1) {
    if (low == high) {
        return low;
    }
    const midPoint = Math.floor((low + high) / 2);
  
    if (target < sums[midPoint]) {
        return lowerBound(target, low, midPoint);
    } else if (target > sums[midPoint]) {
        return lowerBound(target, midPoint + 1, high);
    } else {
        return midPoint + 1;
    }
}

function getRandom() {
    return lowerBound(Math.random());
}

console.log(keys[getRandom()], 'was picked!');

hope you find this helpful. If you need any clarifications please ask

Note: (In Computer Science) the lower bound of a value in a list/array is the smallest element that is greater or equal to it. for example, array:[1,10,24,99] and value 12. the lower bound will be the element with value 24. When the array is sorted from smallest to biggest (like in our case) finding the lower bound of every value can be done extremely quickly with binary searching (O(log(n))).

EDIT: added code example