Combinações de elementos do Vector Multiple sem repetição

Question

Eu tenho n quantidade de vetores, digamos, 3, e eles têm n quantidade de elementos (não necessariamente a mesma quantidade). Eu preciso escolher x quantidade de combinações entre eles. Como escolher 2 a partir de vectores [n]. Exemplo:

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

Não pode haver combinações de um próprio vector, como v1 [0] e v1 [1]. Como posso fazer isso? Já tentei de tudo, mas não pode descobrir isso.

Answer 1

Se eu entendi você tem vetores N, cada um com um número diferente de elementos (ligue para o tamanho do vetor om Si) e você que para escolher M combinações de elementos desses vetores sem repetição. Cada combinação seria N elementos, um elemento de cada vector.

Neste caso, o número de permutações possíveis é o produto dos tamanhos dos vetores, que, por falta de algum tipo de equação definindo Vou ligar P e computação em 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];

Assim, agora o problema torna-se uma colheita de H números distintos entre 0 e P-1, em seguida, a conversão de cada um desses números M em índices de N nos vectores originais. Eu posso pensar de algumas maneiras de computar esses números M, talvez o mais fácil é manter desenho números aleatórios até chegar M queridos distintas (amostragem efetivamente rejeição da distribuição).

A parte um pouco mais complicado é transformar cada um dos seus números de M em um vetor de índices. Podemos fazer isso com

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

que basicamente costeletas estou em pedaços para cada índice, assim como você iria ao indexar uma matriz 2D representado como uma matriz 1D.

Agora, se tomarmos o seu N = 3 exemplo, podemos obter os 3 elementos da nossa permutação com

v1 [índices [0]] v2 [índices [1]] v3 [índices [2]]

gerar tantos valores distintos de m tal como exigido.

Answer 2

Provavelmente a confusão se levanta da definição inadequada do problema. Supondo que você precisa N vezes pegar um elemento a partir de 1 de vetores V, você pode fazer isso:

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.