Examples here are from the repository javascript-algorithms What is "Weighted Random" Let's say you have a list of . The item could be anything. For example, we may have a list of fruits and vegetables that you like to eat: . items [ '🍌', '🍎', '🥕' ] The list of represents the weight (or probability, or importance) of each item. Weights are numbers. For example, weights like would say that: weights [3, 7, 1] you would like to eat more often ( out of times), 🍎 apples 7 3 + 7 + 1 = 11 then you would like to eat less often (only out of times), bananas 🍌 3 11 and the you really don't like (want to eat it only out of times). carrots 🥕 1 11 If we speak in terms of probabilities than the weights list might be an array of floats that sum up to (i.e. ). 1 [0.1, 0.5, 0.2, 0.2] The in this case will be the function that will randomly return you the item from the list, and it will take each item's weight into account so that items with the higher weight will be picked more often. Weighted Random Example of the function interface: const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

function weightedRandom(items, weights) {
  // implementation goes here ...
}

const nextSnackToEat = weightedRandom(items, weights); // Could be '🍎' Applications of Weighted Random In the , the weighted random is used during the "Selection" phase when we need to select the fittest/strongest based on their fitness score for mating and for producing the next stronger generation. You may find an in the article. Genetic Algorithm example Self-Parking Car in 500 Lines of Code In when trying to decide what letter to choose next (to form the sentence) based on the next letter probability. You may find an in the Jupyter notebook. Recurrent Neural Networks (RNN) example Recipe Generation using Recurrent Neural Network (RNN) In to send HTTP requests more often to the servers with the higher weights. Nginx Load Balancing And more... The Algorithm The would be to: straightforward approach Repeat each item in the list according to its weight. Pick the random item from the list. For example, in our case with fruits and vegetables, we could generate the following list of size : 3 + 7 + 1 = 11 const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

// Repeating the items based on weights.
const weightedItems = [
  '🍌', '🍌', '🍌',
  '🍎', '🍎', '🍎', '🍎', '🍎', '🍎', '🍎',
  '🥕',
];

// And now just pick the random item from weightedItems array. However, as you may see, this approach may require a lot of memory, in case if the objects are heavy, and in case if we have a lot of them to repeat in list. weightedItems The would be to: more efficient approach Prepare the list of cumulative weights for each item (i.e. the list which will have the same number of elements as the original list). In our case it will look like this: cumulativeWeights weights cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11] Generate the random number from to the highest cumulative weight value. In our case, the random number will be in a range of . Let's say that we have . randomNumber 0 [0..11] randomNumber = 8 Go through the list from left to right and pick the first element which is higher or equal to the . The index of such element we will use to pick the item from the array. cumulativeWeights randomNumber items The idea behind this approach is that the higher weights will "occupy" more numeric space. Therefore, there is a higher chance that the random number will fall into the "higher weight numeric bucket". const weights =           [3, 7,  1 ];
const cumulativeWeights = [3, 10, 11];

// In a pseudo-representation we may think about the cumulativeWeights array like this.
const pseudoCumulativeWeights = [
  1, 2, 3,               // <-- [3] numbers
  4, 5, 6, 7, 8, 9, 10,  // <-- [7] numbers
  11,                    // <-- [1] number
]; Here is an example of how the function might be implemented: weightedRandom /**
 * Picks the random item based on its weight.
 * The items with higher weight will be picked more often (with a higher probability).
 *
 * For example:
 * - items = ['banana', 'orange', 'apple']
 * - weights = [0, 0.2, 0.8]
 * - weightedRandom(items, weights) in 80% of cases will return 'apple', in 20% of cases will return
 * 'orange' and it will never return 'banana' (because probability of picking the banana is 0%)
 *
 * @param {any[]} items
 * @param {number[]} weights
 * @returns {{item: any, index: number}}
 */
export default function weightedRandom(items, weights) {
  if (items.length !== weights.length) {
    throw new Error('Items and weights must be of the same size');
  }

  if (!items.length) {
    throw new Error('Items must not be empty');
  }

  // Preparing the cumulative weights array.
  // For example:
  // - weights = [1, 4, 3]
  // - cumulativeWeights = [1, 5, 8]
  const cumulativeWeights = [];
  for (let i = 0; i < weights.length; i += 1) {
    cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
  }

  // Getting the random number in a range of [0...sum(weights)]
  // For example:
  // - weights = [1, 4, 3]
  // - maxCumulativeWeight = 8
  // - range for the random number is [0...8]
  const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];
  const randomNumber = maxCumulativeWeight * Math.random();

  // Picking the random item based on its weight.
  // The items with higher weight will be picked more often.
  for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
    if (cumulativeWeights[itemIndex] >= randomNumber) {
      return {
        item: items[itemIndex],
        index: itemIndex,
      };
    }
  }
} Implementation Check the file for the implementation of the function. weightedRandom.js weightedRandom() Check the file for the tests-cases. weightedRandom.test.js First published here

Apple

ORANGE

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Computer Science

2022 - HackerNoon Contributor of the Year - Github

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Computer Science

Nominated for 2022 - HackerNoon Contributor of the Year - Github

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

Implementing the Weighted Random Algorithm with JavaScript

Implementing the Weighted Random Algorithm with JavaScript

Too Long; Didn't Read

Companies Mentioned

Oleksii Trekhleb

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Implementing the Weighted Random Algorithm with JavaScript

Too Long; Didn't Read

Companies Mentioned

Oleksii Trekhleb

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES