I am searching for a function which has input a number X from 0, 1, 2, 3....N. Its result should be Y which belongs to a permuted version of the input's set.
The results must be unique and thus all of them are generated. Now, I am aware / don't mind that for all lists of 0, 1, .... N, the same results will be outputed. This is expected and fine, I just want the results to be the input shuffled around.
For example: N = 10. I call the function 10 times with: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and it might return 7, 1, 5, 2, 9, 8, 3, 0, 4, 6.
I found this function :
function perm( x )
{
return x * 833 % N;
}
Where 833 can be any large-ish prime number. This makes good-ish results but they are always with a repeating pattern. See for N = 16: 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13
Imagine it looks like 3 shark fins. Basically my question is, how do I make a function that does what I have described but with a more chaotic shuffle?
I CANNOT pregenerate a permutation of 0, 1...N.
One approach is to pick some big number $n$, say of order $N!/2$. Use that to find the $n^{\text{th}}$ lexicographic permutation of $N$. The first number is $\lfloor \frac n{(N-1)!} \rfloor$. Then form $n'=n-\lfloor \frac n{(N-1)!} \rfloor$ The second number is the $\lfloor \frac {n'}{(N-2)!} \rfloor$th one of what is left (so increment by $1$ if higher than the first). Keep going, reducing the factorial in the denominator by $1$ each time.