Le combinazioni di più elementi del vettore, senza ripetizione

Question

ho n quantità di vettori, dire 3, e hanno n quantità di elementi (non necessariamente la stessa quantità). Ho bisogno di scegliere x quantità di combinazioni tra di loro. Come scegliere 2 da vettori [n]. Esempio:

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

Non ci possono essere combinazioni di uno stesso vettore, come v1 [0] e v1 [1]. Come posso fare questo? Ho provato di tutto, ma non riesco a capire questo fuori.

Answer 1

Se ho capito bene si dispone di N vettori, ognuno con un diverso numero di elementi (chiamano la dimensione del vettore-esima Si) e quale scegliere le combinazioni M di elementi da questi vettori senza ripetizione. Ciascuna combinazione sarebbe N elementi, un elemento da ciascun vettore.

In questo caso il numero di possibili permutazioni è il prodotto delle dimensioni dei vettori che, per mancanza di qualche forma di equazione modificando chiamerò P e calcolano 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];

Così ora il problema diventa quello di raccogliere M numeri distinti tra 0 e P-1, quindi convertendo ciascuno di quei numeri M in indici N nei vettori originali. Mi vengono in mente alcuni modi per calcolare questi numeri M, forse il più semplice è quello di mantenere il disegno numeri casuali fino ad ottenere quelle distinte M (campionamento efficacemente il rifiuto dalla distribuzione).

La parte un po 'più complicata è quello di trasformare ognuno dei vostri numeri M in un vettore di indici. Siamo in grado di farlo con

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

che sminuzza fondamentalmente m in blocchi per ciascun indice, proprio come si farebbe quando indicizzare una matrice 2D rappresentato come una matrice 1D.

Ora, se prendiamo il tuo N = 3 esempio possiamo ottenere i 3 elementi della nostra permutazione con

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

generando in molti valori distinti di m come richiesto.

Answer 2

Probabilmente la confusione si alza dalla definizione impropria del problema. Indovinare che è necessario N volte scegliere 1 elemento a partire dal 1 di vettori V, si può fare questo:

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.