c# Randomly order a list when values are the same

Question

I have a list which I have ordered by score like this:

var orderedList = outcomeRequestModels
    .Where(m => m.Score > 0)
    .OrderByDescending(m => m.Score).ToList();

What I would like to do, is randomise the items in the list with the same score. So if I have a list of items like this:

var t = [{
  name: 'test 1',
  score: 20
}, {
  name: 'test 2',
  score: 30
}, {
  name: 'test 3',
  score: 20
}, {
  name: 'test 4',
  score: 20
}, {
  name: 'test 5',
  score: 20
}, {
  name: 'test 6',
  score: 30
}, {
  name: 'test 7',
  score: 15
}, {
  name: 'test 8',
  score: 20
}, {
  name: 'test 9',
  score: 30
}];

I would like it to order like this:

var t = [{
  name: 'test 9',
  score: 30
}, {
  name: 'test 6',
  score: 30
}, {
  name: 'test 2',
  score: 30
}, {
  name: 'test 1',
  score: 20
}, {
  name: 'test 4',
  score: 20
}, {
  name: 'test 5',
  score: 20
}, {
  name: 'test 3',
  score: 20
}, {
  name: 'test 8',
  score: 20
}, {
  name: 'test 7',
  score: 15
}];

and if I went through again, it would switch the order up like this:

var t = [{
  name: 'test 6',
  score: 30
}, {
  name: 'test 2',
  score: 30
}, {
  name: 'test 9',
  score: 30
}, {
  name: 'test 8',
  score: 20
}, {
  name: 'test 4',
  score: 20
}, {
  name: 'test 5',
  score: 20
}, {
  name: 'test 1',
  score: 20
}, {
  name: 'test 3',
  score: 20
}, {
  name: 'test 7',
  score: 15
}];

Does anyone know how I can do this?

I think you can do something like : `var orderedList = outcomeRequestModels .Where(m => m.Score > 0) .OrderByDescending(m => m.Score).OrderBy(x => Guid.NewGuid()).ToList();` — Steve, Feb 26 '18 at 16:27
@Steve Guids are unique, not random, and are not a suitable source of randomness. — Servy, Feb 26 '18 at 16:28
@Steve You need `ThenBy`, and you also want to associate the same `Guid` with each record upfront to avoid inconsistencies when ordering records. — Sergey Kalinichenko, Feb 26 '18 at 16:30
@dasblinkenlight A quick peruse of Linq2Objects `EnumerableSorter` (the business end of OrderBy) looks like it builds an array of sort keys before any sort takes place, and it is this array that is used in the sort. Of course, it's an imlementation detail, so it's probably best not to lean on this behaviour too hard. — spender, Feb 26 '18 at 16:40
This is not a good duplicate - OP wants multiple shuffles within same-score groups, while the duplicates look for a shuffle of the entire set, or obtaining its random subset. Voting to re-open. — Sergey Kalinichenko, Feb 26 '18 at 17:05
Rather than using `OrderBy` - which is a sorter - you could use a proper shuffle — Ňɏssa Pøngjǣrdenlarp, Feb 26 '18 at 17:10
@Plutonix That solution was given via [this duplicate](https://stackoverflow.com/questions/5807128/an-extension-method-on-ienumerable-needed-for-shuffling), but dasblinkenlight felt the need to reopen the question because he's apparently opposed to a working solution to this problem. — Servy, Feb 26 '18 at 17:15
@Plutonix Do you have a source for an explanation of how that shuffle is biased (outside of the fact that `Random` is only pseudorandom)? I don't see how that algorithm is considering items more than is appropriate. It still does the appropriate swap after yielding an item, to ensure that the range of values it's selecting a value from has all of the unselected values on each iteration. — Servy, Feb 26 '18 at 17:27
@Plutonix Yes, an individual item might be swapped more than once before being returned. Why would that bias the results? — Servy, Feb 26 '18 at 19:13
Actually, I worded that wrong - its not *for every item that is moved more than once*, the number of items not moved is equal to the sum of the multi swap count. An item moved 4 times means 3 others dont move — Ňɏssa Pøngjǣrdenlarp, Feb 26 '18 at 19:39
@Plutonix How do you get stuck? On every one of a fixed number of iterations it chooses a value from the range of values not yet chosen, and then shrinks the set of values not yet chosen by one. It can't every get stuck, as it always chooses a value, and every single value not yet chosen always has an equal probability of being the one to be chosen. That particular implementation accomplishes that by moving the selected item *out* of a given range, and moving the item at the bottom of the range into that slot, allowing the range of not chosen items to shrink by one. — Servy, Feb 26 '18 at 19:39
@Plutonix When choosing the next item to yield it always selects randomly from all of the items not yet chosen. Every item is equally likely. It doesn't matter how many times a given item ends up needing to be swapped in the intermediate array, all that matter is that every single time you "get the next item to yield" every single item (not yet yielded) is equally likely, and this does that. Whether you accomplish that by swapping each item exactly once or swapping some several times and others not at all doesn't matter. — Servy, Feb 26 '18 at 19:45
@Plutonix Perhaps you're worried about the final state of that intermediate list. Keep in mind that in this example that list is never used for anything, and will in fact have garbage data (unlike a traditional FS shuffle which mutates an array, rather than yielding a new one). What matters is the values that are yielded. — Servy, Feb 26 '18 at 19:45

Sergey Kalinichenko · Accepted Answer · 2018-02-26T17:18:00.657

2

You can randomize by "tie breaking" on an arbitrarily assigned unique value:

var orderedList = outcomeRequestModels
    .Select(m => new {Model = m, RandomId = Guid.NewGuid()})
    .Where(m => m.Model.Score > 0)
    .OrderByDescending(m => m.Model.Score)
    .ThenBy(m => m.RandomId)
    .Select(m => m.Model)
    .ToList();

Of course, this is not truly random, but will give a pretty good appearance of being arbitrary. The same approach could be used with an instance of Random without much change:

var rnd = new Random();
var orderedList = outcomeRequestModels
    .Select(m => new { Model = m, RandomId = rnd.Next() })
    .Where(m => m.Model.Score > 0)
    .OrderByDescending(m => m.Model.Score)
    .ThenBy(m => m.RandomId)
    .Select(m => m.Model)
    .ToList();

edited Feb 26 '18 at 17:18

answered Feb 26 '18 at 16:28

Sergey Kalinichenko

714,442
84
1,110
1,523

4

...although @Servy's comment above about guids being *unique* rather than *random* is still pertinent. – spender Feb 26 '18 at 16:29
1

Probably not relevant in OPs case, but if you use `Random` then you'll struggle to use this with an ORM (i.e. EF) – DavidG Feb 26 '18 at 16:34
1

@spender There are things that work in practice, and there are things that are formally correct. In my book, Servy is an undisputed champion of splitting hairs, so at some point I stopped paying much attention to his very important comments. – Sergey Kalinichenko Feb 26 '18 at 16:40

score 0 · Answer 2 · answered Feb 26 '18 at 16:40

Beaten to it - but a slight variation on the other answer to help with the ORM comment.

How about something like

var rnd = new Random();

var orderedList = models
    .Where(m => m.Score > 0)
    .AsEnumerable()    // Optional - This should alleviate the ORM comment in the previous answer
    .Select(m => new { m.Name, m.Score, Rand = rnd.Next() })
    .OrderByDescending(m => m.Score).ThenBy(m => m.Rand)
    .Select(m => new { m.Name, m.Score })  // Optional
    .ToList();

c# Randomly order a list when values are the same

2 Answers2