c - 获得数字数组的第 i 个组合

Question

我知道有很多类似的问题，我已经阅读了几个小时。但是他们似乎都不符合我的要求。

我的问题:

给定 n 个 int 数组，每个数组的形式都是

array_i[] = {0, 1,...,count_i-1}, i = 0,1,...,n-1.

我们从每个数组中选取一个数进行组合，这样的组合数为

count_0*count_1*...*count_{n-1}

例如

array_0 = {0,1}
array_1 = {0,1,2}
array_2 = {0,1}

2*3*2 = 12种组合是

 0| 0 0 0
 1| 0 0 1
 2| 0 1 0
 3| 0 1 1
 4| 0 2 0
 5| 0 2 1
 6| 1 0 0 
 7| 1 0 1
 8| 1 1 0
 9| 1 1 1
10| 1 2 0
11| 1 2 1

我想得到第 i 个组合(例如第 9 个组合是 {1,1,1})并高效地得到它。我试过 base-n 转换的想法，像这样 Permutation for numbers in C .但它效率不高，因为基数必须是最大的 count_i，这可能是不必要的。我也考虑过为每一位使用不同的基数的想法，但是要正确地建立关系是很棘手的。

我们非常欢迎任何建议。

Answer 1

与您的链接 (Permutation for numbers in C) 的主要区别在于 49^i 成为 count_j 的乘积:

index_0 = ( i / sub_0 ) % count_0
index_1 = ( i / sub_1 ) % count_1
...

你预先计算的地方

sub_0 = count_1*count_2*...*count_{n-1}
sub_1 = count_2*count_3*...*count_{n-1}
...

在您的示例中，counts = 2,3,2，我们有 sub=6,2,1，因此 i=9 index=1,1,1