zdobądź ważoną pozycję losową

Mam na przykład ten stół

+ ----------------- +
| owoce | waga |
+ ----------------- +
| jabłko | 4 |
| pomarańczowy | 2 |
| cytryna | 1 |
+ ----------------- +

Muszę zwrócić losowy owoc. Ale jabłko powinno być zbierane 4 razy częściej niż cytryna i 2 razy częściej niż pomarańcza .

W bardziej ogólnym przypadku powinno to być f(weight)często razy.

Jaki jest dobry ogólny algorytm do wdrożenia tego zachowania?

A może na Ruby są gotowe klejnoty? :)

PS
Zaimplementowałem obecny algorytm w Ruby https://github.com/fl00r/pickup

Najprostszym koncepcyjnie rozwiązaniem byłoby utworzenie listy, w której każdy element występuje tyle razy, ile jego waga, więc

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

Następnie użyj dowolnych funkcji, które masz do dyspozycji, aby wybrać losowy element z tej listy (np. Wygeneruj losowy indeks w odpowiednim zakresie). Jest to oczywiście mało wydajne pod względem pamięci i wymaga wag całkowitych.

Kolejne, nieco bardziej skomplikowane podejście wyglądałoby tak:

1. Oblicz skumulowane sumy wag:

   intervals = [4, 6, 7]

   Gdy wskaźnik poniżej 4 oznacza jabłko , 4 do poniżej 6 pomarańczy, a 6 do poniżej 7 cytryny .

2. Wygeneruj liczbę losową nz zakresu od 0do sum(weights).

3. Znajdź ostatni element, którego łączna suma jest wyższa n. Odpowiedni owoc to twój wynik.

To podejście wymaga bardziej skomplikowanego kodu niż pierwszy, ale mniej pamięci i obliczeń oraz obsługuje wagi zmiennoprzecinkowe.

W przypadku każdego algorytmu krok konfiguracji można wykonać raz dla dowolnej liczby losowych wyborów.

Oto algorytm (w języku C #), który może wybierać losowo ważony element z dowolnej sekwencji, iterując go tylko raz:

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. 
}

Jest to oparte na następującym rozumowaniu: wybierzmy pierwszy element naszej sekwencji jako „bieżący wynik”; następnie przy każdej iteracji zachowaj ją lub odrzuć i wybierz nowy element jako bieżący. Możemy obliczyć prawdopodobieństwo, że dany element zostanie wybrany na końcu jako iloczyn wszystkich prawdopodobieństw, że nie zostanie odrzucony w kolejnych krokach, razy razy prawdopodobieństwo, że zostanie on wybrany. Jeśli wykonasz matematykę, zobaczysz, że ten produkt upraszcza (ciężar elementu) / (suma wszystkich ciężarów), a dokładnie tego potrzebujemy!

Ponieważ ta metoda iteruje tylko raz sekwencję wejściową, działa nawet z nieprzyzwoicie dużymi sekwencjami, pod warunkiem, że suma wag pasuje do int(lub możesz wybrać większy typ dla tego licznika)

Już obecne odpowiedzi są dobre i rozwinę je nieco.

Jak zasugerował Benjamin, w tego rodzaju problemach zwykle wykorzystuje się skumulowane kwoty:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

Aby znaleźć element w tej strukturze, możesz użyć czegoś takiego jak fragment kodu Neverminda. Ten fragment kodu C #, którego zwykle używam:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

Teraz interesująca część. Jak skuteczne jest to podejście i jakie jest najbardziej wydajne rozwiązanie? Mój fragment kodu wymaga pamięci O (n) i działa w czasie O (n) . Nie sądzę, że można tego dokonać w przestrzeni mniejszej niż O (n), ale złożoność czasu może być znacznie niższa, w rzeczywistości O (log n) . Sztuką jest użycie wyszukiwania binarnego zamiast zwykłej pętli for.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess >= lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

Jest też historia o aktualizacji wag. W najgorszym przypadku aktualizacja wagi dla jednego elementu powoduje aktualizację sumarycznych sum dla wszystkich elementów, zwiększając złożoność aktualizacji do O (n) . To też można zmniejszyć do O (log n) za pomocą binarnego drzewa indeksowanego .

Jest to prosta implementacja w języku 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

i

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

print select(population, weights)

W algorytmach genetycznych ta procedura wyboru nazywa się selekcją proporcjonalną do sprawności lub selekcją koła ruletki, ponieważ:

• część koła jest przypisana do każdego z możliwych wyborów na podstawie ich wartości masy. Można to osiągnąć, dzieląc wagę selekcji przez całkowitą wagę wszystkich selekcji, tym samym normalizując je do 1.
• następnie losowy wybór jest podobny do tego, w jaki sposób obraca się koło ruletki.

Typowe algorytmy mają złożoność O (N) lub O (log N), ale możesz także wykonać O (1) (np. Wybór koła ruletki poprzez akceptację stochastyczną ).

Ta istota robi dokładnie to, o co prosisz.

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;
    }

możesz użyć tego w ten sposób:

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

Powyższy kod najprawdopodobniej (% 98) zwróci wartość 0, która jest indeksem „jabłka” dla danej tablicy.

Ponadto ten kod testuje metodę podaną powyżej:

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);

Daje to wynik podobny do tego:

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