[thethirdone]

What "O(1)-state shuffle" could you possibly be talking about? It takes `O(nlogn)` space to store a permutation of list of length n. Any smaller and some permutations will be unrepresentable. I am very aware of this because shuffling a deck of cards correctly on a computer requires at least 200 random bits.

If the requirements are softer than "n random permutations", there might be a lot of potential solutions. It is very easy to come up with "n permutations" if you have no requirements on the randomness of them. Pick the lowest `k` such that `n < k!`, permute the first k elements leaving the rest in place, and now you have n distinct permutations storeable in `O(log(n)` (still not O(1) but close).

I know this is not really your point, but misusing `O(1)` is a huge pet peeve of mine.

[hansvm]

It's O(1) if you don't need access to every permutation (common in various monte carlo applications). 64-128 bits of entropy is good enough for a lot of applications, and that's all you get from any stdlib prng, so that's what I was comparing it to.

Those sorts of applications would tend to not work well with a solution leaving most elements in the same place or with the same relative ordering.