Le cas échéant, quel est le problème avec ce brassage de l'algorithme et comment puis-je savoir?

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 le 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.

  • Les réponses à cette question peut aider: stackoverflow.com/questions/1685339/... Elle avait également être la peine de prendre un coup d'oeil à Knuth l'analyse de Fisher-Yates (voir l'article de wikipédia vous lié pour une citation).
  • Je recommande que vous prenez ce MathOverflow. Inductive preuve qu'il fonctionne comme prévu semble faire bouillir le calcul de la somme d'une ligne. (Mais je suis à peu près certain que c'est correct mais pas garanti arrêter à un moment donné).
  • doublep > je pense aussi que cet algorithme fonctionne. Voir mon post pour une explication détaillée.
  • J'ai pensé infini ralentissement a été considéré comme très mauvais, dans les algorithmes de tri? Aussi, ne serait pas lists:split, lists:droplast et lists:append la mise en œuvre de l'algorithme trivial?