Random copy of List

Question

Possible Duplicate:
Most efficient way to randomly “sort” (Shuffle) a list of integers in C#

How to effectively create a random copy of List<T>?

List<string> myList = new List<string>();
myList.Add("A");
myList.Add("B");
myList.Add("C");

// Now an extension method or a function which returns a random arrangement of myList:

List<string> GetRandomList()
{
    // List<string> result = new List<string>();
    // Random rnd = new Random();
    // Inside a loop
    // result.Add(myList[rnd.Next(1, myList.Count)]);
}

The extension method woud be public static List<T> Shuffle(List<T> this)

http://stackoverflow.com/questions/2459264/why-is-fisher-yates-the-most-useful-shuffling-algorithm — Mitch Wheat, May 02 '11 at 00:12
http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm — Mitch Wheat, May 02 '11 at 00:13
http://stackoverflow.com/questions/3343797/is-this-c-implementation-of-fisher-yates-shuffle-correct — Mitch Wheat, May 02 '11 at 00:13

score 4 · Accepted Answer · edited May 23 '17 at 12:03

4

You are looking for a Shuffle, there are various implementations out there, usually the Fisher-Yates shuffle.

Below a generic implementation taken from here:

public static void Shuffle<T>(this IList<T> list)  
{  
    Random rng = new Random();  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

Note that this re-orders the list in place, it's easy enough to refactor it to return a new list if that's what you want to do.

edited May 23 '17 at 12:03

Community

1
1

answered May 02 '11 at 00:07

BrokenGlass

158,293
28
286
335

Down side is it changes the list itself instead of returning a new shuffled list. – Xaqron May 02 '11 at 00:28

score 0 · Answer 2 · answered May 02 '11 at 00:07

0

public List<T> Random<T>(this IEnumerable<T> collection)
{
    return collection.OrderBy(i => Guid.NewGuid()).ToList();
}

Thanks to Jeff Atwood for this solution.

answered May 02 '11 at 00:07

Daniel A. White

187,200
47
362
445

Will that only call the delegate once per item in the collection, or multiple times? Let's say we wanted to shuffle the list `{1, 2, 3}`, and the OrderBy implementation decided to compare `1` vs. `2`, and then `1` vs `3`. It would call the delegate, which would call `NewGuid`, but when it wanted to compare `1` against two different numbers, would it call `NewGuid` only once, or multiple times? If it calls multiple times, then this does not produce a good shuffle, and the final order depends greatly on the implementation of OrderBy. – David Yaw May 02 '11 at 00:55
It will call it multiple times. – Daniel A. White May 02 '11 at 01:12
1

See http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html for an interesting analysis of the results of doing shuffles in a bad way. In that case, the comparison function (`int Compare(object a, object b)`) returned a random number 1 or -1. Because of the way the sort was implemented, the resulting ordering was not random, and it varied by sort implementation. – David Yaw May 02 '11 at 04:43

Random copy of List

2 Answers2