CODEWITHSUNDEEP
c#.netalgorithmrandomshuffle
Patrick M
Patrick M

Reputation: 109

Shuffle to cover all possible permutations

The Random object in the .NET framework takes a 32 bit integer as the seed. This means any shuffling algorithm that uses the Random object is limited to (at most) 4 billion possible shuffles (assuming the shuffle is deterministic in accordance to the random sequence, which I can't imagine why it wouldn't be). This means that once a collection exceeds 13 elements it's guaranteed that the shuffle will not cover all possible permutations. As the collection size gets further from this size the subset of possible permutations covered by the shuffle becomes more and more insignificant.

4 billion is a (subjectively) large number but if you're generating multiple "random" permutations of a collection the chance of a duplicate becomes much larger than it should be (particularly so when you consider birthday paradox/pigeonhole principle).

Is there simple any way around this that doesn't involve me implementing my own random number generator?

Upvotes: 3

Views: 325

Answers (2)

pjs
pjs

Reputation: 19855

You could use one of the freely available ports of Mersenne Twister to C#. MT19937 has a 19937 bit state space, and while you can choose to seed it with a single int, full state seeding is also available if you have a suitable source of entropy from which to feed it.

Upvotes: 0

Ananke
Ananke

Reputation: 1230

I wouldn't recommend creating your own random number generator (RNG). The theory behind them is quite solid. If you need something that's 'more random' then you need to use a cryptographically secure RNG. To use the default generator provided by the .Net framework:

using System.Security.Cryptography;

var generator = RandomNumberGenerator.Create();

You can use this to get some random bytes which you can convert to an int, or some other value type.

Upvotes: 1

Related Questions