We are searching for the permutation function $P_{n,s}(i)$ that computes the $i$th value of an $n$-length permutation ($n,s,i \in N, ~ i < n$) (without storing the entire ordered array), and its inverse $P^{-1}_{n,s}(i)$, with the following requirements:
- both functions are fast (ideally with $O(1)$ or $O(\log n)$ time and space complexity)
- for different values of the meta parameter $s$, we get different permutations (like a seed)
- the permutation is random-like (quality randomness is a nice-to-have, but not required)
The first requirement is simply satisfied by the identity permutation: $P_{n,s}(i) := i$.
The first two requirements are satisfiable, for example, with "mirroring" $s$-sized blocks:
$$ P_{n,s}(i) := \begin{cases} i+s-1-(i \mod s) & \mbox{if } i < n \div s \\ \mbox{(some recursion...)} & \mbox{else} \end{cases} $$
For example ($s = 3$):
$$ \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\ 2 & 1 & 0 & 5 & 4 & 3 & 8 & \cdots \end{pmatrix} $$
(Then, we can combine a lot of similar tricks for achieving more mix-up, but we still far from which could be called random.)
Is there an efficient method for independently calculating the values of a random permutation?
Cryptography is our friend, format-preserving encryption is a suitable solution to the above problem. For example, a k-bit block cipher algorithm can act as a reversible permutation for $n_u = 2^k$. For any $n ~~ (2^{k-1} \lt n \le 2^k = n_u)$ we can compute the value with cycle walking.