まず、フィッシャー・イェーツ・シャッフルについて知っています。しかし、引数のために、ユーザーがドロップダウン リストから並べ替えオプションを選択できるようにしたいとしましょう。このリストには、「ランダム」オプションが含まれます。彼らの選択の結果に基づいて、ソートを IComparer インスタンスに置き換えたいだけです。IComparer はどのように見えるでしょうか?
Google は多くの欠陥のある結果を表示しますが、これらはすべて次の形式を取ります。
public class NaiveRandomizer<T> : IComparer<T>
{
private static Random rand = new Random();
public int Compare(T x, T y)
{
return (x.Equals(y))?0:rand.Next(-1, 2);
}
}
ただし、その実装には偏りがあり、状況によっては例外をスローすることさえあります。バイアスは、次のコードで実証できます。
void Test()
{
Console.WriteLine("NaiveRandomizer Test:");
var data = new List<int>() {1,2,3};
var sortCounts = new Dictionary<string, int>(6);
var randomly = new NaiveRandomizer<int>();
for (int i=0;i<10000;i++)
{ //always start with same list, in _the same order_.
var dataCopy = new List<int>(data);
dataCopy.Sort(randomly);
var key = WriteList(dataCopy);
if (sortCounts.ContainsKey(key))
sortCounts[key]++;
else
sortCounts.Add(key, 1);
}
foreach (KeyValuePair<string, int> item in sortCounts)
Console.WriteLine(item.Key + "\t" + item.Value);
}
string WriteList<T>(List<T> list)
{
string delim = "";
string result = "";
foreach(T item in list)
{
result += delim + item.ToString();
delim = ", ";
}
return result;
}
IComparer<T>では、これらの問題を解決するランダムをどのように実装できるのでしょうか? .Sort()これを行う他の方法が見当たらないため、各呼び出しで個別の IComparer インスタンスを使用するように要求することが許可されています。特定のソート操作内。
私はここから始めましたが、急いで投稿され、非常に遅く、可能なすべてのソートを返すことさえありません（テストでは、欠落しているオプションを数えなければ、少なくともバイアスを排除することが示されています）。Fisher-Yates のような O(n) のパフォーマンスは期待していませんが、合理的なもの (小さな n に対して n log n) が必要であり、考えられるすべての並べ替えが表示されることを期待しています。残念ながら、そのリンクはその質問に対する現在受け入れられている回答であるため、もう少し良いものに置き換えることができることを望んでいます。
他に何もないとしても、これが IComparable ソリューションを探しているすべての Google クエリの磁石になることを望んでいます。つまり、間違ったバージョンを使用するように他の場所に指示するのではなく、ここに行き着くということです。