3

首先，定义两个整数N和K，其中N >= K，都在编译时已知。例如：N = 8和K = 3。

接下来，定义一组整数[0, N)（或者[1, N]如果这使答案更简单）并将其命名为S. 例如：{0, 1, 2, 3, 4, 5, 6, 7}

S带有元素的子集的数量K由公式给出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;
}

很抱歉，我有一个算法可以解决您现在要求的问题，但我相信尝试理解我在上面所做的事情将是一个很好的练习。事实是，这是我在“算法的设计和分析”课程中教授的算法之一，这就是我预先编写它的原因。

于 2013-01-04T16:30:28.827 回答
1

这就是你（和我）需要的：

hash()映射k-tuplesfrom[1..n]到 set 1..C(n,k)\subset N。努力是k减法（O(k)无论如何都是一个下限，请参见上面 Strandjev 的评论）：

// bino[n][k] is (n "over" k) = C(n,k) = {n \choose k}
// these are assumed to be precomputed globals

int hash(V a,int n, int k) {// V is assumed to be ordered, a_k<...<a_1
  // hash(a_k,..,a_2,a_1) = (n k) - sum_(i=1)^k (n-a_i   i) 
  // ii is "inverse i", runs from left to right

  int res = bino[n][k];
  int i;

  for(unsigned int ii = 0; ii < a.size(); ++ii) {
    i = a.size() - ii;   
    res = res - bino[n-a[ii]][i];
  }
  return res;
}
于 2013-12-07T14:07:56.927 回答