samedi 17 avril 2021

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

I want to construct a bijective function f(k, seed) from [1,n] to [1,n] where 1<=k<=n and 1<=f(k, seed)<=n for each given seed. It actually returns 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, seed)'s time complexity to be O(1) and space complexity to be < O(n) 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.




Aucun commentaire:

Enregistrer un commentaire