Optimal Linq Query to Get a Random Sub Collection - Shuffle

Optimal LINQ query to get a random sub collection - Shuffle

Another option is to use OrderBy and to sort on a GUID value, which you can do so using:

var result = sequence.OrderBy(elem => Guid.NewGuid());

I did some empirical tests to convince myself that the above actually generates a random distribution (which it appears to do). You can see my results at Techniques for Randomly Reordering an Array.

How to get a Random Object using Linq

What about:

SelectedPost = q.ElementAt(r.Next(1, Answers.Count()));

Further reading:

The comments below make good contributions to closely related questions, and I'll include them here, since as @Rouby points out, people searching for an answer to these may find this answer and it won't be correct in those cases.

Random Element Across Entire Input

To make all elements a candidate in the random selection, you need to change the input to r.Next:

SelectedPost = Answers.ElementAt(r.Next(0, Answers.Count()));

@Zidad adds a helpful extension method to get random element over all elements in the sequence:

public static T Random<T>(this IEnumerable<T> enumerable)
{
    if (enumerable == null)
    {
         throw new ArgumentNullException(nameof(enumerable));
    }

    // note: creating a Random instance each call may not be correct for you,
    // consider a thread-safe static instance
    var r = new Random();  
    var list = enumerable as IList<T> ?? enumerable.ToList(); 
    return list.Count == 0 ? default(T) : list[r.Next(0, list.Count)];
}

linq: order by random

http://msdn.microsoft.com/en-us/library/system.guid.newguid.aspx

return (from examQ in idb.Exam_Question_Int_Tbl
      where examQ.Exam_Tbl_ID==exam_id
      select examQ).OrderBy(x => Guid.NewGuid()).Take(50);

If this is LINQ-to-SQL you could simply add a ORDER BY NEWID() to your SELECT statement.

As commented it might be better to use an algorithm like Fisher-Yates Shuffle, here is an implementation: https://stackoverflow.com/a/375446/284240

Using LINQ to shuffle a deck

LINQ methods are not mutating existing collections. So this statement does nothing at all: this.OrderBy(a => Guid.NewGuid());
Also, I'm pretty sure you can't assign to this, so you have to either don't inherit from List<T> (which is good), or do something like this:

var sorted = this.OrderBy(a => Guid.NewGuid()).ToList();
this.Clear();
this.AddRange(sorted);

Also look at this SO answer, there is more correct shuffling algorithm.

Shuffle a list using one of the properties in the class

This works:

scheduleList = scheduleList.Shuffle().ToList();

Ok, it works only if you add these extensions which uses the Fisher-Yates-Durstenfeld shuffle:

public static class EnumerableExtensions
{
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        return source.Shuffle(new Random());
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (rng == null) throw new ArgumentNullException("rng");

        return source.ShuffleIterator(rng);
    }

    private static IEnumerable<T> ShuffleIterator<T>(
        this IEnumerable<T> source, Random rng)
    {
        List<T> buffer = source.ToList();
        for (int i = 0; i < buffer.Count; i++)
        {
            int j = rng.Next(i, buffer.Count);
            yield return buffer[j];

            buffer[j] = buffer[i];
        }
    }
}

The credit goes to: https://stackoverflow.com/a/1653204/284240

An extension method on IEnumerable needed for shuffling

You can use a Fisher-Yates-Durstenfeld shuffle. There's no need to explicitly pass a size argument to the method itself, you can simply tack on a call to Take if you don't need the entire sequence:

var shuffled = originalSequence.Shuffle().Take(5);

// ...

public static class EnumerableExtensions
{
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        return source.Shuffle(new Random());
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (rng == null) throw new ArgumentNullException(nameof(rng));

        return source.ShuffleIterator(rng);
    }

    private static IEnumerable<T> ShuffleIterator<T>(
        this IEnumerable<T> source, Random rng)
    {
        var buffer = source.ToList();
        for (int i = 0; i < buffer.Count; i++)
        {
            int j = rng.Next(i, buffer.Count);
            yield return buffer[j];

            buffer[j] = buffer[i];
        }
    }
}

How can I randomly ordering an IEnumerable ?

Enumerators allow "iterated" access only. Thus, there is no possibility to access the elements randomly or in a sorted way. You have to read the enumerated values and (temporarily) store them in another list for which you can apply your (random) sorting algorithm.

[edit] Example:

List<MyObject> list = new List<MyObject>( my_enumerable );
Random rnd = new Random(/* Eventually provide some random seed here. */);
for (int i = list.Count - 1; i > 0; --i)
{
    int j = rnd.Next(i + 1);
    MyObject tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
}
my_enumerable = list;

(I have not tested the example code.)

Is there a more efficent way to randomise a set of LINQ results?

(Please read all the way through, as there are different aspects of efficiency to consider.)

There are definitely simpler ways of doing this - and in particular, you really don't need to perform the query for correct answers repeatedly. Why are you fetching randSubmissions inside the loop? You should also look at ElementAt to avoid the Skip and FirstOrDefault - and bear in mind that as randSubmissions is a list, you can use normal list operations, like the Count property and the indexer!

The option which comes to mind first is to perform a partial shuffle. There are loads of examples on Stack Overflow of a modified Fisher-Yates shuffle. You can modify that code very easily to avoid shuffling the whole list - just shuffle it until you've got as many random elements as you need. In fact, these days I'd probably implement that shuffle slightly differently to you could just call:

return correctSubmissions.Shuffle(random).Take(amount).ToList();

For example:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = 0; i < elements.Length; i++)
    {
        // Find an item we haven't returned yet
        int swapIndex = i + rng.Next(elements.Length - i);
        T tmp = elements[i];
        yield return elements[swapIndex];
        elements[swapIndex] = tmp;
        // Note that we don't need to copy the value into elements[i],
        // as we'll never use that value again.
    }
}

Given the above method, your GetRandomWinners method would look like this:

public List<Submission> GetRandomWinners(int competitionId, Random rng)
{
    List<Submission> submissions = new List<Submission>();
    int winnerCount = DbContext().Competitions
                                 .Single(s => s.CompetitionId == competitionId)
                                 .NumberWinners;

    var correctEntries = DbContext().Submissions
                                    .Where(s => s.CompetitionId == id && 
                                                s.CorrectAnswer)
                                    .ToList();

    return correctEntries.Shuffle(rng).Take(winnerCount).ToList();
}

I would advise against creating a new instance of Random in your method. I have an article on preferred ways of using Random which you may find useful.

One alternative you may want to consider is working out the count of the correct entries without fetching them all, then work out winning entries by computing a random selection of "row IDs" and then using ElementAt repeatedly (with a consistent order). Alternatively, instead of pulling the complete submissions, pull just their IDs. Shuffle the IDs to pick n random ones (which you put into a List<T>, then use something like:

return DbContext().Submissions
                  .Where(s => winningIds.Contains(s.Id))
                  .ToList();

I believe this will use an "IN" clause in the SQL, although there are limits as to how many entries can be retrieved like this.

That way even if you have 100,000 correct entries and 3 winners, you'll only fetch 100,000 IDs, but 3 complete records. Hope that makes sense!

In LINQ, does orderby() execute the comparing function only once or execute it whenever needed?

Your approach should work but it is slow.

It works because OrderBy first calculates the keys for every item using the key selector, then it sorts the keys. So the key selector is only called once per item.

In .NET Reflector see the method ComputeKeys in the class EnumerableSorter.

this.keys = new TKey[count];
for (int i = 0; i < count; i++)
{
    this.keys[i] = this.keySelector(elements[i]);
}
// etc...

whether this is absolutely safe and always works as expected

It is undocumented so in theory it could change in future.

For shuffling randomly you can use the Fisher-Yates shuffle. This is also more efficient - using only O(n) time and shuffling in-place instead of O(n log(n)) time and O(n) extra memory.

Related question

C#: Is using Random and OrderBy a good shuffle algorithm?

How to loop randomly through certain parts of an array?

I think this will give you the results you want:

private Random rnd = new Random();
public MainWindow()
{
    InitializeComponent();
    string[] assignments = new string[]
    {
        "https://cdn2.iconfinder.com/data/icons/animals/48/Turtle.png",
        "https://cdn2.iconfinder.com/data/icons/animals/48/Butterfly.png",
        "https://cdn2.iconfinder.com/data/icons/animals/48/Dolphin.png",
        "https://cdn2.iconfinder.com/data/icons/animals/48/Elephant.png",
        "https://cdn2.iconfinder.com/data/icons/animals/48/Hippopotamus.png",
        "https://cdn2.iconfinder.com/data/icons/animals/48/Panda.png"
    }.OrderBy(x => rnd.Next()).ToArray();

    string[] animals =
        Enumerable
            .Range(0, 99)
            .Select(i => assignments[i % assignments.Length])
            .ToArray();

    foreach (int i in Enumerable.Range(1, 9))
    {
        animals[i * 9] = assignments[9 % assignments.Length];
    }

    ItemsControl1.ItemsSource = animals;
}

Just a small hint to save you trouble, always make your Random variable a single field - this will avoid potential mistakes with rapidly call code repeating random numbers. That won't happen in this code, but it's just a good habit to get in to.

I just realised that I could lose the foreach loop by doing this:

    string[] animals =
        Enumerable
            .Range(0, 99)
            .Select(i => assignments[i % 9 == 0 ? 9 : i % assignments.Length])
            .ToArray();

That's even better.

Optimal Linq Query to Get a Random Sub Collection - Shuffle