3

まず、2つの整数Nとを定義します。KここでN >= K、両方ともコンパイル時に認識されます。例：N = 8およびK = 3。

次に、整数のセットを定義し[0, N)（または[1, N]、それによって答えが簡単になる場合）、それを呼び出しますS。例えば：{0, 1, 2, 3, 4, 5, 6, 7}

SwithK要素のサブセットの数は式で与えられC(N, K)ます。例

私の問題はこれです：それらのサブセットのための完全な最小ハッシュを作成します。サンプルのハッシュテーブルのサイズはC(8, 3)またはになります56。

順序は気にせず、ハッシュテーブルに56個のエントリがあり、K整数のセットからハッシュをすばやく決定できることだけです。可逆性も気にしません。

ハッシュの例：hash({5, 2, 3}) = 42。（42という数字は重要ではありませんが、少なくともここでは重要ではありません）

Nおよびの任意の値で機能するこのための一般的なアルゴリズムはありKますか？私はグーグルを検索することによって、または私自身の素朴な努力によってそれを見つけることができませんでした。

4

2 に答える 2

3

与えられた固定のすべての組み合わせの辞書式順序で組み合わせをその数にコード化およびデコードするアルゴリズムがありますK。Nアルゴリズムは、組み合わせのコードとデコードの両方に対して線形です。どんな言語に興味がありますか？

編集：これはc ++のサンプルコードです（要素を持つものとは対照的に、n個の要素のすべての組み合わせのシーケンスで組み合わせの辞書式順序を見つけますkが、本当に良い出発点です）：

typedef long long ll;

// Returns the number in the lexicographical order of all combinations of n numbers
// of the provided combination. 
ll code(vector<int> a,int n)
{
    sort(a.begin(),a.end());
    int cur = 0;
    int m = a.size();

    ll res =0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i] == cur+1)
        {
            res++;
            cur = a[i];
            continue;
        }
        else
        {
            res++;
            int number_of_greater_nums = n - a[i];
            for(int j = a[i]-1,increment=1;j>cur;j--,increment++)
                res += 1LL << (number_of_greater_nums+increment);
            cur = a[i];
        }
    }
    return res;
}
// Takes the lexicographical code of a combination of n numbers and returns the 
// combination
vector<int> decode(ll kod, int n)
{
    vector<int> res;
    int cur = 0;

    int left = n; // Out of how many numbers are we left to choose.
    while(kod)
    {
        ll all = 1LL << left;// how many are the total combinations
        for(int i=n;i>=0;i--)
        {
            if(all - (1LL << (n-i+1)) +1 <= kod)
            {
                res.push_back(i);
                left = n-i;
                kod -= all - (1LL << (n-i+1)) +1;
                break;
            }
        }
    }
    return res;
}

申し訳ありませんが、現在あなたが求めている問題のアルゴリズムを持っていますが、私が上記で何をしているのかを理解することは良い練習になると思います。真実は、これが「アルゴリズムの設計と分析」のコースで教えるアルゴリズムの1つであり、それが私が事前に作成した理由です。

于 2013-01-04T16:30:28.827 に答える