Random Order of IEnumerable

  • Thread starter Thread starter shapper
  • Start date Start date
S

shapper

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
 
shapper said:
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
}
Click to expand...

Can you clarify the question? The method you posted doesn't 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'll 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's 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'll 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
 
Can you clarify the question?  The method you posted doesn't 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'll 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's 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'll 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
Click to expand...

I am using an extension as follows:

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

// Order items randomly
List<T> randomly = new List<T>(collection);
while (randomly.Count > 0) {
Int32 index = 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.
 
shapper said:
I am using an extension as follows:

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

// Order items randomly
List<T> randomly = new List<T>(collection);
while (randomly.Count > 0) {
Int32 index = 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.
Click to expand...

No, it's 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've decided upon one with O(n^2) complexity.

What was wrong with the advice I gave you?

Pete
 
shapper said:
I am using an extension as follows:
Click to expand...
 public static class CollectionExtensions {
    private static Random random = new Random();
    public static IEnumerable<T> OrderRandomly<T>(this IEnumerable<T>
collection) {
Click to expand...
      // Order items randomly
      List<T> randomly = new List<T>(collection);
      while (randomly.Count > 0) {
        Int32 index = random.Next(randomly.Count);
        yield return randomly[index];
        randomly.RemoveAt(index);
      }
    } // OrderRandomly
}
Click to expand...
Not sure if it is a good approach but it is working and I can reuse it.
Click to expand...

No, it's 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've decided upon one with O(n^2) complexity.

What was wrong with the advice I gave you?

Pete
Click to expand...

Hi Pete,

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

Thank You,
Miguel
 
shapper said:
I am using an extension as follows:

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

// Order items randomly
List<T> randomly = new List<T>(collection);
while (randomly.Count > 0) {
Int32 index = 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.
Click to expand...

No, it's 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've decided upon one with O(n^2) complexity.

What was wrong with the advice I gave you?

Pete
Click to expand...

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

Oz
 
Back
Top