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を取得i1N
  3. K[i]sequenceは 1 から N までのすべての数字を繰り返しなしで列挙することが証明されています (実際にK[N + 1] == K[1]は、最初の N 個の数字だけが必要なため、これは問題ではありません)。

ユークリッド アルゴリズムPを使用して O(log(N)) の複雑さで GCD を計算し、均一な分布 (たとえば、適切なランダム関数) でこのような数値を効率的に生成できる場合、必要なものが得られます。

于 2012-09-17T15:56:05.390 に答える
1

ある程度のランダム性がなければ、「ランダムな」順列を生成することはできません。意味がありません。コードは毎回同じ順列を生成します。

毎回異なる 2 つのランダム ハッシュ関数を選択するつもりだと思われます。しかし、順列を指定するには少しのランダム性a +/- k%bが必要なため、( a,b がランダムに選択された場合) のようなハッシュ関数を使用しても機能しません。O(n log n)

于 2012-09-17T15:55:23.663 に答える
0

質問の意味がわかりません。ランダム順列が必要な場合は、ハッシュ関数ではなく、乱数ジェネレーターが必要です。ハッシュ関数は決定論的である (そしてそうでなければならない) ため、「ランダムな」順列には使用できません。そして、ハッシュは何の順列でもありません。

ランダムな順列が O(1) 空間になるとは思いません。すでに使用されている要素を追跡する必要があります。

于 2012-09-17T15:55:49.130 に答える