determinazione combinazioni semplici

[valentino46]

Devo implementare un algoritmo che dato un array di interi mi stampi tutte le combinazioni semplici dei suoi elementi, ad esempio:
con {1,2,3,4}
mi dia
1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234

So che non è una cosa poi così complicata ma non riesco a venirne a capo..ho cercato su internet ma o trovo in altri linguaggi e quindi non so tradurre o trovo cose parzialmente giuste.
Mi aiutate????
Grazie!!

[andbin]

Devo implementare un algoritmo che dato un array di interi mi stampi tutte le combinazioni semplici dei suoi elementi, ad esempio:
[...]

Innanzitutto bisogna precisare una cosa. La sequenza che hai postato in realtà sarebbe da vedere come l'insieme di sequenze distinte, dove ciascuna sequenza delle combinazioni ha una classe k (numero di elementi) ben precisa. E ciascuna di queste sequenze è da trattare in modo separato.

Per una certa classe k, enumerare le combinazioni "semplici" è banale se puoi/vuoi "cablare" la classe k in una serie di cicli "annidati".

Ad esempio:

public class CombinazioniSempliciClasseK_2 {
    public static void main(String[] args) {
        int[] valori = { 1, 2, 3, 4 };
        
        for (int i = 0; i < valori.length-1; i++) {
            for (int j = i+1; j < valori.length; j++) {
                System.out.println("comb: " + valori[i] + valori[j]);
            }
        }
    }
}

Nel codice sopra, il numero di valori è arbitrario, puoi aggiungere 5, 6, 7 .... quanti ne vuoi. Ma la classe k è fissa a 2, perché è "cablata" nel fatto che ci sono 2 cicli annidati.

Se non è questo che puoi/vuoi fare, c'è un'altra soluzione: realizzare un algoritmo più generico in cui la classe k può essere "arbitraria". Non è difficilissimo però devi cambiare punto di vista, la enumerazione delle combinazioni semplici devi vederla un po' (anzi molto) come se fosse un "sistema di numerazione", in cui gli indici (dei valori nell'array) progrediscono secondo una logica che puoi facilmente dedurre e poi generalizzare guardando una sequenza più o meno lunga di combinazioni per una certa classe k.

[valentino46]

andbin ti ringrazio per la risposta ma proprio non ci riesco.
Ho anche pensato di implementare il tuo stesso procedimento (con k for annidati) tramite ricorsione (tramite ricorsione poichè la dimensione dell'array di input non è fissa ma la conosco a tempo di esecuzione , quindi devo operare dinamicamente) ma proprio non ci riesco
In pratica devo fare un algoritmo che mi restituisca tutte le combinazioni semplici degli elementi dell'array presi a k a k con k € [1-n] , cioè del tipo

public static Combinazione [] getCombinazioni (int [] array) {
   ...
}

che poi tramite ad esempio un for interno richiami un metodo ricorsivo (?) per il calcolo delle combinazioni semplici relative al corrente valore di k (k=1 ? dammi tutte le combinazioni di dim 1 , k = 2 dammi tutte le combinazioni di dim 2 ecc ecc e poi le inserisco opportunamente nell'array da restituire.Ho reso l'idea?

[valentino46]

Ispirato da quanto scritto da andbin ho risolto nel seguente modo , molto rude ma efficace:
(Preciso innanzitutto che so che l'input avrà lunghezza massima 8 , inoltre ora do l'ingresso come String invece che int [] ma vabè dettagli a partire da int [] costruisco la String concatenando i suoi elementi)

public static LinkedList<String> getCombinazioni (String s , int k) {        
        LinkedList<String> l = new LinkedList<String> ();
        int n = s.length ();
        StringBuilder sb = new StringBuilder ();
        //1
        if (k >= 1) {
            for (int i=0;i<n;i++) {
                l.add (s.charAt (i) + "");
            }
        }


        //2
        if (k >= 2) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    sb.append (s.charAt (i));
                    sb.append (s.charAt (j));
                    l.add (sb.toString ());
                    sb = new StringBuilder ();
                }
            }
        }


        //3
        if (k>=3) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    sb = new StringBuilder ();
                    for (int z=j+1;z<n;z++) {
                        sb.append (s.charAt (i));
                        sb.append (s.charAt (j));
                        sb.append (s.charAt (z));
                        l.add (sb.toString ());
                        sb = new StringBuilder ();
                    }
                }
            }
        }


        //4
        if (k >=4) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    for (int z=j+1;z<n;z++) {
                        for (int a=z+1;a<n;a++) {
                            sb.append (s.charAt (i));
                            sb.append (s.charAt (j));
                            sb.append (s.charAt (z));
                            sb.append (s.charAt (a));
                            l.add (sb.toString ());
                            sb = new StringBuilder ();
                        }
                    }
                }
            }
        }


        //5
        if (k >= 5) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    for (int z=j+1;z<n;z++) {
                        for (int a=z+1;a<n;a++) {
                            for (int b=a+1;b<n;b++) {
                                sb.append (s.charAt (i));
                                sb.append (s.charAt (j));
                                sb.append (s.charAt (z));
                                sb.append (s.charAt (a));
                                sb.append (s.charAt (b));
                                l.add (sb.toString ());
                                sb = new StringBuilder ();
                            }
                        }
                    }
                }
            }
        }


        //6
        if (k >= 6) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    for (int z=j+1;z<n;z++) {
                        for (int a=z+1;a<n;a++) {
                            for (int b=a+1;b<n;b++) {
                                for (int c=b+1;c<n;c++) {
                                    sb.append (s.charAt (i));
                                    sb.append (s.charAt (j));
                                    sb.append (s.charAt (z));
                                    sb.append (s.charAt (a));
                                    sb.append (s.charAt (b));
                                    sb.append (s.charAt (c));
                                    l.add (sb.toString ());
                                    sb = new StringBuilder ();
                                }
                            }
                        }
                    }
                }
            }
        }
        
        //7
        //STESSA PROCEDURA FATTA SOPRA MA AGGIUNGENDO UN ALTRO FOR ANNIDATO
        
                //8
                //IDEM PER LA PROCEDURA 7 MA CON 8 FOR ANNIDATI...


        return l;
    }