如何计算组合给予时的指数(词典编纂顺序) [英] How to calculate the index (lexicographical order) when the combination is given
问题描述
我知道,有一个算法,允许,给定数(不重复,没有秩序)的组合,计算字典顺序的索引。
这将是非常有益的我的应用程序加速比的东西...
I know that there is an algorithm that permits, given a combination of number (no repetitions, no order), calculates the index of the lexicographic order.
It would be very useful for my application to speedup things...
例如:
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:指数(2,5,7,8,10)
- >首页
I need that the algorithm returns the index of the given combination.
es: index( 2, 5, 7, 8, 10 )
--> index
编辑:其实我使用的Java应用程序生成的所有组合C(53,5),并将其插入到一个TreeMap的。
我的想法是创建一个包含所有组合(及相关数据),我可以使用索引算法的数组。
一切都是用来加快联合搜索。
不过,我尝试了一些(不是全部)的解决方案,以及您提出的算法是慢了一个get()从TreeMap中。
如果有帮助:我需要的是5从53开始,从0到52的组合
actually I'm using a java application that generates all combinations C(53, 5) and inserts them into a TreeMap.
My idea is to create an array that contains all combinations (and related data) that I can index with this algorithm.
Everything is to speedup combination searching.
However I tried some (not all) of your solutions and the algorithms that you proposed are slower that a get() from TreeMap.
If it helps: my needs are for a combination of 5 from 53 starting from 0 to 52.
再次感谢所有: - )
Thank you again to all :-)
推荐答案
下面是一个片段,就做好了。
Here is a snippet that will do the work.
#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;
}
它假设你有一个函数
It assumes you have a function
int c(int n, int k);
这将返回的选择k个元素出n个元素的组合的数目。 循环计算的组合preceding的给定组合的数目。 通过添加一个在最后我们得到的实际指数。
that will return the number of combinations of choosing k elements out of n elements. The loop calculates the number of combinations preceding the given combination. By adding one at the end we get the actual index.
对于给定的组合有 C(9,4)=含1和126组合,因此preceding它在字典顺序。
For the given combination there are c(9, 4) = 126 combinations containing 1 and hence preceding it in lexicographic order.
含2作为最小号的组合中有
Of the combinations containing 2 as the smallest number there are
C(7,3)= 35的组合具有3作为第二最小的数
c(7, 3) = 35 combinations having 3 as the second smallest number
C(6,3)= 20的组合具有4作为第二最小的数
c(6, 3) = 20 combinations having 4 as the second smallest number
所有这些都是preceding给定的组合
All of these are preceding the given combination.
含2和5作为两个最小数字的组合中有
Of the combinations containing 2 and 5 as the two smallest numbers there are
C(4,2)=具有6作为第三最小数字6的组合
c(4, 2) = 6 combinations having 6 as the third smallest number.
所有这些都是preceding给定的组合
All of these are preceding the given combination.
等
如果你把一个print语句在内部循环,你会得到的数字 126,35,20,6,1。 希望这解释了code。
If you put a print statement in the inner loop you will get the numbers 126, 35, 20, 6, 1. Hope that explains the code.
这篇关于如何计算组合给予时的指数(词典编纂顺序)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!