ページへ戻る
+ Links
印刷
Python/リストをランダムに並べ替える
の編集 ::
NJF Wiki
xpwiki
:
Python
/
リストをランダムに並べ替える
の編集
# x1b6384d の編集
ページ内容:
*よくあるサンプルは使わないのが無難 [#x1b6384d] 「配列 ランダム 並び替え」などでインターネット検索すると次のようなコードを記載したページが上位に現れます。 randomList = [0,1,2] listLen=len(randomList) for i in range(listLen): a = randomList[i] j = random.randrange(0,listLen) randomList[i] = randomList[j] randomList[j] = a つまり、配列から順に要素を選び、次にランダムに要素を一つ選び、この二つを入れ替えていく物です。 これは結果がかなりかたよります。 実際、このアルゴリズムで100,000回ランダムな(のはず)入れ替えを行ってみると、 0,2,1 18651 0,1,2 14885 2,1,0 14889 1,2,0 18359 2,0,1 14742 1,0,2 18474 となり、明らかに14800ぐらいのものと、18500ぐらいのものに二分されました。 これは[[こちらの記事:http://nmi.jp/archives/541]]で指摘されているように、アルゴリズムの構造的な欠陥です。 たとえば3つのものの並べ替えの結果は3!=6通りですが、上のアルゴリズムでは3回3つの要素をランダムに入れ替えるので、並び替えの方法の数は3*3*3=27通りです。 27は6で割り切れませんから、かならず上のアルゴリズムはそれぞれの結果に対して、どれかが多く、どれかが少なく並び替え方を割り振りを行って並べ替えています。(詳しくは[[上記記事:http://nmi.jp/archives/541]]にあります。) 今は長さ3の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。 よって、プログラマの意図しない結果がもたらされる可能性があり、なるべく使うべきではありません。 pythonにはrandom.shuffleがあるのですから、わざわざ手間をかけてバグとなりかねない物を入れるより、素直にこれを使いましょう。 random.shuffleで同じように100,000回実行してみると結果は、 0,2,1 16597 0,1,2 16750 2,1,0 16986 1,2,0 16579 2,0,1 16564 1,0,2 16524 といったものになり、均等に並び替えられていることが分かります。
編集の要約:
Q & A 認証:
ページ更新時は次の質問にお答えください。(プレビュー時は必要ありません)
Q:
日本の首都は?(漢字で)
A:
お名前:
タイムスタンプを変更しない
テキスト整形のルールを表示する