Returning items randomly from a collection

Question

I've a method which returns a generic list collection(List) from the database. This collection has got order details i.e., Order Id, order name, product details etc.

Also, method the method returns a collection having only the top 5 orders sorted by order date descending.

My requirement is that each time the client calls this method, I need to return collection which has got 5 random orders.

How do I achieve this using C#?

Answer 1

return collection.Where(()=>Random.Next(100) > (5 / collection.Count * 100)));

Answer 2

return myList.OfType<Order>().OrderBy(o => Guid.NewGuid()).Take(5);

Answer 3

I wrote a TakeRandom extension method a while back which does this using a Fisher-Yates shuffle. It's pretty efficient as it only bothers to randomise the number of items that you actually want to return, and is guaranteed to be unbiased.

public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> source, int count)
{
    var array = source.ToArray();
    return ShuffleInternal(array, Math.Min(count, array.Length)).Take(count);
}

private static IEnumerable<T> ShuffleInternal<T>(T[] array, int count)
{
    for (var n = 0; n < count; n++)
    {
        var k = ThreadSafeRandom.Next(n, array.Length);
        var temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }

    return array;
}

An implementation of ThreadSafeRandom can be found at the PFX team blog.

Answer 4

You really should do this in the database - no point in returning a big stack of stuff only to drop all but five on the floor. You should amend your question to explain what typew of data access stack is involved so people can give better answers. For instance, you could do an ORDER BY RAND():

SELECT TOP 5 ... FROM orders
ORDER BY RAND()

But that visits every row, which you don't want. If you're using SQL Server [and would like to be tied to it :P], you could use TABLESAMPLE.

If you're using LINQ to SQL, go here

EDIT: Just pretend the rest of this isnt here - it's not efficient and hence Greg's answer is far more desirable if you do want to sort client-side.

But, for completeness, paste the following into LINQPad:

var orders = new[] { "a", "b", "c", "d", "e", "f" };
var random = new Random();
var result = Enumerable.Range(1,5).Select(i=>orders[random.Next(5)])
result.Dump();

EDIT: Brute force answer to Greg's point (Yes, not efficient or pretty)

var orders = new[] { "a", "b", "c", "d", "e", "f" };

var random = new Random();

int countToTake = 5;

var taken = new List<int>( countToTake);

var result = Enumerable.Range(1,countToTake)
 .Select(i=>{
  int itemToTake; 
  do { 
   itemToTake = random.Next(orders.Length); 
  } while (taken.Contains(itemToTake)); 
  taken.Add(itemToTake); 
  return orders[itemToTake];
 });

result.Dump();

Answer 5

Here's how I would do it, using an extension method to perform a Fisher-Yates-Durstenfeld shuffle.

(This is obviously very similar to Greg's answer, but there are a few differences that, in my opinion, merit a separate answer.)

List<Orders> listOfOrders = GetTheOrdersFromSomewhere();
var fiveRandomOrders = listOfOrders.Shuffle().Take(5);

// ...

public static class ExtensionMethods
{
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        if (_threadStaticRng == null)
            _threadStaticRng = new Random();

        return source.Shuffle(_threadStaticRng);
    }

    public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> source, Random rng)
    {
        // parameter null checking removed for brevity

        T[] sourceArray = source.ToArray();
        for (int n = 0; n < sourceArray.Length; n++)
        {
            int k = rng.Next(n, sourceArray.Length);
            yield return sourceArray[k];

            sourceArray[k] = sourceArray[n];
        }
    }

    [ThreadStatic]
    private static Random _threadStaticRng;
}