How to map number in a range to another in the same range with no collisions?

Question

Effectively what I'm looking for is a function f(x) that outputs into a range that is pre-defined. Calling f(f(x)) should be valid as well. The function should be cyclical, so calling f(f(...(x))) where the number of calls is equal to the size of the range should give you the original number, and f(x) should not be time dependent and will always give the same output.

While I can see that taking a list of all possible values and shuffling it would give me something close to what I want, I'd much prefer it if I could simply plug values into the function one at a time so that I do not have to compute the entire range all at once.

I've looked into Minimal Perfect Hash Functions but haven't been able to find one that doesn't use external libraries. I'm okay with using them, but would prefer to not do so.

If an actual range is necessary to help answer my question, I don't think it would need to be bigger than [0, 2^24-1], but the starting and ending values don't matter too much.

Answer 1

You might want to take a look at Linear Congruential Generator. You shall be looking at full period generator (say, m=2²⁴), which means parameters shall satisfy Hull-Dobell Theorem.

Calling f(f(x)) should be valid as well.

should work

the number of calls is equal to the size of the range should give you the original number

yes, for LCG with parameters satisfying Hull-Dobell Theorem you'll get full period covered once, and 'm+1' call shall put you back at where you started. Period of such LCG is exactly equal to m

should not be time dependent and will always give the same output

LCG is O(1) algorithm and it is 100% reproducible

LCG is reversible as well, via extended Euclid algorithm, check Reversible pseudo-random sequence generator for details

Answer 2

Minimal perfect hash functions are overkill, all you've asked for is a function f that is,

1. bijective, and
2. "cyclical" (ie f^N=f)

For a permutation to be cyclical in that way, its order must divide N (or be N but in a way that's just a special case of dividing N). Which in turn means the LCM of the orders of the sub-cycles must divide N. One way to do that is to just have one "sub"-cycle of order N. For power of two N, it's also really easy to have lots of small cycles of some other power-of-two order. General permutations do not necessarily satisfy the cycle-requirement, of course they are bijective but the LCM of the orders of the sub-cycles may exceed N.

In the following I will leave all reduction modulo N implicit. Without loss of generality I will assume the range starts at 0 and goes up to N-1, where N is the size of the range.

The only thing I can immediately think of for general N is f(x) = x + c where gcd(c, N) == 1. The GCD condition ensures there is only one cycle, which necessarily has order N.

For power-of-two N I have more inspiration:

• f(x) = cx where c is odd. Bijective because gcd(c, N) == 1 so c has a modular multiplicative inverse. Also c^N=1, because φ(N)=N/2 (since N is a power of two) so c^φ(N)=1 (Euler's theorem).
• f(x) = x XOR c where c < N. Trivially bijective and trivially cycles with a period of 2, which divides N.
• f(x) = clmul(x, c) where c is odd and clmul is carry-less multiplication. Bijective because any odd c has a carry-less multiplicative inverse. Has some power-of-two cycle length (less than N) so it divides N. I don't know why though. This is a weird one, but it has decent special cases such as x ^ (x << k). By symmetry, the "mirrored" version also works.
  Eg x ^ (x >> k).
• f(x) = x >>> k where >>> is bit-rotation. Obviously bijective, and f^N(x) = x >>> Nk, where Nk mod N = 0 so it rotates all the way back to the unrotated position regardless of what k is.