Longueur maximale de la liste à mélanger au hasard de Python.shuffle?

j'ai une liste que je mélange avec le Python construit dans la fonction shuffle ( random.shuffle )

Toutefois, le Python de référence unis:

noter que pour len(x) , le nombre total de permutations de x est plus grand que 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 peut jamais être générée.

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

30
demandé sur Henrik 2010-06-17 18:48:22

3 réponses

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, noter que "mélanger" une liste peut être compris (conceptuellement) comme générant toutes les permutations possibles des éléments des listes, et de choisir une de ces permutations au hasard.

alors, vous devez vous rappeler que tous les générateurs de nombres aléatoires informatisés autonomes sont en fait " pseudo" aléatoire. C'est-à-dire qu'ils ne sont pas réellement aléatoires, mais s'appuient sur une série de facteurs pour essayer de générer un nombre qui est difficile à deviner dans avancé, ou volontairement reproduit. Parmi ces facteurs est généralement le précédent numéro généré. Ainsi, dans la pratique, si vous utilisez un générateur aléatoire en continu un certain nombre de fois, vous finirez par recommencer la même séquence (c'est la "période" à laquelle la documentation fait référence).

enfin, le docstring sur Lib/random.py (le module aléatoire) dit que "la période [du générateur de nombres aléatoires] est 2**19937-1 ."

donc, étant donné tout cela, si votre liste est telle qu'il y a 2**19937 ou plus de permutations, certaines d'entre elles ne seront jamais obtenues en mélangeant la liste. Vous générez (encore, conceptuellement) toutes les permutations de la liste, puis vous générez un nombre aléatoire x, et vous choisissez la permutation XE. La prochaine fois, vous générez un autre nombre aléatoire y, et choisissez la permutation yth. Et ainsi de suite. Mais, puisqu'il y a plus de permutations que vous obtiendrez des nombres aléatoires (parce que, tout au plus après les nombres générés par 2**19937-1 , vous commencerez à obtenir les mêmes à nouveau), vous commencerez à choisir les mêmes permutations à nouveau.

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

57
répondu rbp 2013-05-11 16:31:06

j'ai écrit ce commentaire dans la source de Python à l'origine, donc peut-être que je peux clarifier ; -)

lorsque le commentaire a été présenté, le générateur de Wichmann-Hill de Python avait 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 grande maintenant, et 2080 est correcte pour la limite supérieure actuelle. Les docs pourraient en dire plus à ce sujet, mais ça serait ennuyeux.

il y a une explication très simple: un PRNG de période P A P états de départ possibles. L'état de départ détermine entièrement la permutation produite. Par conséquent, un PRNG de période P ne peut pas générer plus que des permutations distinctes de P (et c'est une limite supérieure absolue - il peut ne pas être atteint). C'est pourquoi comparer N! P est le calcul correct ici. Et, en effet:

>>> math.factorial(2080) > 2**19937 - 1
False
>>> math.factorial(2081) > 2**19937 - 1
True
17
répondu Tim Peters 2013-09-05 04:53:08

ce qu'ils signifient, c'est que les permutations sur n objets (noté n!) croît ridiculement haut très vite.

en gros 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 possibles de mélanger une liste de 5 éléments.

sur la même documentation de page Python ils donnent 2^19937-1 comme période, qui est 4.quelque chose × 10^6001 ou quelque chose. Basé sur la page Wikipédia sur factoriels, je suppose 2000! devrait être autour de que. (Désolé, je n'ai pas trouvé le chiffre exact.)

donc il y a tellement de permutations possibles que le mélange va prendre qu'il n'y a probablement aucune raison de s'inquiéter de celles qu'il ne va pas.

mais si c'est vraiment un problème (satané client demandant une garantie de hasard peut-être?), vous pouvez également décharger la tâche à un tiers; voir http://www.random.org / for example.

3
répondu Joubarc 2017-03-04 04:04:38