Shuffle a Collection

Aamir Mahmood

Hi everyone,

I have to write a function to shuffle a collection. If anyone has any idea
on how to implement it please share with me.

The signature of function is:
ICollection Shuffle(ICollection c);

Thanks.

AM

Arne Vajhøj

Aamir Mahmood wrote:
> I have to write a function to shuffle a collection. If anyone has any idea
> on how to implement it please share with me.
>
> The signature of function is:
> ICollection Shuffle(ICollection c);

2.0+ style:

public class Util<T>
{
private static Random rng = new Random();
public static ICollection<T> Shuffle(ICollection<T> c)
{
T[] a = new T[c.Count];
c.CopyTo(a, 0);
byte[] b = new byte[a.Length];
rng.NextBytes(b);
Array.Sort(b, a);
return new List<T>(a);
}
}

1.x style:

public class Util
{
private static Random rng = new Random();
public static ICollection Shuffle(ICollection c)
{
object[] a = new object[c.Count];
c.CopyTo(a, 0);
byte[] b = new byte[a.Length];
rng.NextBytes(b);
Array.Sort(b, a);
return new ArrayList(a);
}
}

Arne

Aamir Mahmood

I have already implemented it, any comments/suggestions on my implementation
are welcome:
----------------------------------------------------------------------
public static ICollection Shuffle(ICollection c) {
if (c == null || c.Count <= 1) {
return c;
}

byte[] bytes = new byte[4];
RNGCryptoServiceProvider cRandom = new RNGCryptoServiceProvider();
cRandom.GetBytes(bytes);

int seed = BitConverter.ToInt32(bytes, 0);
Random random = new Random(seed);

ArrayList orig = new ArrayList(c);
ArrayList randomized = new ArrayList(c.Count);
for (int i = 0; i < c.Count; i++) {
int index = random.Next(orig.Count);
randomized.Add(orig[index]);
orig.RemoveAt(index);
}
return randomized;
}
------------------------------------------------



Thanks.

AM


"Aamir Mahmood" <aamirmahmood@gmail.com> wrote in message
news:%23xjW$hp6HHA.5984@TK2MSFTNGP04.phx.gbl...
> Hi everyone,
>
> I have to write a function to shuffle a collection. If anyone has any
> idea on how to implement it please share with me.
>
> The signature of function is:
> ICollection Shuffle(ICollection c);
>
> Thanks.
>
> AM
>

Jon Skeet [C# MVP]

On Aug 30, 3:08 am, Arne Vajhøj <a...@vajhoej.dk> wrote:
> Aamir Mahmood wrote:
> > I have to write a function to shuffle a collection. If anyone has any idea
> > on how to implement it please share with me.
>
> > The signature of function is:
> > ICollection Shuffle(ICollection c);
>
> 2.0+ style:

<snip>

Shuffling by sorting is going to be (at best) O(n log n). It's fairly
easy to do it as O(n)... admittedly it's more code, but for large
collections it could be significant.

Jon

Arne Vajhøj

Jon Skeet [C# MVP] wrote:
> On Aug 30, 3:08 am, Arne Vajhøj <a...@vajhoej.dk> wrote:
>> Aamir Mahmood wrote:
>>> I have to write a function to shuffle a collection. If anyone has any idea
>>> on how to implement it please share with me.
>>> The signature of function is:
>>> ICollection Shuffle(ICollection c);
>> 2.0+ style:
>
> <snip>
>
> Shuffling by sorting is going to be (at best) O(n log n). It's fairly
> easy to do it as O(n)... admittedly it's more code, but for large
> collections it could be significant.

True.

The advantage of the sorting method is that the methods validity
is rather obvious.

Arne

Yaya

You can find a nice example here:
Yair Levinson's Blog on .NET