1

0 から連続する n 個の整数配列が与えられた場合、つまり

0,1,2,..n

n/2数字をランダムに選択したい。

するとn=5 、可能なセットは になります0,3,5。

それを簡単に達成する方法は？

4

6 に答える 6

2

これを行うために私が見つけた最も簡単な方法は、不完全なFisher-Yates shuffleです。n/2 回の反復後に停止します。

実際のシャッフルは、ランダムに選択された数字と、まだ使用されていない数字のプールの 2 つの配列で機能するため、選択できます。たまたま、2 つの配列の合計サイズが元の配列の長さであるため、分割して配置することができます。

n/2 回の反復の後、選択された数値を表すパーティションは、元の配列からランダムに選択されます。

これを別の見方をすると、フル シャッフルの結果の最初の n/2 の数値は、シャッフルの n/2+1 回以降の反復によって変更されないということです。

于 2013-01-26T09:09:33.177 に答える
2

Fisher-Yates Shuffleを使用n/2して、配列の最初の項目を選択します。

@Patricia Shanahan が彼女の回答で指摘しているように、n/2Fisher-Yates を使用して配列の最初の項目をシャッフルするだけで済みます。

于 2013-01-26T09:10:14.923 に答える
0

あなたが書くときにLinqは許可されていませんalgorithmか？

int[] arrInts = new int[] {0, 1, 2, 3, 4, 5, 6};
var r = new Random();
var randomInts = arrInts.OrderBy(i => r.Next(arrInts.Length))
                        .Take(arrInts.Length/2)
                        .ToArray();

編集: パフォーマンスについて 100% 確信があるわけではありませんが、.AsParallel()前に使用する方がよい場合があります.OrderBy()。

Linq は非常に読みやすく、アルゴリズムを記述するのに約 5 秒かかったので、並べ替えとループを「手動で」記述するのに何分もかかりました。

于 2013-01-26T22:55:57.963 に答える
0

アプローチの 1 つは、Next で Random オブジェクトを使用してベクトル番号のインデックスを生成することです。ArrayList や HashSet などの構造体に新しい生成値を追加して、それを記憶します。インデックスを新しく生成するたびに、その値がこの構造に存在するかどうかを確認します。

于 2013-01-26T09:13:03.013 に答える