我知道有一种算法允许在给定数字组合(无重复,无顺序)的情况下计算字典顺序的索引.这对我的应用程序来说非常有用,可以加快速度...
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: index( 2, 5, 7, 8, 10 ) --> index
I need that the algorithm returns the index of the given combination. es: index( 2, 5, 7, 8, 10 ) --> index
实际上我正在使用一个生成所有组合 C(53, 5) 并将它们插入到 TreeMap 中的 Java 应用程序.我的想法是创建一个数组,其中包含我可以使用此算法索引的所有组合(和相关数据).一切都是为了加速组合搜索.但是,我尝试了您的一些(不是全部)解决方案,并且您提出的算法比 TreeMap 中的 get() 慢.如果有帮助:我的需求是从 0 到 52 的 53 的组合.
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.
再次感谢大家:-)
推荐答案这是一个可以完成工作的片段.
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; }假设你有一个函数
int c(int n, int k);这将返回从 n 个元素中选择 k 个元素的组合数.循环计算给定组合之前的组合数.通过在最后添加一个,我们得到了实际的索引.
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) = 126 个包含 1 的组合,因此按字典顺序排在它前面.
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
所有这些都在给定的组合之前.
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.
所有这些都在给定的组合之前.
All of these are preceding the given combination.
等
如果你在内循环中放置一个打印语句,你将得到数字126、35、20、6、1.希望能解释代码.
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.
更多推荐
给定组合时如何计算索引(字典序)
发布评论