Collection Randomization using Extension Method

Question

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

I want to create an extension method which should shuffle the items in the collection.

Can i improve the following?

public static IList<T> RandomList<T>(this IList<T> source)
{
   if (source.Count <= 0) throw new ArgumentException("No Item to Randomize");  

            for (int i =source.Count-1 ; i>0; i--)
            {
                int RandomIndex = Rnd.Next(i + 1);
                T temp = source[i];
                source[i] = source[RandomIndex];
                source[RandomIndex] = temp;
            }

            return source;
 }

Yes, see http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm — jason, Dec 14 '09 at 15:36

score 5 · Answer 1 · answered Dec 14 '09 at 15:58

5

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
{
   foreach(var item in source.OrderBy(i => Guid.NewGuid()))
   {
      yield return item;
   }
}

answered Dec 14 '09 at 15:58

BFree

102,548
21
159
201

score 1 · Answer 2 · answered Dec 14 '09 at 15:38

1

I think is good enough as long as you know Random is not very random.

the Random class is viable for use in simple games and other non-scientific fields. Do not use it for cryptography.

answered Dec 14 '09 at 15:38

Jorge Córdoba

51,063
11
80
130

`Random` is for (almost) all intents and purposes random. – jason Dec 14 '09 at 16:14

score 1 · Answer 3 · answered Dec 14 '09 at 15:55

Generally you should avoid changing the list and instead return a new list. Even better would be to return IEnumerable to be consistent with other Extension methods and LINQ.

Try this.

public static class RandomizeExtensionMethods
{
    private static readonly Random _random = new Random();

    public static IEnumerable<T> Randomize<T>(this IList<T> enumerable)
    {
        if (enumerable == null || enumerable.Count == 0)
        {
            return new List<T>(0);
        }

        return RandomizeImpl(enumerable);           
    }

    public static IEnumerable<T> RandomizeImpl<T>(this IList<T> enumerable)
    {
        var indices = new int[enumerable.Count];
        for(int i=0; i<indices.Length; i++)
        {
            indices[i] = i;
        }

        lock (_random)
        {
            for (int i = 0; i < indices.Length - 1; i++)
            {
                int j = _random.Next(i, indices.Length);
                int swap = indices[j];
                indices[j] = indices[i];
                indices[i] = swap;
            }
        }

        for(int i=0; i<indices.Length; i++)
        {
            yield return enumerable[indices[i]];
        }
    }
}

Nice implementation @Sam. I like the forethought to swap the indicies instead of the elements themselves in case the elements are expensive to copy. — Marty Neal, Jun 09 '10 at 01:36

Craig Gidney · Accepted Answer · 2009-12-14T16:03:55.990

There are a few issues I would have with this method:

It should check for a null argument.
It should not check for a 0-length list.
Avoid side-effects. Create a new list for the shuffled elements, instead of modifying the existing one.
Don't hide dependencies. Pass the random number generator in as an argument.
Use a more descriptive name than 'RandomList'.
The input type can be generalized to IEnumerable.
The method can be changed to an enumerator [generalize the output type].

Essentially:

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

    //copy
    var result = source.ToList();
    //shuffle the copy
    for (int i = result.Count - 1; i > 0; i--)
    {
        int RandomIndex = generator.Next(i + 1);
        T temp = result[i];
        result[i] = result[RandomIndex];
        result[RandomIndex] = temp;
    }

    return result;
}

I didn't generalize the output type. You can do that if you want.

score 0 · Answer 5 · answered Dec 14 '09 at 15:38

Having it return itself is somewhat redundant. If you were returning a deep copy of the list, sure; and in that case it should get called "GetShuffledCopy()" or something similar. If you're acting on the list itself, it should be a void return and be called something like "Shuffle()"

-Oisin

Collection Randomization using Extension Method

5 Answers5