ottiene oggetto casuale ponderato

La soluzione concettualmente più semplice sarebbe quella di creare una lista in cui ogni elemento si presenti tante volte quanto il suo peso, quindi

fruits = [apple, apple, apple, apple, orange, orange, lemon]

Quindi usa tutte le funzioni che hai a disposizione per scegliere un elemento casuale da quella lista (ad es. genera un indice casuale nell'intervallo corretto). Questo naturalmente non è molto efficiente in termini di memoria e richiede pesi interi.

Un altro approccio leggermente più complicato sarebbe simile a questo:

1. Calcola le somme cumulative dei pesi:

   intervals = [4, 6, 7]
   

   Dove un indice inferiore a 4 rappresenta un mela , da 4 a meno di 6 un arancione e da 6 a un di sotto di 7 a limone .

2. Genera un numero casuale n nell'intervallo di 0 in sum(weights) .

3. Trova l'ultimo elemento la cui somma cumulativa è superiore a n . Il frutto corrispondente è il tuo risultato.

Questo approccio richiede un codice più complicato rispetto al primo, ma meno memoria e calcolo e supporta i pesi a virgola mobile.

Per entrambi gli algoritmi, la fase di impostazione può essere eseguita una sola volta per un numero arbitrario di selezioni casuali.

Ecco un algoritmo (in C #) in grado di selezionare elementi pesati casuali da qualsiasi sequenza, eseguendo solo un iterazione una volta sola:

public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
{
    int totalWeight = 0; // this stores sum of weights of all elements before current
    T selected = default(T); // currently selected element
    foreach (var data in enumerable)
    {
        int weight = weightFunc(data); // weight of current element
        int r = Random.Next(totalWeight + weight); // random value
        if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
            selected = data; // it is the probability of discarding last selected element and selecting current one instead
        totalWeight += weight; // increase weight sum
    }

    return selected; // when iterations end, selected is some element of sequence. 
}

Questo è basato sul seguente ragionamento: selezioniamo il primo elemento della nostra sequenza come "risultato corrente"; quindi, a ogni iterazione, mantienilo o scartalo e scegli il nuovo elemento come corrente. Possiamo calcolare la probabilità che ogni dato elemento sia selezionato alla fine come un prodotto di tutte le probabilità che non non venga scartato nei passaggi successivi, tempi che probabilmente saranno selezionati in primo luogo . Se fai i calcoli, vedresti che questo prodotto si semplifica a (peso dell'elemento) / (somma di tutti i pesi), che è esattamente ciò di cui abbiamo bisogno!

Poiché questo metodo esegue una sola volta la sequenza di input sulla sequenza di input, funziona anche con sequenze oscenamente grandi, a condizione che la somma dei pesi si adatti a un int (oppure puoi scegliere un tipo più grande per questo contatore)

Questa è una semplice implementazione Python:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    slot = random()
    for (i, element) in enumerate(container):
        if slot <= probs[i]:
            break

    return element

e

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

Negli algoritmi genetici questa procedura di selezione è chiamata Selezione proporzionale del fitness o Selezione rotellina della roulette dal:

• una proporzione della ruota viene assegnata a ciascuna delle possibili selezioni in base al loro valore di peso. Questo può essere ottenuto dividendo il peso di una selezione per il peso totale di tutte le selezioni, quindi normalizzandole a 1.
• quindi viene effettuata una selezione casuale simile a come viene ruotata la ruota della roulette.

GlialgoritmitipicihannocomplessitàO(N)oO(logN)mapuoianchefareO(1)(es. Roulette- selezione delle ruote tramite accettazione stocastica ).

Questo elenco sta facendo esattamente quello che stai chiedendo.

public static Random random = new Random(DateTime.Now.Millisecond);
public int chooseWithChance(params int[] args)
    {
        /*
         * This method takes number of chances and randomly chooses
         * one of them considering their chance to be choosen.    
         * e.g. 
         *   chooseWithChance(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

        for (int i = 0; i < argCount; i++) {
            sumOfChances += args[i];
        }

        double randomDouble = random.NextDouble() * sumOfChances;

        while (sumOfChances > randomDouble)
        {
            sumOfChances -= args[argCount -1];
            argCount--;
        }

        return argCount-1;
    }

puoi usarlo in questo modo:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(98,1,1);
Console.WriteLine(fruits[choosenOne]);

Il codice sopra riportato molto probabilmente (% 98) restituisce 0 che è indice per 'apple' per l'array specificato.

Inoltre, questo codice verifica il metodo fornito sopra:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

Fornisce un risultato simile a questo:

Start...
Head count:52
Tails count:48