数学组合的完美最小散列

Question

首先，定义两个整数n和k，其中n>=k，两者在编译时都已知。例如:n=8和k=3。

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

具有K元素的S子集的数目由公式C(N,K)给出。例

我的问题是：为这些子集创建一个完美的最小哈希。示例哈希表的大小为C(8,3)或56。

我不关心排序，只关心哈希表中有56个条目，并且我可以从一组k整数中快速确定哈希。我也不在乎可逆性。

哈希示例:哈希（{5,2,3}）=42。（数字42并不重要，至少在这里不重要）

是否有一种通用算法可以处理n和k的任何值？我无法通过搜索谷歌找到一个，或者我自己天真的努力。

Answer 1

有一种算法可以用给定的固定k按照所有组合的词典顺序将组合编码和解码成其编号。对于组合的编码和解码，该算法与n线性。你对什么语言感兴趣？

Edit：下面是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;
}

我很抱歉我现在有一个算法来解决你现在问的问题，但我相信这将是一个很好的练习，试图理解我在上面做了什么。事实上，这是我在“算法的设计和分析”课程中教授的算法之一，这就是为什么我要预先编写它。