Construct a bijective function to map arbitrary integer from [1, n] to [1, n] randomly

Question

I want to construct a bijective function f(k, n, seed) from [1,n] to [1,n] where 1<=k<=n and 1<=f(k, n, seed)<=n for each given seed and n. The function actually should return a value from a random permutation of 1,2,...,n. The randomness is decided by the seed. Different seed may corresponds to different permutation. I want the function f(k, n, seed)'s time complexity to be O(1) for each 1<=k<=n and any given seed.

Anyone knows how can I construct such a function? The randomness is allowed to be pseudo-randomness. n can be very large (e.g. >= 1e8).

Answer 1

No matter how you do it, you will always have to store a list of numbers still available or numbers already used ... A simple possibility would be the following

const avail = [1,2,3, ..., n];

let random = new Random(seed)

function f(k,n) {
  let index = random.next(n - k);
  let result = avail[index]
  avail[index] = avail[n-k];
}

The assumptions for this are the following

• the array avail is 0-indexed
• random.next(x) creates an random integer i with 0 <= i < x
• the first k to call the function f with is 0
• f is called for contiguous k 0, 1, 2, 3, ..., n

The principle works as follows:

avail holds all numbers still available for the permution. When you take a random index, the element at that index is the next element of the permutation. Then instead of slicing out that element from the array, which is quite expensive, you just replace the currently selected element with the last element in the avail array. In the next iteration you (virtually) decrease the size of the avail array by 1 by decreasing the upper limit for the random by one.

I'm not sure, how secure this random permutation is in terms of distribution of the values, ie for instance it may happen that a certain range of numbers is more likely to be in the beginning of the permuation or in the end of the permutation.

Answer 2

A simple, but not very 'random', approach would be to use the fact that, if a is relatively prime to n (ie they have no common factors), then

x-> (a*x + b)%n

is a permutation of {0,..n-1} to {0,..n-1}. To find the inverse of this, you can use the extended euclidean algorithm to find k and l so that

1 = gcd(a,n) = k*a+l*n

for then the inverse of the map above is

y -> (k*x + c) mod n
where c = -k*b mod n

So you could choose a to be a 'random' number in {0,..n-1} that is relatively prime to n, and b to be any number in {0,..n-1}

Note that you'll need to do this in 64 bit arithmetic to avoid overflow in computing a*x.