首先，定义两个整数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 ？ 我是不是能够通过搜索谷歌，还是我自己天真的努力，找到一个。
有一种算法来编码，并与给定的固定的所有组合的字典顺序解码的组合成其数目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;
}
很抱歉，我对你所要求的，现在问题的算法，但我相信这将是一个很好的锻炼，试图了解我做什么上面。 事实是，这是我的课程“算法设计与分析”教的算法之一，这就是为什么我有它预先写好。
这是你（和我）需要什么：
hash()地图k-tuples从[1..n]到集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;
}
