Having natural numbers 1 to N (N is around 1e7), I dream of function that would reorder the set in a way, defined by a rather short set of parameters, compared to the range of values.
For N = 2^i - 1 this can be just bit reordering, thus, a set of only i values of 0..i defines the mutation.
I am looking for a similarly beautiful way, applicable to an arbitrary N.
The bit reordering example. 8 values: 0..7 are encoded with 3 bits: 000 – 111. To reorder that set I stored each bit's new position. Take an array [0,1,2] and randomly reorder it, then store the result as the permutation key. I.e. [1,0,2] will reorder 8 values like so:
210 201
0: 000 - 000 :0
1: 001 - 010 :2
2: 010 - 001 :1
3: 011 - 011 :3
4: 100 - 100 :4
5: 101 - 110 :6
6: 110 - 101 :5
7: 111 - 111 :7
Simple way which don't consume memory is to multiply each number by the constant which is coprime with N, then calculate the remainder of division by N like this (example in Java):
static int reorder(int input, int N) {
// 15485863 is prime, thus coprime with any lesser N
return (int) ((input * 15485863L) % N);
}
Testing with N = 10345560:
public static void main(String[] args) {
int N = 10345560;
int[] source = IntStream.range(0, N).toArray();
int[] reordered = IntStream.of(source).map(i -> reorder(i, N)).toArray();
// Check that all reordered numbers are within 0..N-1
assert IntStream.of(reordered).allMatch(i -> i >= 0 && i < N);
// Check that all numbers are different
assert IntStream.of(reordered).distinct().count() == N;
}
The advantage is that you don't need intermediate memory to store all the numbers: you may process them in streaming way (for example, reading from one file and writing the result to another).
The disadvantage is that for supplied parameter you have to test that it's coprime with N and reject or adjust it if it's not.