Python random.shuffleでシャッフルするリストの最大の長さ？

Question

シャッフル関数に組み込まれたPythonでシャッフルするリストがあります（random.shuffle)

ただし、Pythonリファレンスは次のとおりです。

かなり小さいことに注意してください len(x), 、xの順列の総数は、ほとんどの乱数ジェネレーターの期間よりも大きい。これは、長いシーケンスのほとんどの順列を生成できないことを意味します。

今、私はこの「むしろ小さなレン（x）」が何を意味するのだろうか。 100、1000、10000、...

Answer 1

tl; dr：2080を超える要素を含むリストに「壊れる」が、あまり心配しないでください:)

完全な答え：

まず、リストを「シャッフル」することは、リストの要素のすべての可能な順列を生成し、これらの順列の1つをランダムに選択することとして（概念的に）理解できることに注意してください。

次に、すべての自己完結型のコンピューター化された乱数ジェネレーターは、実際には「擬似」ランダムであることを覚えておく必要があります。つまり、実際にはランダムではありませんが、一連の要因に依存して、高度で推測するのが難しい、または意図的に再現される数字を生成しようとします。これらの要因の中には、通常、以前の生成された数があります。したがって、実際には、ランダムジェネレーターを一定数の回数を継続的に使用する場合、最終的に同じシーケンスを再び取得し始めます（これはドキュメントが指す「期間」です）。

最後に、lib/random.py（ランダムモジュール）のdocstringは、「[乱数ジェネレーターの]期間は 2**19937-1."

だから、それをすべて考えると、あなたのリストがあるなら、 2**19937 またはより多くの順列、これらのいくつかは、リストをシャッフルすることによって決して得られません。再び（概念的に）リストのすべての順列を生成し、乱数Xを生成し、Xth順列を選択します。次回は、別の乱数yを生成し、yth順列を選択します。等々。しかし、乱数が得られるよりも多くの順列があるので（せいぜい後に 2**19937-1 生成された数字は、同じものを再び取得し始めます）、同じ順列を再び選択し始めます。

ですから、あなたのリストがどれくらいの長さであるかという問題ではありません（ただし、それは方程式に入ります）。また、 2**19937-1 かなり長い数です。しかし、それでも、シャッフルのニーズに応じて、そのすべてを念頭に置いてください。単純なケース（およびクイック計算を使用）では、繰り返される要素のないリストの場合、2081の要素が得られます 2081! 順列、それはそれ以上です 2**19937.

Answer 2

私はもともとPythonソースにそのコメントを書いたので、多分私は明確にすることができます;-)

コメントが導入されたとき、PythonのWichmann-Hillジェネレーターの期間ははるかに短く、カードのデッキのすべての順列を生成することさえできませんでした。

現在、期間は天文学的に大きく、2080は現在の上限に合っています。ドキュメントはそれについてもっと言うために強化される可能性があります - しかし、それらはひどく退屈になるでしょう。

非常に簡単な説明があります：Period PのPRNGには、Pの可能性のある状態があります。開始状態は、生成された順列を完全に決定します。したがって、周期PのPRNGは、P以下の異なる順列を生成することはできません（そして、それは絶対的な上限です - それは達成されないかもしれません）。それがNを比較する理由です！ Pへはここで正しい計算です。本当に：

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

Answer 3

それらが意味するのは、nオブジェクトの順列（N！）の順列は非常に速くばかげて成長することです。

基本的にn！ = nx n-1 x ... x 1;たとえば、5！ = 5 x 4 x 3 x 2 x 1 = 120つまり、5項目リストをシャッフルする方法が120の可能性があります。

同じPythonページのドキュメントで、彼らは期間として2^19937-1、つまり4.何か×10^6001か何かを与えます。要因のウィキペディアページに基づいて、2000年だと思います！その周りにあるはずです。 （申し訳ありませんが、正確な数字が見つかりませんでした。）

したがって、基本的には、シャッフルがとる可能性のある順列が非常に多くあり、おそらくそれがそうでないことを心配する本当の理由はないでしょう。

しかし、それが本当に問題である場合（おそらくランダム性の保証を求めている厄介な顧客？）、タスクをサードパーティにオフロードすることもできます。見る http://www.random.org/ 例えば。