Débuter avec le hasard

Installation ou configuration

Instructions détaillées sur la configuration ou l’installation aléatoire.

Mélange Fisher-Yates

Aussi connu sous le nom de mélange de Knuth et de mélange de Durstenfeld-Fisher-Yates. Ce mélange prend un tableau de n éléments et le mélange. L’algorithme est vraiment aléatoire dans la mesure où, après brassage, chaque permutation du tableau est également probable.

En Java :

public static void shuffle(E[] deck) {

    //From the end, swap each card with a random card from the unswapped portion.
    for(int i = deck.length - 1; i > 0; i--)
    {
        //Pick an element from [0,i], inclusive.
        int chosenCard = (int) (Math.random() * (i + 1));

        E temp = deck[i];
        deck[i] = deck[chosenCard];
        deck[chosenCard] = temp;
    }
}

Attention : il faut que l’élément de remplacement vienne de [0,i] inclus et non de [0,i) exclusif : Sinon, les permutations du tableau où les éléments restent en place sont impossibles, ce qui n’est pas vraiment aléatoire.

En supposant que les nombres aléatoires prennent O(1) pour être générés, l’algorithme fonctionne sur place et prend O(n) dans le temps et l’espace. Un tableau ainsi mélangé peut être utilisé pour récupérer des éléments non répétitifs en O(1) temps amorti par élément.

E[] deck;
int drawIndex;

//Elements are taken from an index that advances.
public E drawUniqueCard()
{
    //Once all cards have been drawn, reshuffle the deck and draw from the top.
    if(drawIndex == deck.length)
    {
        shuffle(deck);
        drawIndex = 0;
    }
    //Pull the next card off the deck.
    return deck[drawIndex++];
}