Skip to main content

How to Select from a JavaScript Weighted List (NodeJS, Browser)

This article covers how to select a random item from a weighted list in JavaScript. It also contains an example of how to test and visualize the results using the command line or the browser.

How to Select from a JavaScript Weighted List (NodeJS, Browser)

Step 1. Create a project​

To get started, create a new project. On a Mac I would do it like this:

mkdir -p ~/projects
cd ~/projects
mkdir js-weighted-choice-101
cd js-weighted-choice-101

Step 2. Initialize the project as a module​

To use a more up to date version of JavaScript, we need to use npm to indicate that our code is a module. If that is new to you, see the link to my article on creating a JavaScript module at the end of this article.

  • Add this line to package.json and save the file:
npm init -y
  • Open the project in a code editor
  • Add this line to package.json:
"type": "module",

Step 3. Create a JavaScript file​

Use the editor to create a new file called weighted-choice.js or on the Mac command line:

touch weighted-choice.js

Step 4. Create the weightedChoice function​

Edit weighted-choice.js and add the following:

// Author: Mitch Allen
// File: weighted-choice.js

export function weightedChoice(source) {
    let rnd = Math.random();
    let lower = 0.00;
    for (let choice in source) {
        let weight = source[choice]; 
        let upper = lower + weight;
        if (rnd >= lower && rnd < upper) {
            return choice; 
        }
        lower = upper;
    }

    // Never reached 100% and random 
    // number is out of bounds
    return undefined;   
}

The code does the following:

  • exports a weightedChoice function that takes an object as an argument and returns a random item from the array
  • the source objects keys (properties) will represent the choices to be made
  • the property values are the weights and they should add up to 1 (100%)
  • for example: { "A": 0.25, "B": 0.50, "C": 0.25 }
  • the example above has a 25% chance of returning A, 50% for B and 25% for C
  • sets rnd to Math.random() which returns a random number from 0.0 to up to but not including 1.0
  • sets the lower bound of a range to search for a match
  • the for loop loops through each property (choice) of the source object
  • the weight is the value assigned from the value of the current property in the loop
  • the upper bound of the search range is set to lower plus weight
  • if the rnd (random) value is greater than or equal to the lower bound and less than the upper bound it is considered a match and the property (A, B or C) is returned representing the random selection
  • the value of lower is set to upper to setup the next iteration
  • after looping through all the properties, if the values for the object did not make it to 1 (100%) and the random value falls outside every range then undefined is returned

If that was difficult to follow, picture it like this:

  { "A": 0.25, "B": 0.50, "C": 0.25 }

  0.00 -- 0.25 -- 0.50 -- 0.75 -- 1.00
    |   A   |       B       |   C   |
  • On the first iteration through the for loop the range is set to 0.00..0.25
    • if the rnd value is within that range “A” is returned
  • On the second iteration the range is 0.25..0.75
    • if the rnd value is within that range “B” is returned
  • On the final iteration the range is 0.75..1.00
    • if the rnd value is within that range “C” is returned

Step 5. Add a test file​

To test the function you can create a special test module that calls the weightedChoice function x number of times. The function should log the result and give you an estimate of how evenly distributed the results are.

In the example below I will show you how to use the JavaScript reduce method to count the occurrences of each item in the source that ends up in the results.

Based on the results you can infer the approximate distribution of each item in the selection. If the function is working properly you should get a distribution close to what is expected based on the weighted values.

  • Create a new file called test-weighted-choice.js
  • Paste in this code and save the file:
// Author: Mitch Allen
// File: test-weighted-choice.js

import { weightedChoice } from './weighted-choice.js';

function testWeightedChoice(source = {}) {

    console.log('\nSOURCE:');
    console.log(source);

    // define the number of dice rolls
    const LIMIT = 100;

    // create an array filled with random results
    let arr = Array.from({ length: LIMIT }, () => weightedChoice(source));

    // log the generated results
    console.log(arr);

    // count the occurences of each result
    let occurrences = arr.reduce((prev, curr) => (prev[curr] = ++prev[curr] || 1, prev), {});

    // log a summary of the occurences
    console.log('\OCCURRENCES:');
    console.log(occurrences);
}

testWeightedChoice({
    "A": 0.25,
    "B": 0.50,
    "C": 0.25,
});

testWeightedChoice({
    "A": 0.50,
    "B": 0.25,
    "C": 0.25,
});

testWeightedChoice({
    "A": 0.50,
    "B": 0.35,
    "C": 0.10,
    "D": 0.10,
});

testWeightedChoice({
    "#000000": 0.50,
    "#FFFFFF": 0.35,
    "#FF0000": 0.10,
    "#0000FF": 0.10,
});

The code does the following:

  • imports the weightedChoice function
  • defines a function to test the weightedChoice function
  • logs the source object passed to the function
  • defines a constant limit for generating an array of results
  • generates a random array of results
  • logs the array of results
  • uses the JavaScript reduce method to count the occurrences of each item in the results array
  • logs the summary of the occurrences
  • calls the test function with various source objects for testing

Step 6. Run the test function​

To run the test function do the following from the projects folder:

node test-weighted-choice.js

You should see a result similar to this:

SOURCE:
{ A: 0.25, B: 0.5, C: 0.25 }
[
  'B', 'A', 'C', 'B', 'B', 'B', 'C', 'B', 'B', 'A', 'A',
  'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A', 'C', 'C', 'C',
  'B', 'C', 'C', 'A', 'A', 'C', 'A', 'B', 'A', 'C', 'C',
  'C', 'B', 'C', 'C', 'C', 'B', 'C', 'C', 'B', 'B', 'A',
  'C', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'C', 'A', 'C',
  'C', 'C', 'C', 'A', 'A', 'B', 'B', 'C', 'B', 'B', 'B',
  'C', 'B', 'B', 'A', 'C', 'B', 'B', 'A', 'C', 'C', 'A',
  'C', 'C', 'C', 'C', 'A', 'B', 'C', 'B', 'A', 'A', 'B',
  'B', 'A', 'A', 'C', 'B', 'B', 'B', 'A', 'B', 'A', 'B',
  'B'
]
OCCURRENCES:
{ B: 41, A: 24, C: 35 }
  • all but the last line is the array of results
  • the last line is the summary of the occurrences
  • if you run it several times the summary may never show an exact distribution that matches the weights
  • but most runs should result in a somewhat balanced distribution

If you have a low number of runs and a low weights sometimes not all items will be returned. For example you may notice on runs of 100 that some items with a weight of 10% may have no occurrences listed. But then if you run it again, they might.

Step 7. Run the test in a browser​

  • Create a file called index.html in the root of your project
  • Paste in this code and save it:
<html>

<head>
  <title>js-weighted-choice-01</title>
  <link rel="stylesheet" href="./app.css">
</head>

<body>
  <canvas id="canvas" width="300" height="300" />
  <script type="module" src="./app.js">
  </script>
</body>

</html>

The code does the following:

  • defines a header section
  • defines a title to appear in the browser tab
  • loads a stylesheet (app.css) that will need to be created
  • defines a body section
  • defines a canvas element where we will draw a grid to visualize a series of calls to the function
  • loads a script module (app.js) that will need to be created

Step 8. Create a stylesheet​

  • In the root of the project create a file called app.css
  • Paste in the code below and save the file:
canvas {
    padding: 0;
    margin: auto;
    display: block;
    width: 400px;
    height: 400px;
    position: absolute;
    top: 0;
    bottom: 0;
    left: 0;
    right: 0;
}

The code does the following:

  • centers the canvas element in the middle of the screen

Step 9. Create the app file​

  • In the root of the project create a file called app.js
  • Paste in the code below and save the file:
// Author: Mitch Allen
// File: app.js

import { weightedChoice } from './weighted-choice.js';

let canvas = document.getElementById("canvas");
const SCREEN_SIZE = 300;
const DIM = 10;
const CELL_SIZE = SCREEN_SIZE / DIM;
const BORDER = 1.0;
const COLOR_NEON_PINK = "#FF10F0";
const COLOR_2 = "#F0FF10";
const COLOR_3 = "#10F0FF";
const SOURCE = {
    [COLOR_NEON_PINK]: 0.70,
    [COLOR_2]: 0.10,
    [COLOR_3]: 0.10,
    "white": 0.10,
}
// create an array filled with results
const arr = Array.from({ length: DIM * DIM }, () => weightedChoice( SOURCE ));
console.log(arr);
// draw canvas
let ctx = canvas.getContext('2d');
if (ctx) {
    // draw background
    ctx.clearRect(0, 0, SCREEN_SIZE, SCREEN_SIZE);
    ctx.fillStyle = "black";
    ctx.fillRect(0, 0, SCREEN_SIZE, SCREEN_SIZE);
    // draw cells
    let cursor = 0;
    for (let i = 0; i < DIM; i++) {
        for (let j = 0; j < DIM; j++) {
            ctx.fillStyle = arr[cursor++];
            ctx.fillRect(
                i * CELL_SIZE + BORDER,
                j * CELL_SIZE + BORDER,
                CELL_SIZE - BORDER * 2,
                CELL_SIZE - BORDER * 2
            );
        }
    }
}

The code does the following:

  • gets a handle to the canvas element in the HTML
  • defines a series of constants
  • to simplify the code a square will be drawn where width and height are the same constants
  • SCREEN_SIZE is the width and height of the canvas element (it should match the canvas width and height attributes)
  • DIM is the row and columns of the grid to represent each call to the function which will be show in a grid “cell”
  • CELL_SIZE calculates the size of a cell to draw on the screen by dividing the screen size by the number of rows or columns
  • BORDER is the border size to leave empty around each cell
  • COLOR_NEON_PINK is an HTML constant for a base color to fill each some cell with followed by a few additional colors
  • SOURCE is an object made of random colors with weights assigned to them as values
  • an array is filled with random results
  • the length of the result array DIM x DIM is the number of results to fill a DIM x DIM grid (10 x 10 cells = 100 results needed)
  • the array (arr) is logged to the console which you can view in the browser via the debugger / inspector console window
  • a context handle to the canvas object is created for drawing
  • the context is cleared and replaced with a background color
  • a cursor for looping through the array is created
  • inner and outer loops for converting the array to a grid are defined
  • the color in the result array at the current cursor position is used to define the fill color for a cell
  • adjustments are made to draw the cell slightly smaller so it appears to have a border around it

Step 10. Test the project in the Chrome browser​

You have to run the code through a local Web server.

On a Mac you can serve the files from the current folder using this command:

python -m SimpleHTTPServer $PORT || 8000

Leave that command running

Open up the Chrome browser and browse to:

http://localhost:8000/

To see different results, reload the browser window.

Source Code​

Conclusion​

In this article you learned how to:

  • generate a function that returns a random item from a weighted list of choices
  • write a test function to verify the distributed results were near the expected weights
  • how to use the canvas object in a browser to visualize the results

References​

  • Math.random() – [1]