Weighted Random

Definition

Definition

The Weighted Random Algorithm is a method used to select elements randomly from a collection, with each element having a weighted probability of being chosen. This algorithm is commonly employed in scenarios where certain elements are more likely to be selected than others based on their assigned weights

Explanation

It operates in 3 main phases:

• preprocessing
• selection
• updating cumulative weights (optionally)

During preprocessing, cumulative weights for each element are computed by summing up the weights of all preceding elements in the collection. In the selection phase, a random number within the range of total weight sums is generated, and the algorithm iterates through the collection to find the first element whose cumulative weight surpasses this generated number, which is then returned as the selected element. Optionally, if the weights of elements dynamically change, the algorithm can update cumulative weights to reflect these changes

Guidance

• Preprocessing
  • start with an empty cumulative weight variable
  • traverse the collection
  • for each element, add its weight to the cumulative weight
  • store cumulative weight for each element
• Selection
  • generate a random number between 0 and the total sum of weights
  • initialize a variable to store the cumulative weight
  • traverse the collection
  • for each element, check if the cumulative weight exceeds the generated random number
  • if found, return the element
• Updating cumulative weights (Optional)
  • whenever weights change
  • recalculate cumulative weights following the preprocessing steps

Tips

• ensure that the weights of items accurately reflect their importance or priority
• consider using an efficient data structure to store the items and their weights, such as a dictionary or a tuple

Practice

Practice

weighted_random(collection):
  cum_weights = calculate_cumulative_weights(collection)
  random_num = generate_random_number(0, total_sum(cum_weights))
  return select_element(collection, cum_weights, random_num)

calculate_cumulative_weights(collection):
  cum_weights = []
  cum_weight = 0
  for each element in collection:
    cum_weight += element.weight
    cum_weights.append(cum_weight)
  return cum_weights

select_element(collection, cum_weights, random_num):
  for i from 0 to length(collection) - 1:
    if random_num < cum_weights[i]:
      return collection[i]

Solution

package main

import (
	"math/rand"
)

type WeightedItem struct {
	Item   interface{}
	Weight int
}

func weightedRandom(items []WeightedItem) interface{} {
	totalWeight := 0
	for _, item := range items {
		totalWeight += item.Weight
	}

	randomWeight := rand.Intn(totalWeight)

	for _, item := range items {
		if randomWeight < item.Weight {
			return item.Item
		}
		randomWeight -= item.Weight
	}

	return nil
}

import java.util.*;

class WeightedItem<T> {

  T item;
  int weight;

  WeightedItem(T item, int weight) {
    this.item = item;
    this.weight = weight;
  }
}

public class WeightedRandom {

  public static <T> T weightedRandom(List<WeightedItem<T>> items) {
    int totalWeight = items.stream().mapToInt(item -> item.weight).sum();
    Random random = new Random();
    int randomWeight = random.nextInt(totalWeight);

    for (WeightedItem<T> item : items) {
      if (randomWeight < item.weight) {
        return item.item;
      }
      randomWeight -= item.weight;
    }

    return null;
  }
}

function weightedRandom(items) {
  const totalWeight = items.reduce((acc, item) => acc + item.weight, 0);
  let randomWeight = Math.floor(Math.random() * totalWeight);

  for (const item of items) {
    if (randomWeight < item.weight) {
      return item.item;
    }
    randomWeight -= item.weight;
  }

  return null;
}

import kotlin.random.Random

data class WeightedItem<T>(val item: T, val weight: Int)

fun <T> weightedRandom(items: List<WeightedItem<T>>): T? {
    val totalWeight = items.sumBy { it.weight }
    val randomWeight = Random.nextInt(totalWeight)

    var cumulativeWeight = 0
    for (item in items) {
        cumulativeWeight += item.weight
        if (randomWeight < cumulativeWeight) {
            return item.item
        }
    }
    return null
}

import random

class WeightedItem:
    def __init__(self, item, weight):
        self.item = item
        self.weight = weight

def weighted_random(items):
    total_weight = sum(item.weight for item in items)
    random_weight = random.randint(0, total_weight - 1)

    cumulative_weight = 0
    for item in items:
        cumulative_weight += item.weight
        if random_weight < cumulative_weight:
            return item.item

use rand::Rng;

#[derive(Debug)]
struct WeightedItem<T> {
    item: T,
    weight: u32,
}

fn weighted_random<T>(items: &[WeightedItem<T>]) -> Option<&T> {
    let total_weight: u32 = items.iter().map(|item| item.weight).sum();
    let mut rng = rand::thread_rng();
    let random_weight: u32 = rng.gen_range(0..total_weight);

    let mut cumulative_weight = 0;
    for item in items {
        cumulative_weight += item.weight;
        if random_weight < cumulative_weight {
            return Some(&item.item);
        }
    }
    None
}

class WeightedItem<T> {
  constructor(
    public item: T,
    public weight: number,
  ) {}
}

function weightedRandom<T>(items: WeightedItem<T>[]): T | null {
  const totalWeight = items.reduce((acc, item) => acc + item.weight, 0);
  const randomWeight = Math.floor(Math.random() * totalWeight);

  let cumulativeWeight = 0;
  for (const item of items) {
    cumulativeWeight += item.weight;
    if (randomWeight < cumulativeWeight) {
      return item.item;
    }
  }

  return null;
}