0

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).

Daniel
  • 1,783
  • 2
  • 15
  • 25
  • How big is n? If it is small you could implement f via a look up table that is manufactured by shuffling {1,..n} – dmuir Apr 17 '21 at 08:08
  • @dmuir n can be very large, e.g. >= 1e8. – Daniel Apr 17 '21 at 08:14
  • 1
    You're likely looking for a [block cipher](https://en.wikipedia.org/wiki/Block_cipher). [This question](https://crypto.stackexchange.com/q/504) and its answers may be of interest. – Mark Dickinson Apr 17 '21 at 11:06
  • 1
    Possible duplicate of https://stackoverflow.com/q/3910101/270986 ? – Mark Dickinson Apr 17 '21 at 11:08
  • @MarkDickinson I will check it out. Thanks! – Daniel Apr 17 '21 at 11:09
  • Does this answer your question? [How to generate a predictable shuffling of a sequence without generating the whole sequence in advance?](https://stackoverflow.com/questions/3910101/how-to-generate-a-predictable-shuffling-of-a-sequence-without-generating-the-who) – Peter O. Apr 17 '21 at 15:50
  • @PeterO. The block cipher part in the post seems very related. – Daniel Apr 18 '21 at 03:05

2 Answers2

0

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.

derpirscher
  • 14,418
  • 3
  • 18
  • 35
  • The 3rd and 4th assumptions are not true. Actually I need to call `f(k, n, seed) ` in different order of `k`, and will call many `f(k, n, seed)` for different `k` parallelly. – Daniel Apr 17 '21 at 09:55
  • Well, then the only possibility is to precreate the permutation. – derpirscher Apr 17 '21 at 10:35
  • 1
    *No matter how you do it, you will always have to store a list of numbers still available or numbers already used*: as the comments under the question demonstrate, this is not true. – President James K. Polk Apr 17 '21 at 14:21
0

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.

dmuir
  • 4,211
  • 2
  • 14
  • 12
  • Yes, this method is not very 'random', and I have tried it and find that even for huge prime chosen for `a`, the resulting sequence can have some obvious pattern. e.g., roughly increasing periodically for 1-100 in the resulting sequence. – Daniel Apr 17 '21 at 11:43
  • If you had some control over n, better methods might be available. For example if n was a power of two it would be simple to split any number in {1,..n} into smaller chunks, permute each chunk and recombine. Or, if n had a fair number of factors one could perhaps the chinese remainder theorem to break it into chunks. – dmuir Apr 17 '21 at 12:10