首先,我确实知道Fisher-Yates shuffle.但为了论证,我想允许用户从下拉列表中选择一个排序选项.该列表将包括"随机"选项.根据他们的选择结果,我只想在IComparer实例中替换我的排序.IComparer会是什么样子?
谷歌提出了大量有缺陷的结果,所有结果都采取以下形式:
public class NaiveRandomizer: IComparer { 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() {1,2,3}; var sortCounts = new Dictionary (6); var randomly = new NaiveRandomizer (); for (int i=0;i<10000;i++) { //always start with same list, in _the same order_. var dataCopy = new List (data); dataCopy.Sort(randomly); var key = WriteList(dataCopy); if (sortCounts.ContainsKey(key)) sortCounts[key]++; else sortCounts.Add(key, 1); } foreach (KeyValuePair item in sortCounts) Console.WriteLine(item.Key + "\t" + item.Value); } string WriteList (List list) { string delim = ""; string result = ""; foreach(T item in list) { result += delim + item.ToString(); delim = ", "; } return result; }
那你怎么能实现IComparer
解决这些问题的随机性呢?允许每次调用都要.Sort()
使用单独的IComparer实例,因为我没有看到任何其他方法来执行此操作:必须使用其他一些真正随机的值来比较项目,但该值对于项目也必须是一致的在给定的排序操作中.
我开始在这里,但它被张贴在仓促,是极其缓慢的,甚至不返回所有可能的排序(测试表明,它确实至少消除偏见,如果你不指望缺少的选项).我不希望O(n)表现像Fisher-Yates那样,但我确实想要一些合理的东西(n log n表示小n),我确实希望它显示所有可能的排序.不幸的是,这个链接是当前接受的答案,所以我希望能够用更好的东西替换它.
如果不出意外的话,我希望这可以成为所有谷歌查询寻找IComparable解决方案的磁铁 - 他们最终会在这里而不是其他地方告诉他们使用不正确的版本.
我对这个帖子有点惊讶,发布了多少错误的答案.只是为了提出类似于OP发布的解决方案的其他人,以下代码看起来是正确的:
int[] nums = new int[1000]; for (int i = 0; i < nums.Length; i++) { nums[i] = i; } Random r = new Random(); Array.Sort(nums, (x, y) => r.Next(-1, 2)); foreach(var num in nums) { Console.Write("{0} ", num); }
但是,代码偶尔会抛出异常,但并非总是如此.这就是让调试变得有趣的原因:)如果你运行它足够多次,或者在一个循环中执行排序过程50次左右,你会得到一个错误说明:
IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The IComparer: ''.
换句话说,快速排序将一些数字x
与自身进行比较并获得非零结果.代码的明显解决方案是写:
Array.Sort(nums, (x, y) => { if (x == y) return 0; else return r.NextDouble() < 0.5 ? 1 : -1; });
但即使这样也行不通,因为有时.NET会将3个数字相互比较,从而返回不一致的结果,例如A> B,B> C和C> A(oops!).无论您使用Guid,GetHashCode还是任何其他随机生成的输入,上面显示的解决方案仍然是错误的.
话虽如此,Fisher-Yates是改组数组的标准方法,所以没有真正的理由首先使用IComparer.Fisher-Yates是O(n),而使用IComparer的任何实现都使用具有时间复杂度O(n log n)的场景后面的快速排序.没有充分的理由不使用众所周知的,有效的标准算法来解决这类问题.
但是,如果您真的坚持使用IComparer和rand,那么在排序之前应用随机数据.这需要将数据投影到另一个对象上,这样您就不会丢失随机数据:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Pair{ public T Item1 { get; private set; } public U Item2 { get; private set; } public Pair(T item1, U item2) { this.Item1 = item1; this.Item2 = item2; } } class Program { static void Main(string[] args) { Pair [] nums = new Pair [1000]; Random r = new Random(); for (int i = 0; i < nums.Length; i++) { nums[i] = new Pair (i, r.NextDouble()); } Array.Sort >(nums, (x, y) => x.Item2.CompareTo(y.Item2)); foreach (var item in nums) { Console.Write("{0} ", item.Item1); } Console.ReadKey(true); } } }
或者用自己糟糕的自己获得LINQy:
Random r = new Random(); var nums = from x in Enumerable.Range(0, 1000) orderby r.NextDouble() select x;