如何在给出组合时计算指数(词典顺序)

Question

我知道有一种算法允许,在给定数字组合(无重复,无顺序)的情况下,计算字典顺序的索引.
对我的应用来说,加速事情会非常有用......

例如:

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 )- > index

编辑:实际上我正在使用一个生成所有组合C(53,5)的Java应用程序并将它们插入到TreeMap中.我的想法是创建一个包含我可以使用此算法索引的所有组合(和相关数据)的数组.
一切都是加速组合搜索.但是我尝试了一些(不是全部)解决方案,你提出的算法比TreeMap中的get()慢.
如果它有帮助:我的需求是从0到52的5到53的组合.

再次感谢大家:-)

Answer 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为第三个最小数.

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

等等.

如果你在内部循环中放置一个print语句,你将获得数字126,35,20,6,1.希望能解释代码.

Answer 2

将您的号码选择转换为阶乘基数.此数字将是您想要的索引.从技术上讲,这会计算所有排列的词典索引,但是如果你只给它组合,那么索引仍然是有序的,只是每个组合之间的所有排列都有一些大的间隙.

编辑:删除了伪代码,这是不正确的,但上面的方法应该有效.太累了,现在想出正确的伪代码.

编辑2:这是一个例子.假设我们从一组10个元素中选择了5个元素的组合,就像上面的例子一样.如果组合是2 3 4 6 8,您将获得相关的阶乘基数,如下所示:

取出未选择的元素并计算您必须经过多少才能到达您选择的元素.

1 2 3 4 5 6 7 8 9 10
2 -> 1
1 3 4 5 6 7 8 9 10
3 -> 1
1 4 5 6 7 8 9 10
4 -> 1
1 5 6 7 8 9 10
6 -> 2
1 5 7 8 9 10
8 -> 3

因此,因子基数中的指数是 1112300000

在十进制基数中,它是

1*9! + 1*8! + 1*7! + 2*6! + 3*5! = 410040