.NET で文字列の配列をランダム化する最良の方法は何ですか? Array私の配列には約 500 個の文字列が含まれており、同じ文字列をランダムな順序で使用して新しい配列を作成したいと考えています。
回答に C# の例を含めてください。
Matthias
質問する
179571 次
19 に答える
242
次の実装では、Knuth Shuffle として知られるFisher-Yates アルゴリズムを使用します。これは O(n) 時間で実行され、所定の場所でシャッフルされるため、コード行数は増えますが、「ランダムに並べ替える」手法よりもパフォーマンスが向上します。パフォーマンスの比較測定については、こちらを参照してください。私は System.Random を使用しましたが、これは暗号化以外の目的には問題ありません。*
static class RandomExtensions
{
public static void Shuffle<T> (this Random rng, T[] array)
{
int n = array.Length;
while (n > 1)
{
int k = rng.Next(n--);
T temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
}
使用法：
var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle
* より長い配列の場合、(非常に多くの) 順列の数が均等になるようにするには、スワップごとに疑似乱数ジェネレーター (PRNG) を何度も繰り返して実行し、十分なエントロピーを生成する必要があります。500 要素の配列の場合、可能な 500 のごく一部にすぎません! PRNGを使用して順列を取得することが可能になります。それにもかかわらず、Fisher-Yates アルゴリズムは偏りがないため、シャッフルは使用する RNG と同じくらい優れています。
于 2008-09-21T08:51:46.963 に答える
208
.NET 3.5 を使用している場合は、次の IEnumerable クールネスを使用できます。
Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();
編集：対応するVB.NETコードは次のとおりです。
Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()
時間ベースのシーケンスを返すため、System.Random は「スレッドセーフではない」および「おもちゃのアプリにのみ適している」という発言に応えて、2 番目の編集: 私の例で使用されているように、Random() は完全にスレッドセーフでない限り、配列をランダム化するルーチンを再入力できるようにしています。その場合lock (MyRandomArray)、データを破損しないようにするためにとにかく何かが必要になります。これにより、同様に保護rndされます。
また、エントロピーのソースとしての System.Random はあまり強力ではないことをよく理解する必要があります。MSDN のドキュメントに記載されているように、System.Security.Cryptography.RandomNumberGeneratorセキュリティ関連の作業を行う場合は、から派生したものを使用する必要があります。例えば：
using System.Security.Cryptography;
...
RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();
...
static int GetNextInt32(RNGCryptoServiceProvider rnd)
{
byte[] randomInt = new byte[4];
rnd.GetBytes(randomInt);
return Convert.ToInt32(randomInt[0]);
}
于 2008-09-20T17:40:06.357 に答える
19
シャッフルアルゴリズムを探していますよね？
さて、これを行うには2つの方法があります。方法、そしてそれが機能するので、岩のように愚かですが、誰が気にしますか。
ばかげた方法
- 最初の配列の複製を作成しますが、各文字列に乱数をタグ付けする必要があります。
- 重複する配列を乱数に関してソートします。
このアルゴリズムはうまく機能しますが、乱数ジェネレーターが2つの文字列に同じ番号のタグを付ける可能性が低いことを確認してください。いわゆる誕生日のパラドックスのために、これはあなたが予想するよりも頻繁に起こります。その時間計算量はO（n log n）です。
賢い方法
これを再帰的アルゴリズムとして説明します。
サイズnの配列をシャッフルするには（[0 .. n -1]の範囲のインデックス）：
n =0の 場合n >0の 場合
- 何もしない
- （再帰的ステップ）配列の最初のn -1要素をシャッフルします
- [0 ..n-1]の範囲のランダムなインデックスxを選択します
- インデックスn -1の要素をインデックスxの要素と交換します
反復的に同等なのは、イテレータを配列内でウォークスルーし、進行中にランダムな要素と交換することですが、イテレータが指す要素の後にある要素と交換することはできないことに注意してください。これは非常によくある間違いであり、偏ったシャッフルにつながります。
時間計算量はO（n）です。
于 2008-09-20T17:54:15.263 に答える
8
このアルゴリズムは単純ですが、効率的ではありません (O(N 2 ))。すべての「順序付け」アルゴリズムは通常、O(N log N) です。数十万の要素以下ではおそらく違いはありませんが、大きなリストの場合は違います。
var stringlist = ... // add your values to stringlist
var r = new Random();
var res = new List<string>(stringlist.Count);
while (stringlist.Count >0)
{
var i = r.Next(stringlist.Count);
res.Add(stringlist[i]);
stringlist.RemoveAt(i);
}
O(N 2 ) である理由は微妙です。List.RemoveAt()は、最後から順番に削除しない限り、O(N) 操作です。
于 2008-09-20T17:39:27.467 に答える
4
Matt Howells から拡張メソッドを作成することもできます。例。
namespace System
{
public static class MSSystemExtenstions
{
private static Random rng = new Random();
public static void Shuffle<T>(this T[] array)
{
rng = new Random();
int n = array.Length;
while (n > 1)
{
int k = rng.Next(n);
n--;
T temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
}
}
次に、次のように使用できます。
string[] names = new string[] {
"Aaron Moline1",
"Aaron Moline2",
"Aaron Moline3",
"Aaron Moline4",
"Aaron Moline5",
"Aaron Moline6",
"Aaron Moline7",
"Aaron Moline8",
"Aaron Moline9",
};
names.Shuffle<string>();
于 2010-08-18T15:45:00.240 に答える
2
頭のてっぺんから考えてみると、次のことができます。
public string[] Randomize(string[] input)
{
List<string> inputList = input.ToList();
string[] output = new string[input.Length];
Random randomizer = new Random();
int i = 0;
while (inputList.Count > 0)
{
int index = r.Next(inputList.Count);
output[i++] = inputList[index];
inputList.RemoveAt(index);
}
return (output);
}
于 2008-09-20T17:42:21.390 に答える
1
一連の文字列を移動する必要があるため、配列のランダム化は集中的です。配列からランダムに読み取らないのはなぜですか？最悪の場合、getNextString() を使用してラッパー クラスを作成することもできます。本当にランダムな配列を作成する必要がある場合は、次のようなことができます
for i = 0 -> i= array.length * 5
swap two strings in random places
※5は任意です。
于 2008-09-20T17:38:46.610 に答える
1
わかりました、これは明らかに私の側からの衝突です (申し訳ありません...) が、私は非常に一般的で暗号的に強力な方法をよく使用します。
public static class EnumerableExtensions
{
static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
{
var randomIntegerBuffer = new byte[4];
Func<int> rand = () =>
{
RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
return BitConverter.ToInt32(randomIntegerBuffer, 0);
};
return from item in enumerable
let rec = new {item, rnd = rand()}
orderby rec.rnd
select rec.item;
}
}
Shuffle() は任意の IEnumerable の拡張であるため、たとえば、リスト内のランダムな順序で 0 から 1000 までの数値を取得するには、
Enumerable.Range(0,1000).Shuffle().ToList()
このメソッドは、並べ替えに関しても驚くことはありません。並べ替え値は、シーケンス内の要素ごとに 1 回だけ生成され、記憶されるためです。
于 2012-10-24T15:37:06.313 に答える
0
Jacco さん、カスタム IComparer を使用するソリューションは安全ではありません。ソート ルーチンでは、適切に機能するために比較子がいくつかの要件に準拠する必要があります。それらの最初のものは一貫性です。比較子が同じオブジェクトのペアで呼び出された場合、常に同じ結果を返す必要があります。(比較も推移的でなければなりません)。
これらの要件を満たさないと、並べ替えルーチンで無限ループの可能性など、さまざまな問題が発生する可能性があります。
ランダムな数値を各エントリに関連付け、その値で並べ替えるソリューションに関しては、2 つのエントリに同じ数値が割り当てられるたびに、出力のランダム性が損なわれるため、出力に固有の偏りが生じます。(「安定した」並べ替えルーチンでは、入力の最初のものは出力の最初になります。Array.Sort はたまたま安定していませんが、Quicksort アルゴリズムによって行われるパーティショニングに基づくバイアスがまだあります)。
必要なランダム性のレベルについて考える必要があります。決定的な攻撃者から保護するために暗号レベルのランダム性が必要なポーカー サイトを運営している場合、曲のプレイリストをランダム化したいだけの場合とは非常に異なる要件があります。
曲リストのシャッフルには、シードされた PRNG (System.Random など) を使用しても問題ありません。ポーカー サイトの場合、それはオプションではなく、stackoverflow で他の人があなたのためにしようとしているよりもはるかに一生懸命に問題について考える必要があります。(暗号化 RNG を使用することは始まりにすぎません。アルゴリズムがバイアスを導入しないこと、エントロピーの十分なソースがあること、およびその後のランダム性を損なう内部状態を公開しないことを確認する必要があります)。
于 2008-09-21T13:36:08.777 に答える
0
同じ長さのランダムな float または int の配列を生成します。その配列をソートし、ターゲット配列で対応するスワップを行います。
これにより、真に独立したソートが得られます。
于 2008-09-20T17:37:36.583 に答える
0
Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();
while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}
于 2008-09-20T17:43:31.810 に答える
0
この投稿にはすでにかなりの回答が寄せられています - 高速で偏りのない結果を得るには、フィッシャー・イェーツ シャッフルのダーステンフェルド実装を使用してください。いくつかの実装が投稿されていますが、実際には正しくないものもあります。
この手法を使用して完全シャッフルと部分シャッフルを実装することについて、しばらく前にいくつかの投稿を書きました(この 2 番目のリンクは、私が価値を追加したいと考えている場所です) また、実装が公平かどうかを確認する方法に関するフォローアップ投稿も書きました。これは、任意のシャッフル アルゴリズムのチェックに使用できます。2 番目の投稿の最後で、乱数の選択における単純なミスの影響を確認できます。
于 2008-09-21T17:37:30.177 に答える
-1
private ArrayList ShuffleArrayList(ArrayList source)
{
ArrayList sortedList = new ArrayList();
Random generator = new Random();
while (source.Count > 0)
{
int position = generator.Next(source.Count);
sortedList.Add(source[position]);
source.RemoveAt(position);
}
return sortedList;
}
于 2012-05-01T12:00:09.090 に答える
-1
OLINQ を使用した簡単な方法を次に示します。
// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());
// Output array
List<String> lstRandom = new List<string>();
// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);
于 2008-09-20T19:03:07.517 に答える