Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich

[Lebowski1]

Hallo,

ich habe mehrere Listen (ArrayList) mit einer unterschiedlichen Anzahl von Elementen, z. B.

ListA: a, b, c
ListB: c, d

Nun könnte ich alle Kombinationen der Elemente aus ListA und ListB bilden, indem ich zwei for-Schleifen verschachtel.

Wie gehe ich aber vor, wenn die Anzahl der Listen unterschiedlich ist, die Ausgangssituation also z. B.

ListA: a, b, c
ListB: c, d
ListC: e,f,g

oder so

ListA: a, b, c
ListB: c, d
ListC: e,f,g
ListD: h,i,j,k,l,m

sein kann. Es ist ja unschön, wenn ich prophylaktisch soviele for-Schleifen implementiere, wie bei dem zugehörigen Problem auftreten könnten.

Besten Dank

 

[Machareder]

http://www.java-forum.org/java-basi...44-2dim-array-ausgabe-zahlen-teilbar-3-a.html

 

[Lebowski1]

Hallo,

das hilft mir leider nicht weiter. Ich will ja alle Kombinationen finden. Als mehrdimensionales Array dargestellt sieht das dann so aus:

a,b,c,d,e
f
g,h,i,j
k,l,m,n

Kombinationen sind dann afgk, afgl, ... afin, ... efjn

Ich kann ja nun folgendes machen, um alle Kombinationsmöglichkeiten aller Reihen untereinander zu bekommen

char[][] foo = {
        {'a', 'b', 'c', 'd', 'e'},
        {'f'},
        {'g', 'h', 'i', 'j'},
        {'k', 'l', 'm', 'n'}
};

for(char[] reihe1: foo){
    for(char akt1: reihe1){
        for(char[] reihe2: foo){
            if(reihe1 ==reihe2) continue;
            for(char akt2: reihe2){
                System.out.println(String.valueOf(akt1)+String.valueOf(akt2)+"");
            }
        }
    }
}

ab das liefert mir eben nur alle Zweierkombinationen, also af, bf ... jn

Wie bekomme ich es hin, dass ich alles Reihen mit allen Reihen kombiniere

 

[Natac]

Ich denke Rekursion wäre hier ein guter Ansatz.

Schreibe doch erstmal eine Methode, die alle Elemente von 2 Listen kombiniert:

public List<String> combine(List<String> l1, List<String> l2)

Dann überlege dir, wie du diese Methode aufrufen (nicht ausbauen) kannst, um drei Listen zu kombinieren.

 

[NoXiD]

öhm meinst du so:
[Java]
char[][] foo = {
{'a', 'b'},
{'f'},
{'g','h','i'}
};
[/Java]

Ausgabe:
[Java]
ab
af
aghi
ba
bf
bghi
fab
f
fghi
gab
gf
ghi
hab
hf
hgi
iab
if
igh
[/Java]
?

Spoiler: Code

[Java]public static void permutate(char[][]foo){
for(int i = 0 ; i < foo.length; i++){
char[] currentRow = foo;
for(int ii = 0; ii < currentRow.length; ii++){
for(int j = 0; j < foo.length; j++){
System.out.print(String.valueOf(currentRow[ii]) );
for(int jj = 0; jj < foo[j].length;jj++){
if(currentRow[ii] != foo[j][jj]){
System.out.print(String.valueOf(foo[j][jj]));
}
}
System.out.println();
}
}
}
}[/Java]

[WR]mit Rekursion wärs schöner[/WR]

 

[ry_void]

Ich glaube auch das hier ein Rekursiver Aufruf besser wäre.

Nimm erst ein Element der ersten Dimension und geh damit alle Elemente der nächsten Dimension durch. Und wenn es noch eine Dimension gibt dann gehe erst alle Elemente von dieser durch... und immer weiter und immer weiter...

Je nachdem ob es Permutation mit oder ohne Wiederholung sein soll wird es komplexer oder nicht.

 

[Lebowski1]

Hallo,

und danke für die Rückmeldungen. Ich habe jetzt folgende Möglichkeit gefunden, die ist aber iterativ. Wie sähe denn die rekursive Lösung aus?

import java.util.ArrayList;

public class Combinations
{
    ArrayList<ArrayList<String>> listen;

    public Combinations()
    {
        ArrayList<String> a = new ArrayList();
        a.add("A");
        a.add("B");
        a.add("C");
        a.add("D");
        a.add("E");

        ArrayList<String> b = new ArrayList();
        b.add("F");

        ArrayList<String> c = new ArrayList();
        c.add("G");
        c.add("H");
        c.add("I");
        c.add("J"); 

        ArrayList<String> d = new ArrayList();
        d.add("K");
        d.add("L");
        d.add("M");
        d.add("N");

        listen = new ArrayList();

        listen.add(a);
        listen.add(b);
        listen.add(c);
        listen.add(d);
    }

    public void allCombinationes(){
        ArrayList<String>  erg = listen.get(0);
        for(int i = 1;i<listen.size();i++){
            erg = combine(erg,listen.get(i));
        }
        // Ausgeben
        for(String combination: erg)
            System.out.println(combination);
        System.out.println("Anzahl: "+erg.size());
    }

    public ArrayList<String> combine(ArrayList<String> listA, ArrayList<String> listB){
        ArrayList<String> erg = new ArrayList();
        for(String c1: listA){
            for(String c2: listB){
                erg.add(c1+c2);
            }
        }
        return erg;
    }
}

Die Ausgabe ist dann

AFGK
AFGL
AFGM
AFGN
AFHK
AFHL
AFHM
AFHN
AFIK
AFIL
AFIM
AFIN
AFJK
AFJL
AFJM
AFJN
BFGK
BFGL
BFGM
BFGN
BFHK
BFHL
BFHM
BFHN
BFIK
BFIL
BFIM
BFIN
BFJK
BFJL
BFJM
BFJN
CFGK
CFGL
CFGM
CFGN
CFHK
CFHL
CFHM
CFHN
CFIK
CFIL
CFIM
CFIN
CFJK
CFJL
CFJM
CFJN
DFGK
DFGL
DFGM
DFGN
DFHK
DFHL
DFHM
DFHN
DFIK
DFIL
DFIM
DFIN
DFJK
DFJL
DFJM
DFJN
EFGK
EFGL
EFGM
EFGN
EFHK
EFHL
EFHM
EFHN
EFIK
EFIL
EFIM
EFIN
EFJK
EFJL
EFJM
EFJN
Anzahl: 80