Combinare tutti gli elementi di una matrice

di
Raziel84
il
10 risposte
Raziel84
Raziel84
Pochi posts
Iscritto da
giu, 2018
Messaggi:
10

Combinare tutti gli elementi di una matrice

Un saluto a tutti.
Ho un esercizio che mi sta facendo uscire matto
Creata una matrice da input (quindi di qualsiasi dimensione, anche irregolare) devo combinare gli elementi di ogni riga con quelli delle righe successive. Es:

String [][] m = {
{"A"},
{"1"}, {"2"},
{"X"},
{"Y"}
};
quindi output:
A 1 X Y
A 2 X Y

Devo creare un metodo sia iterativo che ricorsivo per ottenere lo stesso risultato.
Data una matrice m[][], con quello iterativo ho fatto così:

for (String item : m[0])
for (String item1 : m[1])
for (String item2 : m[2])
for (String item3 : m[3])
System.out.println(item + " " + item1 + " " + item2 + " " + item3);

Funziona benissimo, ma il problema è che è creato "su misura" in quanto ho creato tanti for-each per quante sono le righe e l'istruzione che ognuna di esse contiene si occupa di scorrere correttamente le colonne per creare le possibili combinazioni. Il metodo da creare invece dev'essere standard, a prescindere dalla matrice creata in input.
Avete soluzioni da suggerire? Ricordatevi che ho bisogno di una soluzione anche ricorsiva dello stesso problema (ancora più difficile per me).
Grazie in anticipo a chi risponderà.

10 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Combinare tutti gli elementi di una matrice

    Raziel84 ha scritto:

    Creata una matrice da input (quindi di qualsiasi dimensione, anche irregolare) devo combinare gli elementi di ogni riga con quelli delle righe successive.

    Devo creare un metodo sia iterativo che ricorsivo
    Esistono sicuramente più soluzioni per entrambi gli approcci.

    Riguardo le soluzioni iterative, una che a me piace è quella di trattare la progressione delle combinazioni come un "sistema di numerazione".
    String[][] m = {
    {"A", "B"},         // indici 0, 1
    {"1", "2", "3"},    // indici 0, 1, 2
    {"X", "Y"},         // indice 0, 1
};
    quindi un int[3] (3, il numero di righe di m) per i 3 indici. E poi fai progredire gli indici così:

    {0,0,0}
    {0,0,1}
    {0,1,0}
    {0,1,1}
    ....
    {1,2,1}

    Per ciascun gruppo, dagli indici ricavi i valori. Questa logica si può anche incapsulare bene in una classe per gestirla a mo' di "iteratore" (ovvero, ottenere la prossima combinazione ad ogni "next").


    P.S. prima hai scritto {"1"}, {"2"}, ma credo sia sbagliato! Così hai 5 righe.
  • Raziel84
    Raziel84
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Combinare tutti gli elementi di una matrice

    Ebbene si, in effetti volevo scrivere {"1", "2"}, quindi 4 righe secondo l'esempio riportato.

    Il suggerimento che mi hai dato purtroppo non l'ho capito bene. Non è quello che fanno i for, mettere in ciclo gli indici e creare le combinazioni di cui sopra? Ma come faccio a creare queste combinazioni senza creare for su misura? E' questo il passaggio che mi blocca...
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Combinare tutti gli elementi di una matrice

    Raziel84 ha scritto:

    Non è quello che fanno i for, mettere in ciclo gli indici e creare le combinazioni di cui sopra? Ma come faccio a creare queste combinazioni senza creare for su misura?
    No, quanto ho detto io è perfettamente generalizzabile e gestibile "dinamicamente" per qualunque numero di elementi nella combinazione.

    Quello che hai fatto tu invece, ovvero i for "annidati", va a "cablare" fisso nel codice il numero di elementi nella combinazione, che ovviamente ha senso solo se noto/prefissato a priori.

    Prova a pensare come fare quella progressione, se non riesci, posso dare qualche indizio in più.
  • Raziel84
    Raziel84
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Combinare tutti gli elementi di una matrice

    E' stata dura ma penso di avercela fatta!!!
    Ecco qua il codice da me ideato. Sono stati necessari diversi metodi, ma girano divinamente con qualsiasi tipo di matrice! 
    
    public static int[] elementiRiga(String[][] m)
    {
        int[] elementi = new int[m.length];
        
        for (int i = 0; i < elementi.length; i++)
            elementi[i] = m[i].length;

        return elementi;
    }
    
        
    public static int numeroCombinazioni(int[] n)
    {
        int nCombinazioni = 1;
        
        for (int i = 0; i < n.length; i++)
            nCombinazioni *= n[i];
        
        return nCombinazioni;
    }
    
    
    public static int[][] combinazioni(int[] n)
    {
        int[][] combinazioni = new int[numeroCombinazioni(n)][n.length];
        int ripetizioni = combinazioni.length;
        
        for (int colonna = 0; colonna < n.length; colonna++)
        {
            ripetizioni = ripetizioni / n[colonna];
            int conteggio = 1;
            
            for (int riga = 1; riga < combinazioni.length; riga++)
            {
                if (conteggio < ripetizioni)
                {
                    combinazioni[riga][colonna] = combinazioni[riga-1][colonna];
                    conteggio++;
                }
                else if (combinazioni[riga-1][colonna] < n[colonna]-1)
                {
                    combinazioni[riga][colonna] = combinazioni[riga-1][colonna] + 1;
                    conteggio = 1;  
                }
                else // combinazioni[riga-1][colonna] == n[colonna] && riga < combinazioni.length
                    conteggio = 1;
                // La casella contiene già il valore 0, quindi è sufficiente resettare solo il conteggio
                // per continuare il ciclo di combinazioni nel caso di scorrimento riga incompleto.
            }
        }       
        
        return combinazioni;
    }
    
    
    public static void combinaElementiMatrice(String[][] m, int[][] combinazioni)
    {
        for (int[] riga : combinazioni)
        {
            for (int j = 0; j < riga.length; j++)
                System.out.print(m[j][riga[j]] + " ");
            
            System.out.println();
        }
    }
    Infine dentro il main non faccio altro che richiamare questi metodi con due istruzioni
    
        int[][] combinazioni = combinazioni(elementiRiga(matrix));
        combinaElementiMatrice(matrix, combinazioni);
    Ci sono suggerimenti per renderlo migliore o usare meno codice per implementare lo stesso processo di combinazioni? Secondo me è perfetto!
    Di certo ora devo cimentarmi col ricorsivo, e adesso si che cominciano i dolori!!!
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Combinare tutti gli elementi di una matrice

    Raziel84 ha scritto:

    Ci sono suggerimenti per renderlo migliore o usare meno codice per implementare lo stesso processo di combinazioni?
    Ti assicuro che si può fare meglio e con ben meno della metà di codice se seguissi le indicazioni che ho dato prima. Se ti facessi vedere quanto viene semplice come penso io .... secondo me caschi dalla sedia o sbianchi completamente ..
  • Raziel84
    Raziel84
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Combinare tutti gli elementi di una matrice

    Ma è dal tuo suggerimento che sono arrivato a questa conclusione! Per essere un autodidatta penso di aver fatto un buon codice.
    Se mi puoi dire chiaramente come lo avresti fatto con meno codice sarebbe per me un ottimo insegnamento. Mi aiuterebbe per il futuro a pensare in maniera differente.

    PS: con gli argomenti sono arrivato alla ricorsione, che nel mio libro di testo è menzionata subito dopo gli array mono e bidimensionali. Ecco perchè questo esercizio (preso dal libro) vuole la doppia modalità di svolgimento.
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Combinare tutti gli elementi di una matrice

    Raziel84 ha scritto:

    Ma è dal tuo suggerimento che sono arrivato a questa conclusione!
    Il suggerimento era quello di trattare le combinazioni degli indici come un "sistema di numerazione". E per passare da una combinazione alla successiva, è sufficiente applicare la stessa logica che si impara alle elementari, si aggiunge 1 alla cifra meno "significativa" e poi si va avanti sulle cifre di peso maggiore tramite "riporto".
    Per fare tutto questo è sufficiente un solo ciclo for piccolissimo con un solo if dentro.
  • Raziel84
    Raziel84
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Combinare tutti gli elementi di una matrice

    Praticamente quello che fa il mio metodo "combinazioni".

    Solo che, se ho capito bene, per rendere più semplice il tutto non devo creare una matrice con tutte le combinazioni, ma un solo array che di volta in volta cambia le sue combinazioni (tenendo a mente il suo limite massimo che in sostanza è la lunghezza massima che ogni riga può contenere).

    Eccheccavolo ci devo riuscire!!!
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Combinare tutti gli elementi di una matrice

    Raziel84 ha scritto:

    Praticamente quello che fa il mio metodo "combinazioni".
    Ma il tuo è molto più complesso. Oltretutto è pure "girato" al contrario, ovvero parti dalle colonne e per ciascuna fai tutti i valori nelle righe. E questo è poco comprensibile nonché poco "leggibile". Ed appunto ti impone di precalcolare tutte le combinazioni.

    Raziel84 ha scritto:

    per rendere più semplice il tutto non devo creare una matrice con tutte le combinazioni, ma un solo array che di volta in volta cambia le sue combinazioni
    Sì, questa è una soluzione semplice e fattibile. Passare da una combinazione alla successiva è molto facile, basta 1 for e 1 if.
  • Raziel84
    Raziel84
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Combinare tutti gli elementi di una matrice

    Dopo la versione semplificata da te suggerita, la versione ricorsiva l'ho così fatta:
    
    public static void stampaCombinazioniRicorsiva(String[][] m, int[] indici, boolean riporto)
    {
        if (riporto)
        {
            for (int i = 0; i < indici.length; i++)
                System.out.print(m[i][indici[i]] + " ");

            System.out.println();
            
            for (int i = indici.length-1; i >= 0 && riporto; i--)
                if (++indici[i] < m[i].length)
                    riporto = false;
                else
                    indici[i] = 0;

            stampaCombinazioniRicorsiva(m, indici, !riporto);
        }
    }
    E dentro il main ovviamente ho dovuto fare:
    
int[] indici = new int[m.length];
boolean riporto = true;
stampaCombinazioniRicorsiva(m, indici, riporto);
    Penso che così vada bene
Devi accedere o registrarti per scrivere nel forum
10 risposte