I would like to generate a sequence of n
random integers in the interval [1,n]
without duplicates, i.e. a permutation of the sequence [1,2,...,n]
with O(log(n))
space complexity (or a polynomial function of log(n)
).
One hint is that I can assume that I have a family of l-wise uniform hash functions h : [n] -> [k]
(with l<=n
) such that for any y_1, y_2,..., y_l
and any distinct x_1, x_2,..., x_l
:
P(h(x_1) = y_1 and h(x_2) = y_2 and ... and h(x_l) = y_l) = 1/(k^l)
My first idea was to use the hash function to generate the i-th element of the sequence, i.e. x_i = h(i)
, check if x_i
is already used (has already been returned by the hash function for some 0<j<i
) and if it's the case increment x_i
by 1 and check again until x_i
is a new number. My problem is I can not have a vector of booleans of size n
to check if the value x_i
is already used. And if I do a recursive function to get the j-th value I will need at some point O(n log2(n))
bits...
I also found here that pseudorandom generator like Linear congruential generator can be used for this kind of problem with something like x_i+1 = (a*x_i + c)%n + 1
but I am not sure to understand how to choose a
for any value of n
to have a period of length n
.
Aucun commentaire:
Enregistrer un commentaire