5

random.shuffleのPythonドキュメントから、リストを取得し、その要素が次の場合に順序をランダム化します。

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

制限は乱数ジェネレーターに依存しているように見えるので、これはどの言語にも当てはまりますか？任意の長さのリストの可能な順列を生成できる関数を作成することは可能ですか？

4

2 に答える 2

5

http://mail.python.org/pipermail/python-ideas/2009-March/003670.htmlを参照してください。問題が発生し始める正確な長さはPRNGによって異なりますが、基本的な問題は常に当てはまります。

@TryPyPyがリンクしている前の質問もPythonに焦点を当てていますが、受け入れられた回答は、なぜそれが常に発生するのかを非常によく説明しています。言い換えると、このように機能するナイーブなシャッフルアルゴリズムを想像できます。

  1. p入力のすべての可能な順列のリストを生成します。
  2. xPRNGから乱数を取得します。
  3. シャッフルされたリストはp[x]

PRNGが生成できるpすべての可能なリストよりも長い場合、順列の一部に到達できません。x

ファンシーシャッフルアルゴリズムは、基本的に、1つを除くすべてを破棄する前にすべての可能な順列を生成する必要なしにこれを行う方法であるため、これを回避する唯一の方法は、真のランダム性のソースを持つことです。

于 2012-05-19T04:04:11.900 に答える
2

はい、可能です。random.SystemRandomすべての決定に使用する順列ジェネレーターを作成できます。

これの欠点は、オペレーティングシステムが使用するエントロピーを収集している間、プログラムを任意の時間停止しなければならない可能性があることです。

于 2012-05-19T03:59:30.963 に答える