How can I randomly ordering an IEnumerable<>?

Question

I have this IEnumerable :

IEnumerable<MyObject>

and I need to order the list of the MyObject randomly. Do I need to cast into an ArrayList?

Or I can do it directly? Thanks

EDIT

this is my actual random order function :

IList<ArchiePacchettoOfferta> list = new List<ArchiePacchettoOfferta>(m_oEnum);
for (int i = 0; i < list.Count; ++i)
{
    HttpContext.Current.Response.Write(list[i].Titolo + "<br />");
}

Random rnd = new Random();
for (int i = 0; i < list.Count; ++i)
{
    int swapIndex = rnd.Next(i + 1);
    ArchiePacchettoOfferta tmp = list[i];
    list[i] = list[swapIndex];
    list[swapIndex] = tmp;
}

for (int i = 0; i < list.Count; ++i)
{
    HttpContext.Current.Response.Write(list[i].Titolo + "<br />");
}

it orders the list in the same way every time :(

Almost, but not quite a dupe of http://stackoverflow.com/questions/1651619/optimal-linq-query-to-get-a-random-sub-collection-shuffle/1653204#1653204 — LukeH, Jul 04 '11 at 09:52

score 7 · Answer 1 · edited May 23 '17 at 12:26

7

IEnumerable<int> ints;

var random = new Random();
var shuffled = ints.OrderBy(i => random.Next()).ToList();

The ToList is only there to ensure that the same (random) order is returned when iterating over shuffled more than once. Of course you can shuffle 'inplace' if you don't need the original anymore

ints = ints.OrderBy(i => random.Next()).ToList();

Update

There is some discussion on whether you should rely on OrderBy comparing elements only once. If you don't want to do trust your .NET implementation to do that, spell it out:

var random = new Random();
var shuffled = ints
      .Select(i => new { key=random.Next(), i })
      .OrderBy(tmp => tmp.key)
      .Select(tmp => tmp.i)
      .ToList();

See these links for more background on what potential problem this solves (mainly a performance degradation for the current sample, but also the risk of having non-uniform distribution):

Jon Skeet's blog (section "There may be trouble ahead")
Shuffle string array without duplicates (that's Eric arguing for the short version)
Eric Lipperts blog: Shuffling is not sorting (that's the opposite argument)

edited May 23 '17 at 12:26

Community

1
1

answered Jul 04 '11 at 09:30

sehe

374,641
47
450
633

1

I generally dislike this way of shuffling - you're *assuming* that the key projection is only applied to each item once. As it happens, that's the case with the current implementation of LINQ to Objects, but it's not guaranteed. It's also slower than doing a Fischer-Yates shuffle. – Jon Skeet Jul 04 '11 at 09:34
1

Jon: appreciated. **Edit** Eric Lippert actually promised me to get the documentation team to add the 'single comparison' guarantee to the docs. You yourself argued that OrderBy should not (and does not) evaluate the comparison between elements more than once - because the comparison might be expensive - on your blog. You found that the .NET implementation honours this – sehe Jul 04 '11 at 09:37
2

Yes, but that's not the same as suggesting that you should rely on that... especially when ordering by this is more expensive than performing a shuffle anyway. – Jon Skeet Jul 04 '11 at 09:41
@Jon: Wouldn't whether or not this method is 'more expensive' depend on the actual form of the input (which isn't known at this time)? – sehe Jul 04 '11 at 09:42
Link [link](http://stackoverflow.com/questions/6188331/shuffle-string-array-without-duplicates/6197291#6197291) to mentioned earlier discussion – sehe Jul 04 '11 at 09:45
It's interesting - I *thought* I'd seen Eric arguing against using this form of shuffling elsewhere. I'll see what I can dig up. – Jon Skeet Jul 04 '11 at 09:50
2

I've found a quote in a blog post: http://blogs.msdn.com/b/ericlippert/archive/2011/01/31/spot-the-defect-bad-comparisons-part-four.aspx "Shuffling is not sorting; it is the opposite of sorting, so don't use a sort algorithm to shuffle. There are lots of efficient shuffle algorithms that are easy to implement." – Jon Skeet Jul 04 '11 at 09:52
Note that that's using List.Sort rather than OrderBy, but the principle still applies, IMO :) – Jon Skeet Jul 04 '11 at 09:53
2

@Jon: Thanks for the forensic work. All I can say is that we (badly) need a standard Shuffle extension in the .NET framework. It could DoTheRightThing, optimize appropriately and in general prevent surprises – sehe Jul 04 '11 at 10:20

score 2 · Answer 2 · edited May 23 '17 at 12:18

2

You can't just cast an IEnumerable<T> to a different type - and you wouldn't want to convert to the non-generic ArrayList type anyway.

However, what you can do is read everything into a list (simplest with the ToList extension method) and then shuffle that. My answer here has an example of the shuffle code - admittedly within an iterator block, but the guts are there.

EDIT: If you're seeing the same ordering every time, I suspect you're creating multiple instances of Random in a short space of time, and they've all got the same seed.

Read this article for details and workarounds.

edited May 23 '17 at 12:18

Community

1
1

answered Jul 04 '11 at 09:17

Jon Skeet

1,421,763
867
9,128
9,194

Uhm, Yeah but I also do this myEnum.ToArray(); – markzzz Jul 04 '11 at 09:19
@markzzz: Yes, you *can* use an array instead. It's slightly more efficient to convert to a list than to an array, unless you happen to get lucky, IIRC. Either way, you end up with a suitable collection you can shuffle. – Jon Skeet Jul 04 '11 at 09:22
@markzzz: Do you have a `using` directive for `System.Linq`? Note that it also needs to be `ToList();`, not `ToList;`. Please give more details than "doesn't work". – Jon Skeet Jul 04 '11 at 09:33
Tested you random order : the list is the same each time, nothing change – markzzz Jul 04 '11 at 09:54
@markzzz: See my edit. Don't create a new `Random` instance each time. – Jon Skeet Jul 04 '11 at 10:00
? i don't create a Random instance each time. It is not in the for cycle :O – markzzz Jul 04 '11 at 10:03
@markzzz: No, each time you shuffle the list you create a new one. In other words, if you're calling the method containing this code multiple times, it will create multiple instances of Random. – Jon Skeet Jul 04 '11 at 10:06

Flinsch · Accepted Answer · 2011-07-04T10:05:23.490

2

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.)

edited Jul 04 '11 at 10:05

answered Jul 04 '11 at 09:19

Flinsch

4,296
1
20
29

Can you give to me an example? – markzzz Jul 04 '11 at 09:21
I've added a small example to my post that shows the creation and (random) sorting of a helper list. – Flinsch Jul 04 '11 at 09:30
Swapping elements like this doesn't give a uniform distribution, IIRC. See the link in my answer for a modified Fisher-Yates shuffle that *does* give a uniform distribution. – Jon Skeet Jul 04 '11 at 09:35
@Jon, I was not aware that the random sorting has to give a uniform distribution, However, one can apply any sorting algorithm to such a helper list I created in my example provided just to complete the example. I think the question was not to find the "best" random distribution. – Flinsch Jul 04 '11 at 09:38
@Flinsch: It's not as nicely "random" if there's a bias based on original position, is it? It's simple to shuffle in a better way, so why not do so? – Jon Skeet Jul 04 '11 at 09:41
@Jon, simple answer: The random sorting was not part of the problem. But just to make you happy: I'll edit my post. Thanks for the hint anyway. – Flinsch Jul 04 '11 at 09:45
Tried this solution : the list is not randomly ordered :( – markzzz Jul 04 '11 at 09:51
@Mark, what is the result instead and how is "randomly" defined in this specific case? – Flinsch Jul 04 '11 at 09:53
@Mark, does "the list is not randomly ordered" mean that the list stays unchanged or that the "random" result is always the same? In the latter case, you may provide a random seed for Random's constructor. – Flinsch Jul 04 '11 at 10:04
The list change :) But the random list result is always the same. Tried now with Random rnd = new Random(Int32.Parse(DateTime.Now.ToString("ffffff"))); , but the random result list is always the same. How can I fix this trouble? – markzzz Jul 04 '11 at 10:10
Solved. I did a cache on generating web pages :) – markzzz Jul 04 '11 at 10:36

How can I randomly ordering an IEnumerable<>?

3 Answers3

Update

Linked