Ruletový výběr je algoritmus, který provádí výběr náhodnéhu prvku s pravděpodobností odpovídající jeho váze, což je libovolné nezáporné číslo. Čím vyšší váha, tím vyšší pravděpodobnost, že bude daný prvek vybrán.

Obecně je tedy vstupem algoritmu množina prvků a zobrazení, které pro každý prvek určí jeho váhu. Váhy nemusí být celočíselné - jediný rozdíl je v tom, že celočíselné váhy se lépe ukazují na příkladu. Hodnoty váhy mohou být teoreticky libovolně veliké, protože se porovnávají pouze samy mezi sebou, avšak implementace mohou nějaká omezení klást - například rozsahem datových typů.

Jak ruletový výběr funguje? Představme si, že máme prvky (A, B, C, D, E, F) s celočíselnými vahami (4, 1, 3, 8, 1, 1). Z těchto údajů můžeme vytvořit následující ruletu, ve které každý prvek zopakujeme právě tolikrát, kolik udává jeho váha. Na pořadí prvků vůbec nezáleží, protože předpokládáme, že každé políčko rulety může být vybráno se stejnou pravděpodobností.

01234567891011121314151617
BADDADCDDAEDCCFDAD

Prvek nyní zvolíme tak, že vybereme náhodné políčko (0 až 17) a vrátíme odpovídající prvek (např. pro náhodné číslo 5 vrátíme prvek D).

Aby se však tento algoritmus lépe implementoval, zkusme ruletu trochu upravit. V nové ruletě políčka uspořádáme tak, aby všechna políčka představující stejné prvky následovala za sebou:

01234567891011121314151617
AAAABCCCDDDDDDDDEF

Z rulety nyní můžeme vypsat rozsahy políček, které jednotlivé prvky zabírají (první políčko číslujeme jako 0):

PrvekPočet políček (váha)Počáteční políčkoKoncové políčkoRozsah políček
A403(0 až 3)
B144(4 až 4)
C357(5 až 7)
D8815(8 až 15)
E11616(16 až 16)
F11717(17 až 17)

Prvek vybereme opět tak, že zvolíme náhodné políčko (0 až 17) a vrátíme prvek, který se na něm nachází (např. pro náhodné číslo 7 vrátíme prvek C). Nyní však nemusíme znát všechna políčka, stačí nám projít tabulku a najít rozsah, do kterého toto náhodně vybrané políčko patří. Jelikož má tabulka pro každý prvek jen jeden řádek, je průchod tabulkou daleko rychlejší než roztáčení rulety, která musí mít právě tolik políček, kolik udává celková váha.

Druhou výhodou tabulky je, že váhy nyní nemusí být celočíselné. Podobného výběru bychom mohli dosáhnout například s touto tabulkou:

PrvekVáhaRozsah políček
A0,4<0 až 0.4)
B0,1<0.4 až 0.5)
C0,3<0.5 až 0.8)
D0,8<0.8 až 1.6)
E0,1<1.6 až 1.7)
F0,1<1.7 až 1.8)

Nyní však musíme vygenerovat náhodné číslo v rozsahu 0 (včetně) až 1,8. Výběr probíhá stejně - opět najdeme odpovídající rozsah a vrátíme prvek, který do něj patří (např. pro náhodné číslo 0,2442 vrátíme prvek A).

Jednoduchá implementace této techniky v jazyce Java se linární asymptotickou složitostí €O(n)€:

package random;

public class RouletteWheelSelection {
    /**
     * Returns a random integer in range (0, weights.length-1), both inclusive.
     * Every integer n is selected with a probability that corresponds to its weight.
     * The weight of integer n is stored in as weights[n].
     * The weights can be an arbitrary numbers.
     * @param weights array of weights for each number (index = number)
     * @return random index or -1 if the input is empty
     */
    public static int randomWeightedInteger(final double[] weights) {
        double rouletteSize = 0;

        for (final double weight : weights) {
            rouletteSize += weight;
        }

        final double randomRoulettePosition = Math.random() * rouletteSize;
        double currentRoulettePosition = 0;

        for (int i = 0; i < weights.length; i++) {
            currentRoulettePosition += weights[i];

            if (currentRoulettePosition >= randomRoulettePosition) {
                return i;
            }
        }

        // if the array is empty
        // (other scenarios cannot end up here)
        return -1;
    }
}

Zdrojový kód Pokrytí testy

Algoritmus lze vylepšit až na logaritmickou složitost €O(\log(n))€ použitím binárního vyhledávání:

package random;

public class RouletteWheelSelectionWithBinarySearch {
    /**
     * Returns a random integer in range (0, weights.length-1), both inclusive.
     * Every integer n is selected with a probability that corresponds to its weight.
     * The weight of integer n is stored in as weights[n].
     * The weights can be an arbitrary numbers.
     * @param weights array of weights for each number (index = number)
     * @return random index or -1 if the input is empty
     */
    public static int randomWeightedInteger(final double[] weights) {
        if (weights.length == 0) {
            return -1;
        }

        final double[] cumulativeWeights = new double[weights.length + 1];
        double cumulativeWeight = 0;

        for (int i = 0; i < weights.length; i++) {
            cumulativeWeights[i] = cumulativeWeight;
            cumulativeWeight += weights[i];
        }

        final double randomRoulettePosition = Math.random() * cumulativeWeight;

        // as the cumulativeWeights array is sorted, we can use binary search
        return binarySearch(cumulativeWeights, randomRoulettePosition);
    }

    private static int binarySearch(final double[] values, final double key) {
        int start = 0;
        int end = values.length - 1;

        while (end - start > 1) {
            final int mid = (start + end) / 2;
            if (values[mid] > key) {
                // go to the left subtree
                end = mid;
            } else {
                // go to the right subtree
                start = mid;
            }
        }

        // we do not need an exact match, just the greatest lower bound
        return start;
    }
}

Zdrojový kód Pokrytí testy

Reference