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

51

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

fl00r
źródło
11
to powinna być ta sama formuła uzyskiwania losowych łupów w Diablo :-)
Jalayn
1
@Jalayn: Właściwie pomysł rozwiązania interwału w mojej odpowiedzi poniżej pochodzi z tego, co pamiętam o stołach bojowych w World of Warcraft. :-D
Benjamin Kloster
Zobacz także
BlueRaja - Danny Pflughoeft
Zaimplementowałem kilka prostych ważonych algorytmów losowych . Daj mi znać, jeśli masz pytania.
Leonid Ganeline,

Odpowiedzi:

50

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.

Benjamin Kloster
źródło
2
rozwiązanie interwałowe wydaje się fajne
Jalayn
1
To była moja pierwsza myśl :). Ale co, jeśli mam stół ze 100 owocami, a waga może wynosić około 10 000? Będzie to bardzo duża tablica, a to nie będzie tak wydajne, jak chcę. Chodzi o pierwsze rozwiązanie. Drugie rozwiązanie wygląda dobrze
fl00r
1
Zaimplementowałem ten algorytm w Ruby github.com/fl00r/pickup
fl00r
1
Metoda alias jest sposobem na poradzenie sobie z tym. Jestem szczerze zdziwiona liczbą postów, które powtarzają ten sam kod w kółko, jednocześnie ignorując metodę aliasu . na miłość boską, masz stałą wydajność w czasie!
opa
30

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)

Nieważne
źródło
2
Porównałbym to przed założeniem, że jest to lepsze tylko dlatego, że iteruje się raz. Generowanie tak wielu losowych wartości też nie jest zbyt szybkie.
Jean-Bernard Pellerin,
1
@ Jean-Bernard Pellerin Zrobiłem to, a tak naprawdę jest szybciej na dużych listach. Chyba że użyjesz silnego kryptograficznie losowego generatora (-8
Nevermind
Powinna być zaakceptowana odpowiedź imo. Podoba mi się to bardziej niż podejście „interwał” i „powtarzane wejście”.
Vivin Paliath,
2
Chciałem tylko powiedzieć, że w ciągu ostatnich kilku lat wróciłem do tego wątku 3 lub 4 razy, aby użyć tej metody. Ta metoda wielokrotnie zapewniała odpowiedzi, których potrzebuję wystarczająco szybko do moich celów. Chciałbym móc głosować za odpowiedzią za każdym razem, gdy wrócę, aby z niej skorzystać.
Jim Yarbro,
1
Ładne rozwiązanie, jeśli naprawdę musisz wybrać tylko raz. W przeciwnym razie wykonanie wstępnej pracy nad rozwiązaniem w pierwszej odpowiedzi raz jest znacznie bardziej wydajne.
Deduplicator
22

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 .

Cesarz Orionii
źródło
Dobra uwaga na temat wyszukiwania binarnego
fl00r
Odpowiedź Neverminda nie wymaga dodatkowej przestrzeni, więc jest to O (1), ale dodaje złożoności środowiska wykonawczego poprzez wielokrotne generowanie liczb losowych i ocenę funkcji wagi (która, w zależności od problemu, może być kosztowna).
Benjamin Kloster
1
To, co twierdzisz, że jest „bardziej czytelną wersją” mojego kodu, tak naprawdę nie jest. Twój kod musi wcześniej znać całkowitą sumę wag i sumy zbiorcze; mój nie.
Nevermind
@Benjamin Kloster Mój kod wywołuje funkcję wagi tylko raz na element - nie da się nic lepszego. Ale masz rację co do liczb losowych.
Nevermind
@Nevermind: Wywołujesz go tylko raz na wywołanie funkcji pick, więc jeśli użytkownik wywoła go dwa razy, funkcja wagi jest wywoływana ponownie dla każdego elementu. Oczywiście możesz to buforować, ale nie jesteś już O (1) ze względu na złożoność przestrzeni.
Benjamin Kloster
8

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.

Wybór koła 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ą ).

manlio
źródło
Czy wiesz, jakie jest oryginalne źródło tego obrazu? Chcę go użyć w formie papierowej, ale muszę się upewnić co do atrybucji.
Malcolm MacLeod
@MalcolmMacLeod Przepraszamy, jest używany w wielu artykułach / witrynach GA, ale nie wiem, kto jest autorem.
manlio
0

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
Ramazan POLAT
źródło
2
Programiści jest o koncepcyjnych pytania i oczekuje odpowiedzi, aby wyjaśnić rzeczy. Rzucanie zrzutów kodu zamiast objaśnień przypomina kopiowanie kodu z IDE na tablicę: może wyglądać znajomo, a czasem nawet być zrozumiałe, ale wydaje się dziwne ... po prostu dziwne. Tablica nie ma kompilatora
komnata
Masz rację, skupiłem się na kodzie, więc zapomniałem powiedzieć, jak to działa. Dodam wyjaśnienie, jak to działa.
Ramazan Polat