c++ - 哈希函数和随机排列

Question

看完this问题。我想知道是否有可能使用 O(1) 空间，我们可以使用类似双重哈希的方法生成具有均匀分布的序列 [1...n] 的随机排列吗？

我用序列 [1,2,3,4,5] 的一个小例子尝试了这个并且它有效。但是对于更大的集合来说，它的规模是失败的。

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;
    }
}

Answer 1

您可以尝试另一种方法。

1. 取 GCD(P, N) == 1 的任意整数 P，其中 GCD(P,
N) 是 greatest common divisor P 和 N(例如 GCD(70, 42) == 14，GCD(24, 35) == 1).
2. 获取序列K[i]::= (P * i) mod N + 1，i从1到 N
3. 已证明序列 K[i] 枚举了介于1 和 N 没有重复(实际上 K[N + 1] == K[1] 但这不是问题，因为我们只需要前 N 个数字)。

如果您可以使用 Euclidean algorithm 有效地生成具有均匀分布(例如具有良好随机函数)的此类数字 P计算复杂度为 O(log(N)) 的 GCD，您会得到想要的结果。