Qu'est-ce qu'un bon brassage pseudo-aléatoire en un seul passage?

Question

Le shuffle de Fisher-Yates donne un bel algorithme de mélanger un tableau A de la longueur n en un seul passage:

For k = 1 to n
    Pick a random integer j from k to n
    Swap A[k] and A[j]

Après un seul passage dans cet algorithme, les entrées d' A se produire uniformément au hasard.

Une façon courante de bousiller cet algorithme est de faire ce qui suit:

For k = 1 to n
    Pick a random integer j from 1 to n
    Swap A[k] and A[j]

La distribution à partir d'un seul passage à travers cet algorithme est pas uniformément aléatoire, et il y a une belle analyse de ce qu'il est à ce poste: de la distribution Que vous obtenez à partir de ce cassé aléatoire shuffle?

J'ai lu récemment un délicieux article de Diaconis, Fulman et Holmes droit de l'Analyse de Casino Plateau de Brassage des Machines où les auteurs décrivent une machine physique qui ne le lot suivant, shuffle:

For k = 1 to n
    Pick a random integer j from 1 to 10
    Randomly choose to place card k on the top or bottom of stack j

La question de l'adresse des auteurs est de savoir si ou non cela donne une assez aléatoire de la commande après un seul passage. La réponse est résolument pas. Une façon de voir la faille dans ce shuffle est de commencer avec un jeu de cartes qui a n/2 cartes rouges au sommet de l' n/2 cartes noires. La résultante de pont après un seul passage aura tout au plus 10 touffes de cartes rouges! Pour n = 52*6, ce n'est pas vraiment aléatoire. Les auteurs montrent également que la meilleure "deviner la carte suivante" stratégie pour une fois mélangées, en moyenne, deviner correctement 9.5 cartes, alors qu'une stratégie optimale pour un jeu aléatoire sera en moyenne de seulement 4,5 cartes correctement deviné.

Existe-il des autres intéressants à passage unique mélange qui réalisent la quasi-aléatoire et/ou intéressant les distributions? Je suis surtout intéressé par le mélange similaire à ce dernier que le travail avec les lots d'entrées.

Answer 1

Si vous avez un mélangées bureau, dans lequel vous voulez mélanger un lot de nouvelles cartes (et vous savez qu'aucun de ces cartes sont des doublons), alors je pense que ce qui suit est valable.

ForEach card in batch:
    gap = random(deck.size() + 1)  # choose a gap between cards, before first, or after last.
    deck.insertAt(gap,card)

Distribution

La distribution aléatoire uniforme, et la commande de la platine est inchangé, encore en uniforme. Je pense que le résultat doit être uniforme. (Mes stats est trop rouillé pour être sûr).

Le temps

En supposant que insertAt est O(1) O(N) - qui dépend de la implementeation de pont - l'ensemble de la routine est en O(taille de lot) - qui est le meilleur que vous pouvez espérer parce que vous avez à gérer chaque carte.