3

カードが使用中かどうかを示す配列があります。

int used[52];

使用済みのカードがたくさんある場合、ランダムにカードを選ぶのはひどい方法です。

do {
  card = rand() % 52;
} while (used[card]);

未使用のカードが 3 ～ 4 枚しかない場合、それらを見つけるのに永遠に時間がかかるからです。

私はこれを思いつきました：

 int card;
 int k = 0;
 int numUsed = 0;
 for (k=0; k < 52; ++k) {
   if (used[k]) numUsed += 1;
 }
 if (numUsed == 52) return -1;
 card = rand() % (52 - numUsed);

 for (k=0; k < 52; ++k) {
   if (used[k]) continue;
   if (card == 0) return k;
   card -= 1;
 }

デッキがいっぱいの場合はうまくいくと思いますが、2 つの for ループを通過する必要があるため、デッキが空の場合はうまくいきません。

これを行う最も効率的な方法は何ですか?

4

9 に答える 9

10

どのカードが特定のドローの対象となるかを事前に知らないというコメントに追加した制約を考えると、2パスアルゴリズムが最善の方法である可能性が高いと思います.

狡猾な「単一パスで未知のサイズのリストからランダムに選択する」アルゴリズムを試すことができます。

int sofar = 0;
int selected = -1;
for (i = 0; i < 52; ++i) {
    if (used[i]) continue;
    ++sofar;
    if ((rand() % sofar) == 0) selected = i;
}
if (selected == -1) panic; // there were no usable cards 
else used[selected] = 1;   // we have selected a card

次に、（コメントで言うように）異なるドローに異なる基準がある場合used[i]、実際の基準が何であれ置き換えることができます。

それが機能する方法は、最初のカードを選択することです。次に、1/2 の確率で 2 枚目のカードに置き換えます。その結果を 1/3 の確率で 3 枚目のカードに置き換えます。n ステップ後、前のカードのそれぞれが選択されたものである確率が 1/n であることを帰納法によって証明するのは簡単です。

この方法では多くの乱数が使用されるため、各アイテムの取得が遅くなったり、条件の評価が遅くなったりしない限り、おそらく 2 パス バージョンよりも遅くなります。これは通常、ファイルからランダムな行を選択する場合などに使用されますが、実際にはデータを 2 回実行したくない場合に使用されます。また、乱数の偏りにも敏感です。

シンプルでいいですけどね。

[編集：証拠

ステップ k の後にカード番号 j が現在選択されているカードである確率を p(j,k) とします。

証明する必要があります: すべての n に対して、p(j,n) = 1/n すべての 1 <= j <= n に対して

n = 1 の場合、最初のステップで最初のカードが確率 1/1 = 1 で選択されるため、明らかに p(1,1) = 1 です。

すべての 1 <= j <= k に対して p(j,k) = 1/k であるとします。

次に、ステップ (k+1) で確率 1/(k+1)、つまり p(k+1,k+1) = 1/(k+1) で (k+1) 番目のカードを選択します。

確率 k/(k+1) で既存の選択を保持するため、任意の j < k+1 について:

p(j,k+1) = p(j,k) * k/(k+1)
         = 1/k    * k/(k+1)   // by the inductive hypothesis
         = 1/(k+1)

したがって、すべての 1 <= k <= k+1 に対して p(j,k+1) = 1/(k+1)

したがって、帰納法により、すべての n について: p(j,n) = 1/n for all 1 <= j <= n]

于 2009-07-15T21:47:12.190 に答える
10

未使用のカードのコレクションをもう 1 つ保管しませんか?

それらをランダムな順序で並べたい場合は、最初にそれらをシャッフルし ( Fisher-Yates )、必要に応じてポップします。

于 2009-07-15T20:53:00.957 に答える
6

これを行う最善の方法は、デッキをランダムな順序でシャッフルしてから、最初の未使用のカードを選ぶことです。 このようなシャッフルを実行する最も一般的な方法を次に示します。

于 2009-07-15T20:53:48.990 に答える
2

ランダム カードを配るための標準的なアルゴリズムは次のとおりです。

  • すべてのカードを含むようにデッキを初期化します (順序は重要ではありません)
  • ループ：
  • 0 からデッキサイズ - 1 の範囲でランダムなインデックスを生成します
  • そのインデックスでカードを表示します（または、好きなことをします）
  • デッキのインデックス付きカードを [デッキサイズ -1] のカードと入れ替える
  • デッキサイズを1つ減らす
  • goto ループ: 必要に応じて何度でも
于 2009-07-15T20:58:02.100 に答える
1

次のようなコードを使用して、2 つのループを取り除くことができます。

int card;
int k = 0;
int i = 0;
int unUsed[52];
int numUsed = 0;
for (k = 0; k < 52; ++k) {
  if (used[k]) {
    numUsed += 1;
  } else {
    unUsed[i] = k;
    i++;
  }
}
if (numUsed == 52) return -1;
card = rand() % (52 - numUsed);
return unUsed[card];

効率の向上はそれほど大きくないと思いますが、より多くのメモリを使用することになります。

于 2009-07-15T20:58:52.537 に答える
1

もう 1 つのオプションは、2 つのリストを作成し、1 つを使用して使用済みカードを追跡し、もう 1 つを未使用カードを追跡することです。したがって、カードを使用する場合は、未使用カード リストからそのカードを差し引き、使用済みカード リストの最後に追加します。これにより、毎回 2 つの for ループを実行する必要がなくなります。

于 2009-07-15T21:02:51.950 に答える
0

使用済みのカードを配列の最後に、未使用のカードを最初に保持します。まだ使用されていないカードの数を追跡します。新しいカードが使用されるとき、それを最後の未使用のカードと交換し、残りのカードの数を減らします。

if (numRemaining == 0) return -1;
int cardNum = rand() % numRemaining;
Card card = cards[cardNum]; // or int, if cards are represented by their numbers
cards[cardNum] = cards[numRemaining - 1];
cards[numRemaining - 1] = card;
numRemaining--;
于 2009-07-15T21:59:00.013 に答える
0

多くの言語でのクヌース シャッフル

于 2009-07-16T05:06:40.623 に答える
-1

これが本当にランダムなドローを生成するかどうかはわかりませんが、ほとんどの場合、デッキ全体のループを回避できます. パフォーマンスの点でどのように比較されるかはさらにわかりませんが、それでも次のとおりです。

  • デッキからランダムにカードを入手する
  • カードが既に使用されている場合は、ランダムな方向 (前方または後方) を選択します。
  • 次の未使用のカードが見つかるまで、現在の位置からランダムに決定された方向にデッキをステップスルーします（もちろん、配列の端で適切にラップアラウンドしていることを確認する必要があります）

したがって、最悪の場合、最後の未使用のカードのすぐ隣にあるカードを選び、デッキを「間違った」方向に進めて、デッキを完全にループさせます。

于 2009-07-16T05:38:12.180 に答える