CODEWITHSUNDEEP
c++algorithmhashpermutation
andre
andre

Reputation: 7249

Hash functions and random permutation

After reading this question. I was wondering is it possible using O(1) space can we generate a random permutation of the sequence [1...n] with a uniform distribution using something like double hashing?

I tried this with a small example for the sequence [1,2,3,4,5] and it works. But it fails for scale for larger sets.

int h1(int k) {
    return 5 - (k % 7);
}

int h2(int k) {
    return (k % 3) + 1;
}

int hash(int k, int i) {
    return (h1(k) + i*h2(k)) % size;
}

int main() {
    for(int k = 0; k < 10; k++) {
        std::cout << "k=" << k <<  std::endl;
        for(int i = 0; i < 5; i++) {
            int q = hash(k, i);
            if(q < 0) q += 5;
            std::cout << q;
        }
        std::cout << std::endl;
    }
}

Upvotes: 2

Views: 1610

Answers (3)

UnknownGosu
UnknownGosu

Reputation: 864

You can try another approach.

  1. Take arbitrary integer number P that GCD(P, N) == 1 where GCD(P, N) is greatest common divisor of P and N (e.g. GCD(70, 42) == 14, GCD(24, 35) == 1).
  2. Get sequence K[i] ::= (P * i) mod N + 1, i from 1 to N
  3. It's proven that sequence K[i] enumerates all numbers between 1 and N with no repeats (actually K[N + 1] == K[1] but that is not a problem because we need only first N numbers).

If you can efficiently generate such numbers P with uniform distribution (e.g. with a good random function) with using Euclidean algorithm to calculate GCD in O(log(N)) complexity you'll get what you want.

Upvotes: 3

James Kanze
James Kanze

Reputation: 153977

I'm not sure what the question is. If you want a random permutation, you want a random number generator, not a hash function. A hash function is (and must be) deterministic, so it cannot be used for a "random" permutation. And a hash is not a permutation of anything.

I don't think that a random permutation can be O(1) space. You've got to keep track somehow of the elements which have already been used.

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

It is not possible to generate a "random" permutation without some randomness. It doesn't even make sense. Your code will generate the same permutation every time.

I suspect you intend that you pick a different two random hash functions every time. But even that won't work using hash functions like you have (a +/- k%b for a,b chosen at random), as you need O(n log n) bits of randomness to specify a permutation.

Upvotes: 1

Related Questions