给定组合时如何计算索引（字典顺序）

一尘不染

给定组合时如何计算索引（字典顺序）

algorithm

我知道有一种算法可以在给定数字组合（无重复，无顺序）的情况下计算词典顺序的索引。
这对于我的应用程序加速工作非常有用…

例如：

combination(10, 5)  
1 - 1 2 3 4 5  
2 - 1 2 3 4 6  
3 - 1 2 3 4 7  
....  
251 - 5 7 8 9 10  
252 - 6 7 8 9 10

我需要算法返回给定组合的索引。
es：index( 2, 5, 7, 8, 10 )->索引

编辑：实际上我正在使用Java应用程序，该应用程序会生成所有组合C（53，5）并将其插入TreeMap中。我的想法是创建一个包含所有组合（和相关数据）的数组，我可以使用此算法对其进行索引。
一切都是为了加快组合搜索。但是，我尝试了一些（不是全部）解决方案，并且您提出的算法要比TreeMap的get（）慢。
如果有帮助，我的需求是从53到0到52的5的组合。

再次感谢大家：-)

阅读 260

2020-07-28

共1个答案

一尘不染

这是一个可以完成工作的代码段。

#include <iostream>

int main()
{
    const int n = 10;
    const int k = 5;

    int combination[k] = {2, 5, 7, 8, 10};

    int index = 0;
    int j = 0;
    for (int i = 0; i != k; ++i)
    {
        for (++j; j != combination[i]; ++j)
        {
            index += c(n - j, k - i - 1);
        }
    }

    std::cout << index + 1 << std::endl;

    return 0;
}

假设您具有功能

int c(int n, int k);

这将返回从n个元素中选择k个元素的组合数。循环计算给定组合之前的组合数量。通过在末尾添加一个，我们可以获得实际的索引。

对于给定的组合，有c（9，4）= 126个组合，其中包含1，因此按字典顺序位于其前面。

在包含2个最小数字的组合中，有

c（7，3）= 35个组合，其中3为第二个最小数字

c（6，3）= 20个组合，第二个最小数为4

所有这些都在给定组合之前。

在包含2和5作为两个最小数字的组合中，有

c（4，2）= 6个组合，其中6为第三最小数。

所有这些都在给定组合之前。

等等。

如果在内部循环中放置打印语句，则会得到数字126、35、20、6、1。希望可以解释代码。

2020-07-28