[ridiculous_fish]

This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations.

There are "N choose k" combinations, which in the worst case (k = N/2) grows as ~ 2^N. The number of combinations quickly outstrips the number of possible states of the LCG, and most combinations will never be found. For example, we have a list of length 16 and wish to choose 8. We have a choice of 16 distinct seeds, so there are only 16 different combinations (out of 12870 possible) that we can get for any given LCG.

[mrdrozdov]

By randomly adding skips, can definitely get to all possible combinations even with only 16 seeds (since skips can be seeded from a much larger space), although there could be a speed implication.

[vrfcodf]

Good point. You would get different sequences by choosing different constants for the generator though, but you couldn't cover all of them by a longshot.

[mcherm]

And this inability to cover all possible sequences has real-world implications.

https://www.cigital.com/papers/download/developer_gambling.p...

http://superuser.com/questions/712551/how-are-pseudorandom-a...