Combinare efficacemente combinazioni di vettori

Question

Sto lavorando a un problema di ricerca per curiosità e non so come programmare la logica che ho in mente. Mi spiego a voi:

ho quattro vettori, diciamo per esempio,

v1 = 1 1 1 1 
v2 = 2 2 2 2 
v3 = 3 3 3 3 
v4 = 4 4 4 4 

Ora quello che voglio fare è quello di aggiungere loro combinazione-saggio, cioè,

v12 = v1+v2 
v13 = v1+v3 
v14 = v1+v4 
v23 = v2+v3 
v24 = v2+v4 
v34 = v3+v4 

Fino a questo punto va bene. Il problema ora è che voglio aggiungere ciascuno di questi vettori un vettore da v1, v2, v3, v4 che non ha aggiunto prima. Ad esempio:

v3 e v4 non è stato aggiunto a v12, quindi voglio creare v123 e v124. Allo stesso modo per tutti i vettori come,

v12 should become: 
v123 = v12+v3 
v124 = v12+v4 

v13 should become: 
v132 // This should not occur because I already have v123 
v134 

v14 should become: 
v142 // Cannot occur because I've v124 already 
v143 // Cannot occur 

v23 should become: 
v231 // Cannot occur 
v234 ... and so on. 

È importante che io non faccia tutto in un solo passaggio all'inizio. Ad esempio, posso fare (4 scegliere 3) 4C3 e terminarlo, ma voglio farlo passo dopo passo ad ogni iterazione.

Come si programma?

P.S .: Sto provando a lavorare su una versione modificata di un algoritmo apriori nel data mining.

Answer 1

In C++, dato la seguente procedura:

template <typename Iterator> 
inline bool next_combination(const Iterator first, 
            Iterator k, 
          const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

Si può quindi procedere a effettuare le seguenti operazioni:

int main() 
{ 
    unsigned int vec_idx[] = {0,1,2,3,4}; 

    const std::size_t vec_idx_size = sizeof(vec_idx)/sizeof(unsigned int); 

    { 
     // All unique combinations of two vectors, for example, 5C2 
     std::size_t k = 2; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    std::sort(vec_idx,vec_idx + vec_idx_size); 

    { 
     // All unique combinations of three vectors, for example, 5C3 
     std::size_t k = 3; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    return 0; 
} 

** Nota 1: * A causa dell'interfaccia iteratore oriented per la next_combination routine, è possibile utilizzare qualsiasi contenitore STL che supporta l'iterazione diretta tramite iteratori, ad esempio std::vector, std::deque e std::list, solo per citarne alcuni.

Nota 2: Questo problema è adatto per l'applicazione di tecniche di memoizzazione. In questo problema, puoi creare una mappa e riempirla con somme vettoriali di combinazioni date. Prima di calcolare la somma di un determinato set di vettori, è possibile cercare se un qualsiasi sottoinsieme delle somme è già stato calcolato e utilizzare tali risultati.Sebbene tu stia eseguendo una sommatoria che è abbastanza economica e veloce, se il calcolo che stavi eseguendo fosse molto più complesso e dispendioso in termini di tempo, questa tecnica sarebbe sicuramente di aiuto per ottenere importanti miglioramenti delle prestazioni.

Answer 2

1. Mantenere un elenco di tutti per la scelta di due valori.
2. Creare un vettore di insiemi in modo tale che l'insieme sia costituito da elementi del vettore originale con gli elementi 4C2. Scorri sopra i vettori originali e per ognuno aggiungi/crea un set con elementi del passaggio 1. Mantieni un vettore di set e solo se il set non è presente, aggiungi il risultato al vettore.
3. Somma il vettore di set ottenuta al passaggio 2.

Ma, come hai indicato, il più semplice è 4C3.

Ecco qualcosa scritto in Python. Si può adottare in C++

import itertools 

l1 = ['v1','v2','v3','v4'] 
res = [] 
for e in itertools.combinations(l1,2): 
    res.append(e) 

fin = [] 
for e in res: 
    for l in l1: 
     aset = set((e[0],e[1],l)) 
     if aset not in fin and len(aset) == 3: 
      fin.append(aset) 
print fin 

Ciò comporterebbe:

[set(['v1', 'v2', 'v3']), set(['v1', 'v2', 'v4']), set(['v1', 'v3', 'v4']), set(['v2', 'v3', 'v4'])] 

Questo è lo stesso risultato 4C3.

Answer 3

Forse sto fraintendendo, ma non è questo equivalente a generare tutti i sottoinsiemi (set di potenza) di 1, 2, 3, 4 e quindi per ogni elemento del set di potenza, sommando il vettore? Per esempio:

//This is pseudo C++ since I'm too lazy to type everything 
//push back the vectors or pointers to vectors, etc. 
vector< vector<int> > v = v1..v4; 

//Populate a vector with 1 to 4 
vector<int> n = 1..4 

//Function that generates the power set {nil, 1, (1,2), (1,3), (1,4), (1,2,3), etc. 
vector< vector <int> > power_vec = generate_power_set(n); 

//One might want to make a string key by doing a Perl-style join of the subset together by a comma or something... 
map< vector <int>,vector<int> > results; 
//For each subset, we sum the original vectors together 
for subset_iter over power_vec{ 
    vector<int> result; 
    //Assumes all the vecors same length, can be modified carefully if not. 
    result.reserve(length(v1)); 
    for ii=0 to length(v1){ 
     for iter over subset from subset_iter{ 
      result[ii]+=v[iter][ii]; 
     } 
    } 
    results[*subset_iter] = result; 
} 

Se questo è l'idea che si aveva in mente, hai ancora bisogno di una funzione insieme potenza, ma che il codice è facile da trovare se si cerca insieme potenza. Ad esempio, Obtaining a powerset of a set in Java.

Answer 4

Penso che questo problema possa essere risolto contrassegnando quale combinazione si è verificata.

Il mio primo pensiero è che è possibile utilizzare una matrice a 3 dimensioni per contrassegnare quale combinazione è avvenuta. Ma non è molto bello.

Che ne dici di un array di bit (come un numero intero) per la segnalazione? Ad esempio:

Num 1 = 2^0 for vector 1 
Num 2 = 2^1 for vector 2 
Num 4 = 2^2 for vector 3 
Num 8 = 2^3 for vector 4 

Quando si effettua una composizione, è sufficiente aggiungere tutto il numero rappresentativo. Ad esempio, il vettore 124 avrà il valore: 1 + 2 + 8 = 11. Questo valore è unico per ogni combinazione.

Questo è solo un mio pensiero. Spero che ti aiuti in qualche modo.

EDIT: Forse non sono abbastanza chiaro riguardo la mia idea. Proverò a spiegarlo un po 'più chiaramente:

1) Assegnare per ogni vettore un numero rappresentativo. Questo numero è l'id di un vettore ed è unico. Inoltre, la somma di ogni sottoinsieme di quel numero è unica, significa che se abbiamo la somma di k il numero rappresentativo è M; possiamo facilmente sapere quali sono i vettori che partecipano alla somma.

Lo facciamo assegnando: 2^0 per vettore 1; 2^1 per il vettore 2; 2^2 per il vettore 3, e così via ...

Con ogni M = somma (2^x + 2^y + 2^z + ...) = (2^x OR 2^y OR 2^z OR ...). Sappiamo che il vettore (x + 1), (y + 1), (z +1) ... prende parte alla somma. Questo può essere facilmente controllato con il numero espresso in modalità binaria.

Per esempio, sappiamo che:

2^0 = 1 (binario) 2^1 = 10 (binario) 2^2 = 100 (binario) ...

Così che se abbiamo la somma è 10010 (binario), sappiamo che il vettore (numero: 10) e il vettore (numero: 10000) si uniscono nella somma.

E per il meglio, la somma qui può essere calcolata dall'operatore "OR", che è anche facilmente comprensibile se si esprime il numero in binario.

2) Utilizzando i fatti di cui sopra, ogni volta prima che conti la somma del tuo vettore, puoi aggiungere/O il loro numero rappresentativo prima. E puoi tenerli traccia in qualcosa come un array di ricerca. Se la somma esiste già nell'array di ricerca, puoi ometterla. Con ciò puoi risolvere il problema.