Quel est le problème, le cas échéant, avec cet algorithme de réorganisation et comment puis-je savoir?

Question

Tout comme arrière-plan, je suis conscient de la de Fisher-Yates parfait shuffle. C'est un grand shuffle avec ses O(n) la complexité et de la garantie de l'homogénéité et je serais un idiot de ne pas l'utiliser ... dans un environnement qui permet en place des mises à jour de tableaux (dans la plupart, si pas tous, impératif environnements de programmation).

Malheureusement, la programmation fonctionnelle du monde ne vous donne pas accès à mutable état.

En raison de Fisher-Yates, cependant, il n'y a pas beaucoup de littérature que je peux trouver sur la façon de concevoir un réarrangement de l'algorithme. Quelques lieux qui adresse à tous les faire brièvement avant de dire, en effet, "alors, voici de Fisher-Yates qui est le brassage que vous devez savoir". J'ai dû, en fin de compte, de venir avec ma propre solution.

La solution je suis venu avec les œuvres de ce genre de lecture aléatoire de toutes les listes de données:

• Si la liste est vide, retourner l'ensemble vide.
• Si la liste contient un seul élément, le retour de ce seul élément.
• Si la liste est non-vide, de la partition de la liste avec un générateur de nombre aléatoire et d'appliquer l'algorithme récursivement à chaque partition, en rassemblant les résultats.

En Erlang code il ressemble à quelque chose comme ceci:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(Si cela ressemble à un dérangé tri rapide pour vous, eh bien, qu'est ce que c'est, en gros.)

Alors, voici mon problème: la même situation qui rend la recherche de brassage des algorithmes qui ne sont pas de Fisher-Yates difficile de trouver des outils pour analyser un réarrangement de l'algorithme tout aussi difficile. Il y a beaucoup de littérature que je peux trouver sur l'analyse de PRNGs pour l'uniformité, de la périodicité, etc. mais pas beaucoup d'informations là-bas sur la façon d'analyser un shuffle. (En effet, certaines des informations que je trouve sur l'analyse de mélange est tout simplement faux -- facilement trompés par de simples techniques.)

Donc ma question est: comment dois-je analyser mon brassage de l'algorithme (en supposant que l' random:uniform() appeler, il est à la tâche de générer winrar nombres aléatoires avec de bonnes caractéristiques)? Ce mathématiques sont les outils à ma disposition pour juger si oui ou non, de dire, de 100 000 passages de la shuffler sur une liste d'entiers allant de 1..100 m'a donné, de manière plausible, bon brassage des résultats? J'ai fait quelques tests de mon propre (en comparant les augmentations diminutions dans le mélange, par exemple), mais j'aimerais savoir un peu plus.

Et si il n'y a aucune indication dans la lecture aléatoire de l'algorithme lui-même qui serait apprécié aussi.

Answer 1

Remarque générale

Mon approche personnelle au sujet de l'exactitude de la probabilité à l'aide d'algorithmes: si vous savez comment prouver que c'est correct, alors il est probablement correct; si vous ne le faites pas, il est certainement erroné.

Autrement dit, il est généralement inutile d'essayer d'analyser chaque algorithme que vous pourriez en venir à: vous avez à garder à la recherche d'un algorithme jusqu'à ce que vous trouviez celui que vous pouvez prouver corriger.

L'analyse d'un algorithme aléatoire par le calcul de la distribution

Je connais un moyen de "automatiquement" analyser un shuffle (ou plus généralement un hasard-à l'aide de l'algorithme) qui est plus forte que la simple "jeter beaucoup de tests et de vérifier l'uniformité". Vous pouvez mécaniquement calculer la distribution associée à chaque entrée de votre algorithme.

L'idée générale est qu'un hasard-à l'aide de l'algorithme explore une partie d'un monde de possibilités. Chaque fois que votre algorithme demande pour un élément choisi au hasard dans un ensemble ({true, false} lors de la rotation d'une pièce de monnaie), il y a deux résultats possibles pour votre algorithme, et l'un d'eux est choisi. Vous pouvez changer votre algorithme de sorte que, au lieu de retourner un des résultats possibles, il explore toutes les solutions en parallèle et retourner tous les résultats possibles avec les distributions.

En général, qui serait à réécrire votre algorithme en profondeur. Si votre langue prend en charge délimité par des continuations, vous n'avez pas, vous pouvez en œuvre que "l'exploration de tous les résultats possibles" à l'intérieur de la fonction demandant un élément aléatoire (l'idée est que le générateur aléatoire, au lieu de retourner un résultat, la capture de la poursuite associé à votre programme et l'exécuter avec tous les différents résultats). Pour un exemple de cette approche, voir oleg est HANSEI

Un intermédiaire, et probablement moins arcanes, la solution est de représenter ce "monde de possibles" comme une monade, et d'utiliser un langage comme Haskell avec des installations pour monadique de programmation.
Voici un exemple d'implémentation d'une variant1 de votre algorithme, en Haskell, à l'aide de la probabilité de l'errance de la probabilité de package :

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

Vous pouvez l'exécuter pour une entrée donnée, et obtenir la sortie de la distribution :

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

Vous pouvez voir que cet algorithme est uniforme avec des entrées de taille 2, mais non uniforme sur les entrées de taille 3.
La différence avec le test est une approche que nous pouvons avoir de certitude absolue en un nombre fini d'étapes : il peut être assez grande, comme il s'élève à une exploration exhaustive de l'univers de possibles, mais généralement plus petit que 2^N, comme leurs sont factorisations des résultats similaires), mais si elle renvoie une distribution non uniforme que nous savons pour sûr que l'algorithme est faux. Bien sûr, si elle retourne une distribution uniforme pour [1..N] et 1 <= N <= 100, vous ne connaissez que votre algorithme est uniforme jusqu'à des listes de taille 100, il peut toujours se tromper.

1: cet algorithme est une variante de votre Erlang est mise en œuvre, en raison de la spécificité de pivot de la manipulation. Si je n'utilise pas de pivot, comme dans votre cas, la taille de saisie n'est pas diminuer à chaque étape de plus : l'algorithme de considérer le cas ont été toutes les entrées sont dans la liste de gauche (ou à droite de la liste), et de se perdre dans une boucle infinie. C'est une faiblesse de la probabilité de l'errance de mise en œuvre (si un algorithme a une probabilité de 0 de non-résiliation, la répartition de calcul peut toujours s'écarter), que je ne sais pas encore comment les corriger.

Tri à base de mélange

Voici un algorithme simple qui j'ai confiance, j'ai pu prouver correct:

1. Choisissez une clé aléatoire pour chaque élément dans votre collection.
2. Si les touches ne sont pas tous distincts, redémarrez à partir de l'étape 1.
3. Trier la collection par ces clés aléatoires.

Vous pouvez omettre l'étape 2, si vous connaissez la probabilité de collision (deux nombres aléatoires cueillis sont égaux) est suffisamment faible, mais, sans elle, l'aléatoire n'est pas parfaitement uniforme.

Si vous chercher vos clés dans [1..N], où N est la longueur de votre collection, vous aurez beaucoup de collisions (problème d'Anniversaire). Si vous choisissez votre clé comme un entier de 32 bits, la probabilité d'un conflit est faible dans la pratique, mais toujours sous réserve de l'anniversaire de problème.

Si vous utilisez l'infini (paresseusement évalué) des chaînes de bits que les clés, plutôt que de longueur finie clés, la probabilité de collision devient 0, et la vérification de la distinction n'est plus nessisary.

Voici un shuffle mise en œuvre en OCaml, à l'aide de paresseux nombres réels comme infini des chaînes de bits:

type 'a stream = Cons of 'a * 'a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
    compare_real a' b'

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

Il y a d'autres approches de la "pure brassage". Une belle est apfelmus de mergesort à base de solution.

Algorithmique considérations: la complexité de l'algorithme précédent dépend de la probabilité que toutes les clés sont distinctes. Si vous choisissez comme des nombres entiers de 32 bits, vous avez une ~4 milliards de probabilité qu'une touche particulière entre en collision avec une autre clé. Tri par ces touches est O(n log n), à condition de choisir un nombre aléatoire est O(1).

Si vous infini des chaînes de bits, vous ne jamais avoir à redémarrer la cueillette, mais la complexité est alors liée à "la façon dont beaucoup d'éléments de la les flux sont évalués sur la base de la moyenne". Je conjecture qu'il est O(log n) en moyenne (donc encore un O(n log n) au total), mais n'ont aucune preuve.

... et je pense que votre algorithme fonctionne

Après plus de réflexion, je pense (comme douplep), que votre mise en œuvre est correcte. Ici c'est une simple explication.

Chaque élément de votre liste est testé par plusieurs random:uniform() < 0.5 tests. À un élément, vous pouvez associer la liste des résultats de ces tests, comme une liste de booléens ou {0, 1}. Au début de l'algorithme, vous ne connaissez pas la liste associée à l'une de ces nombre. Après la première partition appel, vous savez que le premier élément de chaque liste, etc. Lors de votre algorithme retourne la liste des tests sont parfaitement connues et les éléments sont triés en fonction de ces listes (triés dans l'ordre lexicographique, ou considérées comme des représentations binaires des nombres réels).

Donc, votre algorithme est équivalent à trier par infini bitstring clés. L'action de partitionnement de la liste, qui rappelle de quicksort de la partition sur un pivot de l'élément, est en fait une manière de séparer, pour une position donnée dans la bitstring, les éléments d'évaluation 0 contre les éléments avec l'évaluation, 1.

Le tri est uniforme, parce que les chaînes de bits sont tous différents. En effet, les deux éléments avec les nombres réels de l'égalité jusqu'à l' n-ème bit sont sur le même côté de la partition qui se produisent durant un appel récursif shuffle appel de profondeur n. L'algorithme se termine seulement quand tous la liste résultant de partitions sont vides ou des singletons : tous les éléments ont été séparés par au moins un essai, et ont donc un net binaire en décimal.

Probabiliste de la résiliation

D'un point subtil sur votre algorithme (ou ma équivalent de tri de la méthode), c'est que la résiliation condition est probabiliste. De Fisher-Yates toujours se terminer après un nombre connu de mesures (le nombre d'éléments dans le tableau). Avec votre algorithme, la résiliation dépend de la sortie du générateur de nombre aléatoire.

Il y a des sorties possibles qui permettraient de faire de votre algorithme divergent, pas fin. Par exemple, si le nombre aléatoire de générer toujours la sortie 0chaque partition appel renvoie la liste d'entrée inchangé, sur lequel vous récursive appelez le shuffle : vous aurez en boucle indéfiniment.

Cependant, ce n'est pas un problème si vous êtes certain que votre générateur de nombre aléatoire est juste : il ne triche pas, et toujours de retour indépendantes uniformément distribués résultats. Dans ce cas, la probabilité que le test random:uniform() < 0.5 retourne toujours true (ou false) est exactement 0 :

• la probabilité que les N premiers appels de retour true est de 2^{-N}
• la probabilité que tous les appels de retour true est la probabilité de l'intersection infinie, pour tout N, de l'événement que le premier N appels de retour 0; c'est l'infimum limite1 de la 2^{-N}, qui est 0

1: pour les détails mathématiques, voir http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

Plus généralement, l'algorithme ne prend pas fin si et seulement si certains éléments sont associés à la même boolean flux. Cela signifie qu'au moins deux éléments ont la même boolean flux. Mais la probabilité pour que deux aléatoire boolean flux sont égaux à 0 : la probabilité que les chiffres à la position K sont égaux est de 1/2, donc la probabilité que les N premiers chiffres sont égaux à 2^{-N}, et la même analyse s'applique.

Donc, vous savez que votre algorithme se termine avec la probabilité 1. C'est un peu plus faible garantie que le de Fisher-Yates algorith, qui toujours mettre fin. En particulier, vous êtes vulnérable à une attaque d'un mal adversaire contrôle de votre générateur de nombre aléatoire.

Avec plus de la théorie des probabilités, vous pouvez également calculer la distribution de temps de fonctionnement de votre algorithme pour une entrée donnée de la longueur. C'est au-delà de mes compétences techniques, mais je suppose que c'est une bonne chose : je suppose que vous avez seulement besoin de regarder en O(log N) premiers chiffres, en moyenne, pour vérifier que tous les N paresseux, les flux sont différents, et que la probabilité beaucoup plus élevée de l'exécution de la diminution des temps de façon exponentielle.

Answer 2

Votre algorithme est une tri-fonction de lecture aléatoire, tel que discuté dans l'article de Wikipedia.

En règle générale, la complexité de calcul de tri à base de mélange est le même que le sous-jacent algorithme de tri (par exemple, O(n log n) en moyenne, O(n2) le pire des cas pour un tri rapide-fonction de lecture aléatoire), et que la répartition n'est pas parfaitement uniforme, il devrait approche uniforme assez proche pour la plupart des fins pratiques.

Oleg Kiselyov prévoit l'article suivant / discussion:

• Prouvable parfait aléatoire de brassage et de la pureté de ses implémentations fonctionnelles

qui couvre les limitations de sorte à base de mélange dans le détail, et offre également deux adaptations du procédé Fischer–Yates stratégie: un naïf O(n2), et un binaire-tree-based O(n log n).

Malheureusement, la programmation fonctionnelle du monde ne vous donne pas accès à mutable état.

C'est un mythe: la programmation fonctionnelle, évite les effets secondaires, mais prend en charge mutable état parfaitement bien, sans avoir d'effets secondaires.

Dans ce cas particulier, vous pouvez utiliser Haskell mutable tableaux pour mettre en œuvre le procédé Fischer–Yates algorithme tel que décrit dans ce tutoriel:

• Haskell Brassage (Brett Hall)

Addendum

La fondation particulière de votre shuffle de tri est en fait une infinie-clé de tri radix: gasche, chacun partition correspond à un groupement de chiffres.

Le principal inconvénient de cette est le même que toute autre infini-clé de tri aléatoire: il n'y a pas de résiliation de la garantie. Bien que la probabilité de résiliation augmente à mesure que la comparaison des produits, il n'y a jamais de limite: le pire des cas, la complexité est O(∞).

Answer 3

J'ai été faire quelques choses de similaire à ça il y a longtemps, et, en particulier, vous pourriez être intéressé en Clojure de vecteurs, qui sont fonctionnels et immuable, mais toujours avec O(1) random access/caractéristiques de mise à jour. Ces deux gist avoir plusieurs implémentations de "prendre la N des éléments au hasard à partir de ce M la taille de la liste"; au moins l'un d'eux se transforme en une fonctionnelle de la mise en œuvre de Fisher-Yates si vous le permettez N=M.

https://gist.github.com/805546

https://gist.github.com/805747