Longueur maximale de la liste à mélanger avec Python random.shuffle?

Question

J'ai une liste que je mélange avec la fonction de lecture aléatoire intégrée de Python ( random.shuffle )

Cependant, la référence Python indique:

Il est à noter que même pour des len(x) , même assez petits, le nombre total de permutations de x est supérieur à la période de la plupart des générateurs de nombres aléatoires; cela implique que la plupart des permutations d'une longue séquence ne peuvent jamais être générées.

Maintenant, je me demande ce que signifie ce "plutôt petit len (x)". 100, 1000, 10000, ...

Answer 1

TL;DR: Il "casse" sur les listes avec plus de 2080 éléments, mais ne vous inquiétez pas trop :)

Réponse complète:

Tout d'abord, vous remarquerez que le "brassage", une liste peut être compris (conceptuellement) que la génération de toutes les permutations possibles des éléments de la liste, et choisir l'une de ces permutations aléatoires.

Ensuite, vous devez vous rappeler que tous les auto-contenue informatisé des générateurs de nombres aléatoires sont en fait des "pseudo-aléatoire". C'est qu'ils ne sont pas réellement aléatoire, mais reposent sur une série de facteurs d'essayer et de générer un nombre qui est difficile à deviner à l'avance, ou à dessein de le reproduire. Parmi ces facteurs est généralement le précédent numéro généré. Donc, dans la pratique, si vous utilisez un générateur de hasard en permanence un certain nombre de fois, vous allez commencer à obtenir la même séquence de tous les plus de nouveau (c'est la "période" que la documentation se réfère).

Enfin, la docstring sur Lib/random.py (le module random) indique que "La période [de l'générateur de nombre aléatoire] est - 2**19937-1."

Donc, compte tenu de tout cela, si votre liste est telle qu'il y a 2**19937 ou plus des permutations, certains de ces ne sera jamais obtenue en mélangeant la liste. Vous avais (encore une fois, sur le plan conceptuel) générer toutes les permutations de la liste, puis générer un nombre aléatoire x, et de choisir le xème permutation. La prochaine fois, vous générez un autre nombre aléatoire y, et de choisir le yth permutation. Et ainsi de suite. Mais, car il y a plus de combinaisons que vous allez obtenir des nombres au hasard (parce que, au plus, après l' 2**19937-1 nombre généré, vous allez commencer à obtenir les mêmes que ceux de nouveau), vous allez commencer à ramasser les mêmes permutations de nouveau.

Donc, vous voyez, ce n'est pas exactement une question de combien de temps votre liste est (mais qui le fait entrer dans l'équation). Aussi, 2**19937-1 est tout à fait un long numéro. Mais, là encore, en fonction de votre brassage besoins, vous devez garder tout cela à l'esprit. Sur un cas simpliste (et avec un rapide calcul), pour une liste sans éléments répétés, 2081 éléments de rendement 2081! permutations, ce qui est plus que 2**19937.

Answer 2

J'ai écrit ce commentaire dans le source Python à l'origine, donc je peux peut-être préciser ;-)

Lorsque le commentaire a été introduit, Python Wichmann-Hill générateur eu une période beaucoup plus courte, et nous ne pouvions même pas générer toutes les permutations d'un jeu de cartes.

La période est astronomiquement plus grands maintenant, et 2080 est correct pour le courant limite supérieure. La documentation pourrait être renforcée pour en dire plus à ce sujet - mais ils auraient terriblement fastidieux.

Il y a une explication très simple: UN GÉNÉRATEUR de période P a P de départ possible unis. L'état de départ filiale détermine la permutation produit. Donc un GÉNÉRATEUR de période P ne peut pas générer plus de P permutations distinctes (et qui est un absolu limite supérieure - il peut ne pas être atteint). C'est pourquoi la comparaison de N! P est le calcul correct ici. Et, en effet:

>>> math.factorial(2080) > 2**19937 - 1
False
>>> math.factorial(2081) > 2**19937 - 1
True

Answer 3

Ce qu'ils veulent dire, c'est que les permutations de n objets (noté n!) pousse ridiculement élevés très rapidement. Fondamentalement, n! = n x n-1 x ... x 1; par exemple 5! = 5 x 4 x 3 x 2 x 1 = 120 ce qui signifie qu'il y a 120 façons possible de mélanger les 5 éléments de la liste.

Sur le même python page de doc ils donnent 2^19937-1 de l'époque, qui est de 4.quelque chose × 10^6001 ou quelque chose. Fondée sur la page de wikipedia sur les factorielles, je suppose 2000! devrait être autour de cela. (désolé, je n'ai pas trouvé le chiffre exact)

Donc, fondamentalement, il ya tellement de nombreuses permutations possibles, le shuffle, va prendre à partir de ce qu'il y a probablement aucune raison de s'inquiéter de ceux qui il ne sera pas.

Mais si c'est vraiment un problème (satanés client qui demande une garantie de hasard peut-être?), vous pourriez également déléguer la tâche à une tierce partie; voir http://www.random.org/ par exemple.