CODEWITHSUNDEEP
calgorithmpermutationcombinations
linusz
linusz

Reputation: 783

get the i-th combination of arrays of numbers

I know there are many similar questions, and I have read them for hours. But none of them seems to meet my requirement.

My problem:

given n int arrays, and each of them has the form 

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

We choose one number of each array to make a combination, and the number of such combinations is

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

For example

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

the 2*3*2 = 12 combinations are

 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 want to get the i-th combination (e.g. the 9-th combination is {1,1,1}) and get it efficiently. I've tried the idea of base-n conversion, something like this Permutation for numbers in C. But it's not efficient since the base has to be the largest count_i, which might be unnecessary. I've also thought about the idea of using different bases for each bit, but it's tricky to get the relation right.

Any suggestions are truly welcome.

Upvotes: 2

Views: 169

Answers (1)

Joachim W
Joachim W

Reputation: 8197

The main difference from your link (Permutation for numbers in C) is that 49^i becomes a product of count_j's:

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

where you precomputed

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

In your example with counts = 2,3,2, we have sub=6,2,1, hence for i=9 index=1,1,1

Upvotes: 4

Related Questions