2

シャッフルされたカードのデッキを生成するメソッドを書くとしましょう。非常に簡単にするために、スートを無視すると、52 枚のカードがあります。

1 つのアルゴリズムは次のようになります。

  • 最初の要素に 1、2 番目の要素に 2 というように、52 要素の配列を設定します。
  • X 回反復する for ループを作成し、反復ごとにランダムに 2 枚のカードを選んで交換します。
  • X が大きいほど、シャッフルはランダム化されます。

別のアルゴリズム:

  • 前のように配列にデータを入力します。
  • 26 回反復する for ループを作成し、反復ごとに 2 つの乱数を選択し、これらの 2 つの数値を、新たに選択した数値を格納する別の 52 要素配列の連続する先頭に配置します。
  • 各反復で、新しい配列に追加された元の配列から 2 枚のカードを削除します。

シャッフルにはより良いアルゴリズムがあることは知っていますが、これら2つに関しては、どちらが優れているのですか?またその理由は何ですか?

4

4 に答える 4

1

最初のアルゴリズムは、一部のカードを最初の位置に残し、「デュアル スワップ」問題 (同じ 2 枚のカードを 2 回交換すると最初のカードの状態になる) に対して脆弱になる可能性があるため、非常に偏った分布を生成します。

@sh1が言及したように、2番目のアルゴリズムはFisher-Yatesアルゴリズムの展開されたバージョンですが、1つの小さな例外があります.リストからアイテムを削除すること自体が線形操作であり、反復ごとに実行されるため、線形ではありません。したがって、全体的なアルゴリズムの複雑さはO(n^2)。

Fisher-Yates アルゴリズムの効率的なバージョンは次のようになります。

疑似コードで（選択した言語について言及していないため）

for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

念のため、Pythonの実装:)

import random
n = 52
arr = [i for i in range(1,n+1)]

for i in range(n-1, 1, -1):
    elem_to_swap = random.randint(0, i)
    arr[elem_to_swap], arr[i] = arr[i], arr[elem_to_swap]
于 2013-05-31T19:41:30.700 に答える
1

2 番目のアルゴリズムは、 Fisher-Yatesの unrolled by two 実装のようです。このシャッフルには、一様分布で可能なすべての結果から 1 つを選択するという特性があります。ほとんどの人が「公正な」または「完全な」シャッフルと呼ぶもの。乱数ジェネレーターが偏りのない結果を提供していれば、追加のランダム性のために操作を繰り返す必要はありません。

最初のアルゴリズムは、おそらく漸近的にどのような分布かわかりません。私はさまざまな理由でそれを避けます。主な理由は、X が適切なシャッフルを生成する前に必要な大きさがわからないためですが、52 を超えることは確かです。不十分なシャッフルを意図的にシミュレートする以外に、このアルゴリズムの適切なアプリケーションを考えることはできません。

最初のアルゴリズムは適切に機能しており、これは場合によっては有益ですが、それが必要な場合は、2 番目のアルゴリズムを変更して同様に動作させることができます。

于 2013-05-31T19:22:23.003 に答える
0

より良いものは次のとおりです。

  1. 一部の一時配列で 52 の数値を生成する
  2. 一時配列をキーとして使用して、カードで配列を注文します

C＃でそれは見える

Random r = new Random(DateTime.Now.Miliseconds);
string [] cards = new string[52]{"1","2",.....};
int [] temp = new int[52];
for(int i=0;i<52;i++)
{
    temp[i]=r.Next();
}

Array.Sort(temp,cards);
于 2013-05-31T18:59:42.407 に答える