.NET Framework - Random Order of IEnumerable

Asked By shapper

09-Feb-10 08:43 AM

Hello,

How can I create a collection extension that orders its elements in a
random way? Something like:

public static class CollectionExtensions {
private static Random random = new Random();
public static T OrderRandom<T>(this IEnumerable<T> collection) {

T ordered = default(T);
Int32 count = 0;
foreach (T item in collection) {

// Random order elements?

}
return ordered;

} // Random
}

Thank You,
Miguel

09-Feb-10 12:44 PM

Can you clarify the question?  The method you posted does not order the
elements.  Rather, it returns a _single_ element, presumably one that
has been picked randomly.

If you really want a new ordering for the original collection, the
question remains: do you want to actually modify the original
collection?  Or are you looking to simply have a differently-ordered
enumeration of the original collection?

If you just want the latter, one possible approach might look like this:

Random rnd = new Random();

var result = from r in
(from c in collection
select new { Item = c, Order = rnd.Next() })
orderby r.Order
select r.Item;

That will return a new order each time you enumerate the "result" query.
If you want to reorder it once, you will have to resolve the query with
a call to "ToList()" and work from that.

An alternative approach would be to copy your collection into an array
and then shuffle the array.  There have been several discussions in this
newsgroup discussing shuffle techniques.  Just use Google Groups to
search the archives to learn more about that.

Shuffling would be somewhat more efficient than using LINQ (O(n) instead
of O(n log n)), but of course the code is somewhat more complicated and
easier to get wrong (it is particularly important, if you want a true
evenly-distributed randomized order, to exclude already-reordered
elements from subsequent iterations of the shuffle loop).

If you want to permanently reorder the original collection, you can use
either of the above techniques, but apply them directly to the original
collection.  With LINQ, you will have to copy the values back to the
original collection.  With a shuffle, if the original collection is an
IList<T> or similar, you can just reorder in-place.

Pete

09-Feb-10 01:18 PM

{
s

I am using an extension as follows:

public static class CollectionExtensions {
private static Random random =3D new Random();
public static IEnumerable<T> OrderRandomly<T>(this IEnumerable<T>
collection) {

// Order items randomly
List<T> randomly =3D new List<T>(collection);
while (randomly.Count > 0) {
Int32 index =3D random.Next(randomly.Count);
yield return randomly[index];
randomly.RemoveAt(index);
}
} // OrderRandomly
}

Not sure if it is a good approach but it is working and I can reuse it.

09-Feb-10 01:36 PM

No, it is about the worst possible implementation you could have chosen.
I offered two approaches, one with O(n) complexity and one with O(n
log n).  Instead, you have decided upon one with O(n^2) complexity.

What was wrong with the advice I gave you?

Pete

09-Feb-10 05:14 PM

Correct.  The classic shuffle algorithm is found in Knuth, Algorithm
3.4.2 P.

rossum

09-Feb-10 07:00 PM

T>

Hi Pete,

Nothing wrong with your advice ... I am just using it. :-)

Thank You,
Miguel

10-Feb-10 12:44 AM

How is his solution O(n^2) ?
Is the RemoveAT the culprit?

Oz
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?