# complexity theory – Generating a fast permutation function over an integer range

Is there a way to generate a bijection over integers $$F : (0..n) rightarrow (0..n)$$ that satisfies the properties:

• $$n$$ is arbitrarily chosen and can be any positive integer
• $$F$$ generates a pseudorandom, potentially biased permutation of its domain
• $$F$$ is seedable and can be easily influenced to generate a different random permutation
• The computational complexity of computing $$F(i)$$ for all $$i$$ is better than $$O(n)$$ (ideally, $$O(1)$$)
• The computational complexity of generating $$F$$ itself is better than $$O(n)$$ (ideally, $$O(1)$$)

I have looked at Fisher-Yates, LCGs, LFSRs, minimal perfect hashing, and unique-permutation hashing, and haven’t found anything that could tell me if this is possible.

I am mainly interested in this because I want a “scrollable” output of randomly-permuted integers, of which there may be an impractically large number to compute the entire permutation at once, but which will eventually all be consumed.

To optimize memory usage, it would be preferable to return a fixed number $$k$$ at a time. If such an $$F$$ exists, the algorithm could then fetch the next $$k$$ integers, and so on until the permutation is exhausted.