I am searching a fast pseudo-random permutation function with the following requirements.
Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset in order.
In more detail, we need an $n$-length ordered value set $V$ splitted to $k$ (contiguous) partitions. Partitioning is represented by (1) the function $part(v): V \to N$ wich returns with the partition index of the value $v$, and (2) the function $rng(p): N \to V_2$ ($p \in N$, the partition index) which returns with the bounds of the partition associated to $p$. In the same time we need the permutation function $perm(v): V \to V$, where partitions are stable:
$$v_1 < v_2 ~ ~ \land ~ ~ part(v_1) = part(v_2) ~ ~ \implies ~ ~ perm(v_1) < perm(v_2)$$
Partition number is predefined, there can be empty partitions. Permutation and partitioning must be key based: with a different key we get totally different results.
We are searching for such a $part(v)$, $rng(p)$ and $perm(v)$ (and $perm'(v)$, if possible)
It would be nice if partitions could be predefined, or at least controlled in some way (e. g. binomial distribution). It would be also nice if v (∈ V) could have an arbitrary length. The algorithms should be as fast as possible. Cryptographical secureness is a nice-to-have.
Here is an example visualization:
Where (indices from $0$):
- $part(3) = 0$
- $part(C) = 2$
- $rng(1) = [4, A]$
- $perm(4) = 1$
- $perm'(4) = C$