[JAVA] Permutazioni in un array di boolean

[Mira88]

Ciao a tutti, ho cercato in giro prima di scrivere qualcosa ma nn ho trovato niente... il mio problema è il seguente: a partire da un vettore boolean di lunghezza nota devo creare un algoritmo che ne generi tutte le permutazioni. Mi spiego meglio, se la lunghezza del vettore fosse 3 dovrei generare 3^2 permutazioni cioè gli otto numeri rappresentabili con 3 cifre binarie... ho provato a usare un metodo ricorsivo ma non riesco a renderlo corretto.... grazie a tutti in anticipo!! ciao

[andbin]

Originariamente inviato da Mira88
a partire da un vettore boolean di lunghezza nota devo creare un algoritmo che ne generi tutte le permutazioni.

Non avrebbe granché senso con un array di boolean. Se hai un array di boolean di lunghezza 3 e tutti sono a true .... anche permutando cosa ottieni?? Sempre true,true,true!! Quindi?

Originariamente inviato da Mira88
Mi spiego meglio, se la lunghezza del vettore fosse 3 dovrei generare 3^2 permutazioni cioè gli otto numeri rappresentabili con 3 cifre binarie...

No alt. Il numero di "permutazioni" di n elementi è dato dal fattoriale di n: Se hai 3 elementi, 3! = 6. Non certo 3^2 (che fa 9) e non certo 8.

Forse è meglio se chiarisci a noi (e a te) la questione ....

[Mira88]

Si in effetti hai ragione ho fatto un pò di casino... allora io parto da un vettore con tutti false, e devo ottenere tutte le permutazioni, cioè.....

000
001
010
011
100
101
110
111

ok? che sono 2^3 se nn sbaglio (nn 3^2 comè ho scritto prima )...
cerco di spiegarti anche il contesto.... ogniuna di quelle configurazione del vettore rappresenta una configurazione di variabili booleane che successivamente devo testare in una formula tipo questa (1 or 2) and (1 or 2 or not(3)) dove 1 2 e 3 rappresentano le variabili... ho già decodificato la formula a dovere mi rimane da vedere se è soddisfacibile, per fare questo devo generare le permutazioni di cui sopra e testarle.... spero di essere stato comprensibile....... grazie dell'aiuto!!

[andbin]

Originariamente inviato da Mira88
allora io parto da un vettore con tutti false, e devo ottenere tutte le permutazioni, cioè.....

000
001
010
011
100
101
110
111

ok? che sono 2^3 se nn sbaglio (nn 3^2 comè ho scritto prima )...

Allora non sono affatto "permutazioni" (ma sapere almeno cosa vuol dire??) ma "disposizioni con ripetizioni".

Ed è semplicissimo. Se il numero di elementi è noto/fisso, basta fare N cicli for annidati.

Altrimenti c'è la soluzione generica (per un qualunque numero di elementi). Perché basta seguire la logica dei sistemi di numerazione "pesati". Nel sistema decimale si va da 0 a 9. Quando una cifra è 9 e vuoi incrementare, cosa fai? La fai tornare a 0 e c'è un "riporto" sulla cifra più significativa.

Proprio questo. Per ogni nuovo incremento parti dalla cifra meno significativa, la "incrementi" e se fa il "giro" devi incrementare la cifra più significativa. E così via ...

Nel tuo caso di valori boolean è comunque molto semplice.

[Mira88]

ok grazie dell'aiuto!!! ciao

[Mira88]

ciao scusa ma sono di nuovo io..... ho provato ha ragionarci un pò su ma nn riesco a scrivere niente di sensato.... nn è che potresti scrivermi una bozza di codice....?? grazie