Combinazioni array

[Hermiod]

Salve a tutti,
sto cercando da giorni a venire a capo del mio problema che sembra apparentemente banale ma che, in realtà, mi sta facendo impazzire.

Ho una matrice di n array di 3 elementi dove n è variabile. Devo combinare ciascun elemento di ciascuna array con ciascun elemento degli altri array. E' un discorso un po' contorto e spero di chiarirmi con un esempio.

Supponiamo la matrice sia così fatta:

String mat[][] = {
  {"AA", "Aa", "aa"},
  {"BB", "Bb", "bb"},
  {"CC", "Cc", "cc"},
  {"DD", "Dd", "dd"}
};

in questo caso una matrice 4x3. Le combinazioni che devo tirar fuori sarebbere queste:

AA BB CC DD
AA BB CC Dd
AA BB CC dd
AA BB Cc DD
AA BB Cc Dd
...
aa bb cc Dd
aa bb cc dd

ho cercato di abbozzare diversi algoritmi che vanno dai semplici cicli annidati a funzioni ricorsive senza però arrivare ad una soluzione.
Mi potreste dare un'idea su come risolvere?
Ringraziandovi anticipatamente porgo distinti saluti.

PS.: è evidente che al crescere del numero degli array i tempi di computazione
crescono in modo esponenziale ma so a priori, per il campo di applicazione dell'algoritmo, che
saranno rarissimi i casi in cui la matrice avrà un numero di righe superiore a 3 e quindi potrei gestire il tutto con tre cicli annidati ma devo comunque gestire la matrice indipendentemente dalla dimensione.

[andbin]

Originariamente inviato da Hermiod
Ho una matrice di n array di 3 elementi dove n è variabile. Devo combinare ciascun elemento di ciascuna array con ciascun elemento degli altri array.

ho cercato di abbozzare diversi algoritmi che vanno dai semplici cicli annidati a funzioni ricorsive senza però arrivare ad una soluzione.

potrei gestire il tutto con tre cicli annidati ma devo comunque gestire la matrice indipendentemente dalla dimensione.

Vediamo innanzitutto di chiarire/chiarirti alcune cose.
Dici che la quantità di array di 3 elementi è variabile, quindi potresti avere più righe nell'array 'mat' es. {"EE", "Ee", "ee"} ..... {"ZZ", "Zz", "zz"}, giusto?

La classe 'k', ovvero il numero di elementi nei gruppi generati è sempre uguale al numero di righe? Cioè se avessi anche la riga {"EE", "Ee", "ee"}, il primo gruppo sarebbe AA BB CC DD EE e l'ultimo sarebbe aa bb cc dd ee, giusto?

Anche se hai mostrato solo alcuni pezzi della sequenza, io potrei già dedurre che:
- non ci sono "ripetizioni" all'interno di ogni gruppo, quindi non avrai es. AA AA CC DD
- non conta l'ordine degli elementi, quindi avrai AA BB CC DD ma non DD CC BB AA e nemmeno es. AA BB DD CC o altre disposizioni.

Fin qui è corretto? Confermami e posso spiegarti come si può facilmente generare quella sequenza.

[Hermiod]

Ciao andbin e grazie per la tua risposta!
Hai centrato tutto in pieno, scusa se ho trascurato alcune informazioni!

[andbin]

Originariamente inviato da Hermiod
Ciao andbin e grazie per la tua risposta!
Hai centrato tutto in pieno, scusa se ho trascurato alcune informazioni!

Perfetto, allora gestire la generazione di quella sequenza in modo dinamico, cioè con un numero arbitrario di righe nell'array 'mat' è abbastanza semplice.

Non puoi appunto usare cicli annidati, perché in questo modo andresti a "cablare" la classe 'k', ovvero il numero di elementi nel gruppo.

Io ti faccio l'esempio con 3 righe:

String mat[][] = {
  {"AA", "Aa", "aa"},
  {"BB", "Bb", "bb"},
  {"CC", "Cc", "cc"},
};

Ecco la sequenza (a fianco metto degli indici):

AA BB CC   0 0 0
AA BB Cc   0 0 1
AA BB cc   0 0 2

AA Bb CC   0 1 0
AA Bb Cc   0 1 1
AA Bb cc   0 1 2

AA bb CC   0 2 0
AA bb Cc   0 2 1
AA bb cc   0 2 2

Aa BB CC   1 0 0
Aa BB Cc   1 0 1
Aa BB cc   1 0 2
.....
.....
aa bb CC   2 2 0
aa bb Cc   2 2 1
aa bb cc   2 2 2

Gli indici a fianco sono gli indici 0 1 2 dentro una riga es. {"AA", "Aa", "aa"}.

Come ti sembra la progressione degli indici? Lineare e predicibile, no?
Semplicemente istanzia un array int[] con un numero di elementi uguale al numero di righe in 'mat'. L'array è già inizializzato con tutti 0.
Per ogni combinazione nell'array int[] puoi banalmente comporti un array con le stringhe risultanti.

Poi ti basta fare un metodo che faccia "progredire" gli indici partendo dal fondo, come si farebbe in un sistema di numerazione. Ripeto: per ottenere la "prossima" combinazione degli indici, basta fare un semplice ciclo for in cui si incrementa l'indice:
- se è minore di 2, incrementi e puoi uscire subito dal for.
- se è 2, azzeri e il ciclo passa all'indice successivo.

Se lo fai "generico" puoi gestire sia un numero arbitrario di righe nell'array 'mat' sia un numero arbitrario di elementi nelle righe (anche potenzialmente con righe di lunghezza differente!).

P.S. consiglio implementativo: fai una classe apposita a cui passi es. al costruttore il tuo array String[][] e con un metodo "next" (o "successivo", come vuoi) che ti fornisce la prossima combinazione come String[] (o null se finita la sequenza). Come design alternativo: un next() che restituisce boolean e un getCombinazione() che restituisce String[].
Sono varianti che puoi scegliere tu.

[Hermiod]

Buongiorno andbin, ieri ho avuto un impegno e ho dovuto interrompere.
Ho capito l'idea e mi sembra ottima ma non mi torna il fatto che si possa fare con un solo ciclo senza "cablare" l'elaborazione.
Facciamo un esempio ridotto:

String mat[][] = {
  {"AA", "Aa", "aa"},
  {"BB", "Bb", "bb"}
};

le combinazioni risultanti sarebbero

0 0 \
0 1  | blocco 1
0 2 /

1 0 \
1 1  | blocco 2
1 2 /

2 0 \
2 1  | blocco 3
2 2 /

con molta fantasia chiamo l'array delle combinazioni comb, in questo caso di cardinalità 2.
La parte che non riesco a comprendere (colpa mia perché in questo periodo non ci sto con la testa ) è questa qui

Poi ti basta fare un metodo che faccia "progredire" gli indici partendo dal fondo, come si farebbe in un sistema di numerazione. Ripeto: per ottenere la "prossima" combinazione degli indici, basta fare un semplice ciclo for in cui si incrementa l'indice:
- se è minore di 2, incrementi e puoi uscire subito dal for.
- se è 2, azzeri e il ciclo passa all'indice successivo.

questa cosa dell'incremento dell'indice sarebbe in realtà il valore da inserire nella locazione di comb? Ogni volta che mi sposto di locazione, dopo aver inserito il valore, devo ripartire nuovamente dal fondo?!
Scusami, la cosa sarà banale, ma ho la testa da un'altra parte
Grazie infinite per la tua pazienza

[andbin]

Originariamente inviato da Hermiod
Ho capito l'idea e mi sembra ottima ma non mi torna il fatto che si possa fare con un solo ciclo senza "cablare" l'elaborazione.

Certo che si può fare. Come capita spesso, quando vedo quesiti di questo tipo cerco anche io di "esercitarmi" e provo a scrivere del codice.
Bene, ho scritto una classe che si occupa solo di gestire queste combinazioni, con un costruttore che riceve il String[][] (e fa anche una serie di validazioni sull'array) e con un metodo next() che restituisce in String[] il prossimo "gruppo". Tutto generico e "pilotato" interamente dai dati nell'array in input. Il mio sorgente è venuto di 54 righe...

Originariamente inviato da Hermiod
questa cosa dell'incremento dell'indice sarebbe in realtà il valore da inserire nella locazione di comb? Ogni volta che mi sposto di locazione, dopo aver inserito il valore, devo ripartire nuovamente dal fondo?!

Supponi di avere 3 righe, quindi avrai un array int[] di lunghezza 3, inizialmente sarà { 0, 0, 0 }

Io per fare queste cose in genere tengo una variabile boolean di "carry" (riporto), inizialmente a true (perché deve fare "riporto" di 1 già sull'indice meno significativo).

Poi basta fare un ciclo for, ripeto, ne basta uno per far progredire l'array di int dalla combinazione numerica corrente a quella successiva. Parti dall'ultimo elemento, fino verso il primo, se il valore è minore di 2 (se vuoi generalizzarlo, non cablare 2, basati sulla lunghezza della riga i-esima) incrementi e metti carry a false e fai in modo che il ciclo finisca subito.
Se il valore è 2, azzeri il valore e non fai altro, il ciclo prosegue con l'indice più a sinistra e siccome il carry è ancora true, si ripeterà il test.

Se terminato il ciclo il carry è true, vuol dire che ha fatto "riporto" dall'indice più significativo e quindi la sequenza è terminata e il prossimo next() dovrà restituire null (se scegli questo design come ho fatto io).

[Hermiod]

Ok, ho realizzato la fattibilità con un singolo ciclo: il "popolamento" dell'array con le combinazioni avviene mediante la manipolazione dei valori attuali.
Ho implementato l'algoritmo, ora mi concentro sulla terminazione del ciclo.
Ti faccio sapere quando trovo la soluzione e te la posto così mi dici un po' se si possono fare eventuali ottimizzazioni

[Hermiod]

Eccolo

for (int i = com.length - 1; i >= 0; ) {
    System.out.println(Arrays.toString(com));

    if (com[i] < 2) {
        com[i]++;
    } else {
        while (com[i] == 2) {
            com[i] = 0;
            i--;
            if (i < 0) {
                break;
            }
            if (com[i] < 2) {
                com[i]++;
                i = com.length - 1;
            }
        }
    }
}

La storia del carry è chiara ma momentaneamente non ho la testa a posto e necessito di una soluzione urgente e funzionante.
Che ne pensi? So che si può fare di meglio ma dai diversi test che ho fatto funziona a dovere.
Per quanto riguarda il "cablaggio" della dimensione dell'array della matrice mi sta bene così: tutti gli array avranno quel formato lì (sono combinazioni genotipiche, in poche parole trattasi del quadro di Punnet).

[andbin]

Originariamente inviato da Hermiod
Che ne pensi? So che si può fare di meglio ma dai diversi test che ho fatto funziona a dovere.

No, non funziona. Hai fatto il println dentro il for e ti stampa ogni volta solo una situazione "parziale" dell'array e non è quello che ti serve.

Se metti esattamente quel codice in un ulteriore ciclo (come dovrebbe poi effettivamente essere, avendo poi un ciclo che ruota attorno ad un next() o comunque, in generale, a ogni progressione dell'array ...

import java.util.*;

public class Test {
    public static void main(String[] args) {
        int[] com = { 0, 0, 0 };
    
        while (true) {
            System.out.println(Arrays.toString(com));   // SEMPRE 0,0,0 !!!!!!!
            
            //----------------------------------
            for (int i = com.length - 1; i >= 0; ) {
                //System.out.println(Arrays.toString(com));    // Non ha senso

                if (com[i] < 2) {
                    com[i]++;
                } else {
                    while (com[i] == 2) {
                        com[i] = 0;
                        i--;
                        if (i < 0) {
                            break;
                        }
                        if (com[i] < 2) {
                            com[i]++;
                            i = com.length - 1;
                        }
                    }
                }
            }
            //----------------------------------
        }
    }
}

Non funziona.

[Hermiod]

Sorgete

package matrix;

import java.util.Arrays;

public class Matrix {

    public static void main(String[] args) throws Exception {
        String mat[][] = {
            {"AA", "Aa", "aa"},
            {"BB", "Bb", "bb"},
            {"CC", "Cc", "cc"}
        };

        int com[] = new int[mat.length];

        for (int i = com.length - 1; i >= 0; ) {
            System.out.println(Arrays.toString(com));

            if (com[i] < 2) {
                com[i]++;
            } else {
                while (com[i] == 2) {
                    com[i] = 0;
                    i--;
                    if (i < 0) {
                        break;
                    }
                    if (com[i] < 2) {
                        com[i]++;
                        i = com.length - 1;
                    }
                }
            }
        }
    }
}

Output

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

usando gli indici generati accedo a mat e ho fatto!