tutte le possibili 2^n soluzioni

[omniaforever]

Salve ragazzi, avrei bisogno di una semplice soluzione algoritmica.
Praticamente ho un vettore di N elementi. Ognuno di questi elementi può puntare ad un oggetto specifico o essere NULL (banalmente possiamo semplificare dicendo che può assumere i valori 0 o 1).
Avrei bisogno di generare tutte le possibilità di questo vettore, cioè se ad esempio il vettore è di 3 elementi
000
001
010
011
100
101
110
111
Cioè creare in uscita un vettore di vettori, in cui ogni vettore è di N elementi ciascuno dei quali valorizzato o NULL.

In sostanza si dovrebbe ridurre a un problema di trovare tutti i 2^n numeri in versione binaria, a partire da n elementi


LINGUAGGIO C++

Grazie

edit: nel terzo post è chiarito meglio
http://hwupgrade.it/forum/showpost.php?p=37070906&postcount=3

[ESSE-EFFE]

Salve ragazzi, avrei bisogno di una semplice soluzione algoritmica.
Praticamente ho un vettore di N elementi. Ognuno di questi elementi può puntare ad un oggetto specifico o essere NULL (banalmente possiamo semplificare dicendo che può assumere i valori 0 o 1).
Avrei bisogno di generare tutte le possibilità di questo vettore, cioè se ad esempio il vettore è di 3 elementi
000
001
010
011
111

Probabilmente non ti serve il vettore di vettori. Immagino che in qualche modo avrai un indice che ti indica (appunto) quale "possibilità" devi utilizzare. A questo punto ti basta verificare i bit dell'indice. Se il bit è settato, utilizzi il puntatore corrispondente, altrimenti no (come se fosse NULL).

[omniaforever]

Probabilmente non ti serve il vettore di vettori. Immagino che in qualche modo avrai un indice che ti indica (appunto) quale "possibilità" devi utilizzare. A questo punto ti basta verificare i bit dell'indice. Se il bit è settato, utilizzi il puntatore corrispondente, altrimenti no (come se fosse NULL).

Forse mi sono spiegato male.
A me interessa CREARE tutte queste possibilità.

Mettiamo caso che il mio vettore originale è di 3 elementi specifici:
vettore_in = {VAL1, VAL2, VAL3}

quello che voglio creare in uscita è:

vettore_out = {{NULL, NULL, NULL}, {NULL, NULL, VAL3}, {NULL, VAL2, NULL}, {NULL, VAL2, VAL3}, {VAL1, NULL, NULL}, {VAL1, NULL, VAL3},{VAL1, VAL2, NULL}, {VAL1, VAL2, VAL3}}

In realtà mi ero scordato a scrivere i casi 100 e 110 e 101

VAL1, VAL2 E VAL3 sono i valori di partenza dei vari elementi del vettore di in
Man mano nel vettore di out devo renderli null, in modo da ottenere tutte le combinazioni (nel caso in cui non siano null tengono il valore di partenza

[__ZERO_UNO__]

Su questo blog è implementato un algoritmo in C# per generare tutte le combinazioni di k elementi da un insieme di n elementi.

http://seekwell.wordpress.com/2007/11/17/knuth-generating-all-combinations/

[omniaforever]

il link al codice non funziona...
ma la mia richiesta è diversa:
non voglio generare combinazioni di k elementi su un insieme di n elementi.
A me serve generare, a partire a N elementi che possono assumere 2 valori, tutti le possibilità. Ad esempio con 3 elementi {A=valA,B=valB,C=valC} inizializzati a dei valori specifici, ottenere
NULL, NULL, NULL
NULL, NULL, valC
NULL, valB, NULL
NULL, valB, valC
valA, NULL, NULL
valA, NULL, valC
valA, valB, NULL
valA, valB, valC

se sostituiamo i val con 1 e i null con 0
000
001
010
011
100
101
110
111
Cioè tutti i numeri in rappresentazione binaria da 0 a 2^n -1.

L'idea più rozza era quella di fare un ciclo che genera tutte queste stringhe di bit da 0 a 2^n-1 (richiamando un metodo che passando un intero restituisce il relativo array di caratteri rappresentante la codifica binaria) e poi usare questa maschera ottenuta per ottenere ciò che mi interessa.

Ma credo ci sia una soluzione più diretta e veloce

[ESSE-EFFE]

Forse mi sono spiegato male.
A me interessa CREARE tutte queste possibilità.

Mettiamo caso che il mio vettore originale è di 3 elementi specifici:
vettore_in = {VAL1, VAL2, VAL3}

quello che voglio creare in uscita è:

vettore_out = {{NULL, NULL, NULL}, {NULL, NULL, VAL3}, {NULL, VAL2, NULL}, {NULL, VAL2, VAL3}, {VAL1, NULL, NULL}, {VAL1, NULL, VAL3},{VAL1, VAL2, NULL}, {VAL1, VAL2, VAL3}}

Crearle sì, ma non si capisce perchè tu debba tenerle in memoria. Comunque non è un problema, per costruire il vettore_out ti basta qualcosa del genere:


int campi = 3;
int poss = 1 << campi;
for (int i = 0; i < poss; i++)
{
for (int j = 0; j < campi; j++)
{
if (i & (1 << j))
vettore_out[i][campi - j] = vettore_in[j];
else
vettore_out[i][campi - j] = NULL;
}
}


Vado di corsa e non ho avuto modo di testarlo, quindi magari qualche errore c'è, comunque spero che ti dia l'idea.

[omniaforever]

Grazie! Era quello che cercavo!
Incollo il mio codice:


vector<vector<Match*>*> possibleResults (vector<Match*>* vm)
{

vector<vector<Match*>*> poss_res;
long poss = ((long) pow(2.0, (long) vm->size()));
int elem = vm->size() - 1;

for(long i = 0; i < poss ; i++)
{
vector<Match*>* matchesClusterd = new vector<Match*>;
for (int j = 0; j <= elem; j++)
{
if ((i & (1 << j)))
matchesClusterd->push_back((*vm)[j]);
else
matchesClusterd->push_back(NULL);
}

poss_res.push_back(matchesClusterd);
}

return poss_res

}


Solo una cosa: poichè sono parecchio arrugginito con linguaggi così "a basso livello" :D (sai che dramma ricominciare con i puntatori) avendo lavorato per un paio di anni esclusivamente in asp.net web application, qual è il significato di
if ((i & (1 << j)))
???
In particolare la i senza valore assegnato e il "<<"
E' sicuramente una cosa da ABC, ma non ricordo di aver mai utilizzato queste sintassi
Grazie!

[cenarius_88]

Ricordando vagamente l'informatica base gli operatori
>> e << sono detti shift destro e sinistro

In pratica 1<<j sovrebbe significare
1 shiftato a sinistra di j posizioni...
vale a dire
10000...000

dove gli 0 sono pari in numero a j

- if ((i & (1 << j)))

letteralmente significa
se
i (che viene fuori dal ciclo for)
& bit a bit
1 shiftato a sinistra di j posizioni

è una condizione verificata... allora svolgi quello dentro {}



spero di essere stato chiaro e di non aver detto corbellerie :D

[omniaforever]

Ora ho capito tutto.grazie