Combinations of Multiple Vector's Elements Without Repetition

Question

Hi,

I have n amount of vectors, say 3, and they have n amount of elements (not necessarily the same amount). I need to choose x amount of combinations between them. Like choose 2 from vectors[n]. Example:

std::vector<int> v1(3), v2(5), v3(2);

There cannot be combinations from one vector itself, like v1[0] and v1[1]. How can I do this? I've tried everything, but cannot figure this out.

Answer 1

Probably the confusion rises from improper definition of the problem. Guessing that you need to N times pick 1 element from 1 of V vectors, you can do this:

select N of the V vectors you want to pick from (N <= V)
for each of the selected vectors, select 1 of the vector.size() elements.

Answer 2

If I understand you correctly you have N vectors, each with a different number of elements (call the size of the ith vector Si) and you which to choose M combinations of elements from these vectors without repetition. Each combination would be N elements, one element from each vector.

In this case the number of possible permutations is the product of the sizes of the vectors, which, for lack of some form of equation setting I'll call P and compute in C++:

std::vector<size_t> S(N);
// ...populate S...
size_t P = 1;
for(size_t i=0;i<S.size();++i)
    P *= S[i];

So now the problem becomes one of picking M distinct numbers between 0 and P-1, then converting each of those M numbers into N indices into the original vectors. I can think of a few ways to compute those M numbers, perhaps the easiest is to keep drawing random numbers until you get M distinct ones (effectively rejection sampling from the distribution).

The slightly more convoluted part is to turn each of your M numbers into a vector of indices. We can do this with

size_t m = /* ... one of the M permutations */;
std::vector<size_t> indices_m(N);

for(size_t i=0; i<N; ++i)
{
    indices[i] = m % S[i];
    m /= S[i];
}

which basically chops m up into chunks for each index, much like you would when indexing a 2D array represented as a 1D array.

Now if we take your N=3 example we can get the 3 elements of our permutation with

v1[indices[0]] v2[indices[1]] v3[indices[2]]

generating as many distinct values of m as required.