完美最小散列数学组合 [英] Perfect minimal hash for mathematical combinations
问题描述
首先,定义两个整数 N
和 K
,其中 N'GT; = K
,无论是在编译时已知的。例如: N = 8
和 K = 3
First, define two integers N
and K
, where N >= K
, both known at compile time. For example: N = 8
and K = 3
.
接下来,定义一组整数 [0,N)
(或 [1,N]
如果说的使答案更简单),并将其命名为取值
。例如: {0,1,2,3,4,5,6,7}
Next, define a set of integers [0, N)
(or [1, N]
if that makes the answer simpler) and call it S
. For example: {0, 1, 2, 3, 4, 5, 6, 7}
取值
的子集与 K
元素的数量由下式给出Ç (N,K)
。示例
The number of subsets of S
with K
elements is given by the formula C(N, K)
. Example
我的问题是这样的:创建一个完美的哈希值最小为这些子集。这个例子哈希表的大小将是 C(8,3)
或 56
。
My problem is this: Create a perfect minimal hash for those subsets. The size of the example hash table will be C(8, 3)
or 56
.
我不关心排序,只是有是哈希表中的56项,而且我可以从一组 K
整数迅速确定哈希。我也不在乎可逆性。
I don't care about ordering, only that there be 56 entries in the hash table, and that I can determine the hash quickly from a set of K
integers. I also don't care about reversibility.
例如哈希:哈希({5,2,3})= 42
。 (数目42是不重要的,至少不是这里)
Example hash: hash({5, 2, 3}) = 42
. (The number 42 isn't important, at least not here)
有没有一个通用的算法,这种将工作与 N
和 K
的任何值?我没能找到一个通过搜索谷歌,还是我自己天真的努力。
Is there a generic algorithm for this that will work with any values of N
and K
? I wasn't able to find one by searching Google, or my own naive efforts.
推荐答案
有一个算法,以code和德codeA结合到其在给定的固定<$ C所有组合的字典顺序号$ C> K 。该算法是线性的,以 N
为code和组合去code。什么语言你有兴趣吗?
There is an algorithm to code and decode a combination into its number in the lexicographical order of all combinations with a given fixed K
. The algorithm is linear to N
for both code and decode of the combination. What language are you interested in?
编辑:我这里是code C ++中(它开创的组合的序列中的辞书号所有,而不是那些有n个元素的组合 K
元素,但确实是很好的起点):
here is example code in c++(it founds the lexicographical number of a combination in the sequence of all combinations of n elements as opposed to the ones with k
elements but is really good starting point):
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;
}
我很抱歉,我有一个算法,你所要求的,现在的问题,但我相信这将是一个很好的锻炼,试图为明白我做什么上面。事实是这是我教的课程算法设计与分析的算法之一,这就是为什么我是有pre-写的。
I am sorry I have an algorithm for the problem you are asking for right now, but I believe it will be a good exercise to try to understand what I do above. Truth is this is one of the algorithms I teach in the course "Design and analysis of algorithms" and that is why I had it pre-written.
这篇关于完美最小散列数学组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!