Комбинации элементов нескольких векторов без повторения

Question

У меня есть n векторов, скажем 3, и у них есть n элементов (не обязательно такая же сумма). Мне нужно выбрать х комбинаций между ними. Как выбрать 2 из векторов [n]. Пример:

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

Там не может быть комбинации из одного самого вектора, как v1 [0] и v1 [1]. Как я могу это сделать? Я пробовал все, но не могу понять это.

Answer 1

Если я вас правильно понял вы имеете N векторов, каждый с разным числом элементов (назовем размер i-й вектор Si), и вы, которые должны выбрать M комбинаций элементов из этих векторов без повторения. Каждая комбинация будет N элементов, по одному элементу от каждого вектора.

В этом случае число возможных перестановок есть произведение размеров векторов, которые, из-за отсутствия какой-либо форме уравнения заходящего Я позвоню P и вычислим в 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]; 

Так теперь проблема становится одной из множества M различных чисел между 0 и P-1, а затем преобразование каждого из этих M чисел в N индексов в исходные векторы. Я могу подумать о нескольких способах вычисления этих чисел M, возможно, самым простым является сохранение рисования случайных чисел до тех пор, пока вы не получите M отличных от них (эффективно отбраковывая выборку из дистрибутива).

Немного более изогнутая часть состоит в том, чтобы превратить каждое из ваших M-чисел в вектор индексов. Мы можем сделать это с

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]; 
} 

, который в основном измельчает м вверх на куски для каждого индекса, так же, как вы бы при индексировании 2D массив, представленный в виде 1D массив.

Теперь, если мы возьмем ваш N = 3 примера мы можем получить 3 элементы нашей перестановки с

v1 [индексами [0]] v2 [индексами [1]] v3 [Индексы [2]]

генерирует столько различных значений m, сколько требуется.

Answer 2

Возможно, путаница возникает из-за неправильного определения проблемы. Гадать, что вам нужно N раз выбрать 1 элемент из 1 из V векторов, вы можете сделать это:

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.