Pythonに組み込まれているシャッフル関数でシャッフルするリストがあります（random.shuffle）
ただし、Pythonリファレンスには次のように記載されています。
len(x)がかなり小さい場合でも、xの順列の総数は、ほとんどの乱数ジェネレーターの周期よりも大きいことに注意してください。これは、長いシーケンスのほとんどの順列を生成できないことを意味します。
さて、この「やや小さいlen（x）」とはどういう意味なのかしら。100、1000、10000、..。
6173 次
3 に答える
67
TL; DR：2080を超える要素を含むリストでは「壊れます」が、あまり心配する必要はありません:)
完全な答え：
まず、リストの「シャッフル」は、リストの要素のすべての可能な順列を生成し、これらの順列の1つをランダムに選択することとして（概念的に）理解できることに注意してください。
次に、すべての自己完結型のコンピューター化された乱数ジェネレーターは実際には「疑似」ランダムであることを覚えておく必要があります。つまり、それらは実際にはランダムではありませんが、一連の要因に依存して、高度に推測したり、意図的に再現したりするのが難しい数を生成しようとします。これらの要因の中には、通常、以前に生成された数があります。したがって、実際には、ランダムジェネレーターを特定の回数継続して使用すると、最終的に同じシーケンスを最初からやり直すことになります（これはドキュメントで参照されている「期間」です）。
最後に、Lib / random.py（乱数モジュール）のdocstringには、「[乱数ジェネレーターの]期間はです」と書かれてい2**19937-1ます。
したがって、これらすべてを考慮すると、リストに2**19937順列が存在するかそれ以上である場合、リストをシャッフルしても、これらの一部は取得されません。（ここでも、概念的に）リストのすべての順列を生成してから、乱数xを生成し、x番目の順列を選択します。次回は、別の乱数yを生成し、y番目の順列を選択します。等々。ただし、乱数を取得するよりも多くの順列があるため（多くても、2**19937-1生成された数の後に同じ番号を取得し始めるため）、同じ順列を再度選択し始めます。
つまり、リストの長さの問題ではありません（ただし、それは方程式に含まれます）。また、2**19937-1かなり長い数です。ただし、それでも、シャッフルのニーズによっては、これらすべてを念頭に置く必要があります。単純なケース（および迅速な計算）では、要素が繰り返されていないリストの場合、2081要素は。2081!以上の順列を生成し2**19937ます。
于 2010-06-17T15:15:31.840 に答える
21
私はもともとPythonソースにそのコメントを書いたので、多分私は明確にすることができます;-)
コメントが導入されたとき、PythonのWichmann-Hillジェネレーターの期間ははるかに短く、トランプのデッキのすべての順列を生成することさえできませんでした。
周期は現在天文学的に大きくなっており、2080は現在の上限に対して正しいです。ドキュメントはそれについてもっと言うために強化されるかもしれません-しかし、彼らはひどく退屈になるでしょう。
非常に簡単な説明があります。期間PのPRNGには、P個の可能な開始状態があります。開始状態は、生成される順列を完全に決定します。したがって、期間PのPRNGは、Pを超える個別の順列を生成することはできません（これは絶対的な上限です。達成されない場合があります）。そのため、Nを比較します。ここでの正しい計算はPです。本当に：
>>> math.factorial(2080) > 2**19937 - 1
False
>>> math.factorial(2081) > 2**19937 - 1
True
于 2013-09-05T04:53:08.997 に答える
4
それらが意味するのは、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.something×10^6001か何かです。階乗に関するウィキペディアのページに基づくと、2000年だと思います。その周りにあるはずです。（申し訳ありませんが、正確な数字は見つかりませんでした。）
したがって、基本的に、シャッフルが取得する可能性のある順列は非常に多いため、そうでないものについて心配する本当の理由はおそらくありません。
しかし、それが本当に問題である場合（おそらくランダム性の保証を求めている厄介な顧客ですか？）、タスクをサードパーティにオフロードすることもできます。たとえば、http：//www.random.org/を参照してください。
于 2010-06-17T15:09:52.703 に答える