[JAVA] Operazione su array (permutazioni)

[Javino89]

Salve ragazzi. Dovrei fare una particolare operazione dato un array in input. Non so descriverlo a parole quindi vi faccio un esempio:

input --> int[]array = {0,1,2}; (può essere anche più grande)

Dato questo input devo restituire un oggetto di questo tipo:

LinkedList<Stato> ritorno...

Dove Stato è una classe con variabile di istanza di questo tipo: TreeSet<Integer> stati...

Quindi, dato l'input che ho scritto prima,l'output che dovrei ottenere deve essere così:

[[0],[1],[2],[0,1],[0,2],[1,2],[0,1,2]]

E' una cosa mia personale e mi sto veramente incartando. Help!

[andbin]

Originariamente inviato da Javino89
Salve ragazzi. Dovrei fare una particolare operazione dato un array in input. Non so descriverlo a parole quindi vi faccio un esempio:

input --> int[]array = {0,1,2};

Dato questo input devo restituire un oggetto di questo tipo:

LinkedList<Stato> ritorno...

Dove Stato è una classe con variabile di istanza di questo tipo: TreeSet<Integer> stati...

Quindi, dato l'input che ho scritto prima,l'output che dovrei ottenere deve essere così:

[[0],[1],[2],[0,1],[0,2],[1,2],[0,1,2]]

E' una cosa mia personale e mi sto veramente incartando. Help!

Ogni Stato quindi contiene l'insieme di uno o più valori int. E poi hai una lista di stati. Fin qui a me pare chiaro.

Quello che dovresti spiegare è il concetto che sta alla base della sequenza che vuoi ottenere. Che non hai spiegato!

Quello che deduco io, vedendo la sequenza di esempio, è che prima prendi gli N valori singolarmente, poi a coppie (viste così mi sembra siano le "combinazioni semplici, senza ripetizioni"), poi l'insieme di tutti i valori.

Ma se ci sono 4, 5 o più elementi? Quale è la regola generale? Ripeto: non l'hai spiegata.

[Javino89]

Non so se è concettualizzabile,è questo il punto.

Se l'array è fatto così: int[]array = {0,1,2,3}, dovremmo avere:

[[0],[1],[2],[3],[0,1],[0,2],[0,3],[1,2],[1,3],[2,3],[0,1,2],[0,2,3],[1,2,3],[0,1,2,3,4]]

Non so essere più chiaro..

Probabile che per ottenere una cosa simile ci vogliano 3, 4 cicli for annidati.. ma per ora ho la testa un po troppo incasinata e mi serve una mano xD

[andbin]

Originariamente inviato da Javino89
Non so se è concettualizzabile,è questo il punto.

Se l'array è fatto così: int[]array = {0,1,2,3}, dovremmo avere:

[[0],[1],[2],[3],[0,1],[0,2],[0,3],[1,2],[1,3],[2,3],[0,1,2],[0,2,3],[1,2,3],[0,1,2,3,4]]

Non so essere più chiaro..

Allora, volendo generalizzare: sono tutte "combinazioni semplici, senza ripetizioni", solo con un k (classe) differente.

Nel tuo caso N=4, quindi prima prendi le combinazioni semplici con k=1, poi con k=2, poi con k=3, poi con k=4. Insomma, tutte le combinazioni semplici per ogni k da 1 a N.

E a questo punto è solo questione di generare le combinazioni semplici. Cerca in rete, trovi formule, algoritmi, implementazioni, ecc....

[andbin]

Prendiamo per esempio una lista di 5 lettere:

          A B C D E
indice -> 0 1 2 3 4

Quindi n=5, elenchiamo le combinazioni semplici per k=3:

A B C     0 1 2
A B D     0 1 3
A B E     0 1 4
A C D     0 2 3
A C E     0 2 4
A D E     0 3 4
B C D     1 2 3
B C E     1 2 4
B D E     1 3 4
C D E     2 3 4

Osserva la sequenza degli indici a fianco!! Cosa noti?

Il primo indice va da 0 a 2, il secondo va da 1 a 3 e parte sempre dal primo indice+1, il terzo va da 2 a 4 e parte dal secondo+1.

Generalizza questa cosa e hai trovato il modo per enumerare tutte le "combinazioni semplici" n,k per un qualunque array/lista di qualunque tipo e lunghezza!!

[Javino89]

Ok perfetto, il problema è che non ho un k fisso, ma devo calcolare tutte le combinazioni semplici, quindi penso che dovrò incrementare k da 0 a array.length-1 no?

[andbin]

Originariamente inviato da Javino89
Ok perfetto, il problema è che non ho un k fisso, ma devo calcolare tutte le combinazioni semplici, quindi penso che dovrò incrementare k da 0 a array.length-1 no?

Innanzitutto nel tuo caso k va da 1 a N (N=numero di elementi nell'array).
Il fatto di avere una progressione su k è solo al livello più "esterno". Pensa prima al livello più interno. Cioè hai N elementi e devi generare le combinazioni per un k ben preciso.
Quando avrai fatto questo .... beh, farlo per un k variabile è solo un ciclo esterno!!

[Javino89]

Ora che ci penso, conosco un algoritmo RICORSIVO studiato all'università che permette
il calcolo delle disposizioni senza ripetizione o permutazioni (cambiando poco per ottenere
le due versioni differenti), ma combinazioni no. Credo che comunque il riadattamento non è complesso.

L'algoritmo per le permutazioni in questione è questo (in pseudocodice):

Algoritmo permutazioni(k,S,U):
    Input: Un intero k, una sequenza S e un insieme U
    Output: Un elenco di tutte le sequenze di S di lunghezza k che usano
        elementi di U senza ripetizioni
    for all e E U do
        Rimuovi e da U {ora e è usato}
        Aggiungi e alla fine di S
        if k=1 then
            Controlla se S è una configurazione che risolve l'enigma
            if S risolve l'enigma then
                return "Soluzione trovata: " S
        else
            permutazioni(k-1,S,U):
        Rimetti e in U
        Rimuovi e dalla fine di S

Questo è per le permutazioni senza ripetizione, ma credo si possa adattare anche per le combinazioni... la domanda è in che modo xD

Ps: Potrei ripassare tutta la sequenza con le permutazioni ed eliminare da essa gli oggetti Stato che contengono doppioni ma mi pare molto inefficente.

[andbin]

Originariamente inviato da Javino89
Ora che ci penso, conosco un algoritmo RICORSIVO studiato all'università che permette
il calcolo delle disposizioni senza ripetizione o permutazioni (cambiando poco per ottenere
le due versioni differenti), ma combinazioni no. Credo che comunque il riadattamento non è complesso.

Sono (quasi) certo che si possa fare in modo ricorsivo ma in questo momento non ho "testa" per ragionarci. E se riesci a trovare il modo ben venga, scegli tu l'approccio che meglio credi.

Io personalmente preferisco sempre "linearizzare" cose di questo tipo e magari implementarle per offrire un approccio a "iteratore". Se dovessi farlo io, farei una classe es. CombinazioniSemplici che riceve nel costruttore un array di oggetti Object[] (o lista ... dipende) e un valore di k.
Poi offrirei come minimo un metodo es.: Object[] prossimaCombinazione() che fornisce la successiva combinazione con k elementi. Finché non restituisce null. Ed eventualmente (nel miglior stile a "iteratore") un metodo es.: boolean combinazioneDisponibile().

Ma a parte metodi/nomi e varianti varie, così diventa semplice e lineare (nonché facilmente riutilizzabile).

[Javino89]

Non credo che posso mettere un valore di k input visto che non è un valore fisso.

Penso che il tutto debba iniziare con un ciclo for esterno di questo tipo..

for(int k=1; k < input.length; k++)
{

...

}