2

看完这个问题。我想知道是否有可能使用 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;
    }
}
4

3 回答 3

3

您可以尝试另一种方法。

  1. 取任意整数 P，GCD(P, N) == 1它GCD(P, N)是和的最大公约数（例如， ）。PNGCD(70, 42) == 14GCD(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 个数字）。

如果您可以使用欧几里德算法P以 O(log(N)) 复杂度计算 GCD，从而有效地生成具有均匀分布的此类数字（例如，具有良好的随机函数），您将得到您想要的。

于 2012-09-17T15:56:05.390 回答
1

如果没有一些随机性，就不可能生成“随机”排列。这甚至没有意义。您的代码每次都会生成相同的排列。

我怀疑您打算每次都选择不同的两个随机散列函数。但即使这样也不能使用像你这样的散列函数（a +/- k%b对于随机选择的 a，b），因为你需要O(n log n)一些随机性来指定一个排列。

于 2012-09-17T15:55:23.663 回答
0

我不确定问题是什么。如果你想要一个随机排列，你想要一个随机数生成器，而不是一个散列函数。哈希函数是（并且必须是）确定性的，因此它不能用于“随机”排列。哈希不是任何事物的排列。

我不认为随机排列可以是 O(1) 空间。您必须以某种方式跟踪已使用的元素。

于 2012-09-17T15:55:49.130 回答