Sort by Random.Next ()

Question

In this question, one of the suggestions is to sort the list by Random.Next ().

I guess (possibly wrong) suggesting this

public static IEnumerable<T> RandomSort<T>(this IEnumerable<T> items) { Random r = new Random(); var a = items.ToArray(); Array.Sort(a, (t1, t2) => (r.Next()%2==0)?-1 : 1); return a; } 

(Yes, there is already an Array.RandomShuffle function that you obviously use instead. This is not a question)

EDIT: The poster clarified the answer. He suggested using the OrderBy clause.

The question is, is it safe to run the above code (using Array.Sort ())?

My problem is that it violates the basic predicate sorting law:

if (a <b) and (b <c), then (a <c)

This does not even guarantee that if (a <b) then (a <b) the next time you ask.

Will this lead you to "undefined behavior"?

For example, can it break or fall into an infinite loop depending on the sequence of numbers returned by the Random () function?

Answer 1

This is a useful device for creating random permutations of a list. For this permutation, it is absolutely true that if a to b and b to c , then a is in front of c .

Another way to think about it this way: if you sow a random number generator with the same seed every time, then it will always produce the same order. Thus, you can think of each testis of the random number generator, creating (possibly) a different list order.

This does not even guarantee that if (a <b) then (a <b) the next time you ask.

It's good. But, as explained above, if we plant a random number generator with the same seed and present it on Array.Sort , as in your example code in the same state, it will produce the same order.

Answer 2

Just to make a quick observation, since I just tried to make such a randomized view using the following code (to get basic unit tests to run in random order):

 Action<object>[] tests = new Action<object>[] { delegate { SearchStringByTree(SOURCE, distinctor.Keys, out treeResults, out treeTicks); }, delegate { SearchStringByIndexOf(SOURCE, distinctor.Keys, out indexOfResults, out indexOfTicks); }, delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.UTF8, TERMS), out utf8Results, out utf8Ticks); }, delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.ASCII, TERMS), out asciiResults, out asciiTicks); } }; Random r = new Random(); Array.Sort(tests, delegate { return r.Next(-1, 2); }); 

I accidentally got the following ArgumentException :

  IComparer (or the IComparable methods it relies upon) did not return zero 
 when Array.Sort called x.  CompareTo (x).  x: '' x type: 'Action`1' 
 The IComparer: 'System.Array + FunctorComparer`1 [System.Action`1 [System.Object]]'. 

Sort seems to claim equality over elements that are known to be the same (assuming object.ReferenceEquals ), and if Comparer does not return 0 for those that he knows should be equal, it invalidates the whole view.

Answer 3

Just use a random shuffle.

http://www.techtalkz.com/cc-sharp/66613-shuffle-collection.html

Answer 4

how it looks, how it works, it is set only once, and then each subsequent request for this value is the same.

it will be like adding an extra column to a table, filling each field with a random number, and then sorting by that column.

Answer 5

You are right that using a random number function for sorting is an easy way to break the formal requirements that are usually required for sorting functions, including the ones you mentioned.

The current LINQ implementation seems to be calculating all the sort keys up. The following code demonstrates that sort keys are obtained sequentially and exactly once. This is probably a reasonable implementation, as it avoids the problematic scenarios you are worried about.

However, I would not rely on this behavior (it is not documented in MSDN for Enumerable.OrderBy .

  public void Test() { int[] nums = Enumerable.Range(1, 100).ToArray(); var sorted = from i in nums orderby Display(i) select i; sorted.ToArray(); } private static int Display(int i) { Console.WriteLine(i); return i; } 

(The above code sequentially prints from 1 to 100, showing how orderby evaluates the sort keys.)