✔ Kombinationen über rekursiven Algorithmus berechnen?

[smartin123]

Hallo,

ich bin auf der Suche, nach einem Algorithmus, der mir die Kombinationen von n-verschieden Arrays und n-verschiedenen Items berechnet.
Mein Tool läuft sonst grafisch basiert, ich habe hier zu Testzwecken ein konsolenbasiertes Tool geschrieben. Bei dem GUI-Tool stehen dem User verschiedenste Comboboxen, mit Möglichkeit der Mehrfachselektion, zur Verfügung.

Class Main:

package rekursion;

import java.util.ArrayList;
import java.util.List;

public class TestMain {
	
	/**
	 * Test-Main
	 * @param args
	 */
	public static void main(String[] args) {
		
		//object instancing
		TestMain testMain = new TestMain();
		
		//*******************************************************************
		//First parameter
		String [] selection1 = new String[3];
		selection1[0] = ("A1");
		selection1[1] = ("A2");
		selection1[2] = ("A3");
		
		testMain.setRpCollection(selection1);
		
//		//Second parameter
		String [] selection2 = new String[2];
		selection2[0] = ("B1");
		selection2[1] = ("B2");
		
		testMain.setRpCollection(selection2);
		
		//Third parameter
		String [] selection3 = new String[2];
		selection3[0] = ("C1");

		testMain.setRpCollection(selection3);
		
		//*******************************************************************
		
		Combinations.buildCombinations(0);
		
	}
	
	public void setRpCollection(String[] strArray) {
		
		List<String> arrayList = new ArrayList<String>();
		
		for (int i = 0; i < strArray.length; i++) {
			if (strArray[i] != null)
			{
			arrayList.add(strArray[i]);
			}
		}
		
		Combinations.setCombinations( arrayList);

	}


}

Class Combinations:

package rekursion;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Combinations {

	private static List<List<String>> allSelections;

	public static String buildCombinations( int ndx )
	{
		
		if( ndx >= allSelections.size() ){
			return "\n";
		}
		
		Iterator<String> iterator = allSelections.get(ndx).iterator();
		String result = "";
		while( iterator.hasNext() ){
			String part = (String) iterator.next();
			result = part + " " + buildCombinations( ndx + 1);
		System.out.println(result);
		}
		return result;
	}
	
	public static void setCombinations(List<String> arrayList) {
		
		// allSelections doesn´t exist and is empty
		if (allSelections == null) {
			allSelections = new ArrayList<List<String>>();
		}
		
		List<String> cacheList = new ArrayList<String>();
		
		for (String selectionItem : arrayList) {
			
			cacheList.add("Part_" + selectionItem);
			
		}
		allSelections.add(cacheList);
		
	}


}

Leider läuft es noch nicht so wie es soll.

Die Ergebnisliste sollte das lieferen:

Part_A1 Part_B1 Part_C1
Part_A1 Part_B2 Part_C1
Part_A2 Part_B1 Part_C1
Part_A2 Part_B2 Part_C1
Part_A3 Part_B1 Part_C1
Part_A3 Part_B2 Part_C1

Geht das überhaupt?

In meinem GUI-Tool befinden sich verschiedene Comboboxen mit verschiedenen Selections.
In diesem Test-tool sollen die selections (arrays) die Comboboxen repräsentieren.


Die Komplexität besteht darain, dass die Parameter und deren Selections n-verschieden sein können.

Vielleicht ist dies auch ganz einfach zu lösen, leider hab ich darin noch keine Idee,

Kann man mir bitte jemand helfen?

Vielen Dank

MfG
smartin123

 

[Thomas Darimont]

Hallo,

hier mal eine einfache iterative Variante:

package de.tutorials;

public class Combinations {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Object[][] items = {
                {
                    "A1","A2","A3"
                },
                
                {
                    "B1", "B2"
                },
                
                {
                    "C1"
                }
        };
        
        int loops = 1;
        
        for(int i = 0; i < items.length;i++){
            loops *= items[i].length;
        }
        
        int[] indices = new int[items.length];
        
        for(int i = 0; i < loops;i++){
            for(int j = 0; j<items.length;j++){
                System.out.print(items[j][indices[j]] + " ");
                indices[j] = (indices[j] + 1) % items[j].length;
            }
            System.out.println();
        }
    }
}

Ausgabe:

A1 B1 C1 
A2 B2 C1 
A3 B1 C1 
A1 B2 C1 
A2 B1 C1 
A3 B2 C1

Gruß Tom

 

[smartin123]

Tom,
vielen Dank, genau das hab ich gesucht.

vg
smartin123

 

[Allan Knox]

Interessante Vorgehensweise.
Leider werden aber nicht alle Kombinationen erstellt, wenn man z.B. das C-Array erweitert.

Wenn man z.B. das Element C2 hinzufügt, also:

Object[][] items = {
        {
            "A1","A2","A3"
        },

        {
            "B1", "B2"
        },
                
        {
            "C1", "C2"
        }
};

ergibt die Ausgabe:
A1 B1 C1
A2 B2 C2
A3 B1 C1
A1 B2 C2
A2 B1 C1
A3 B2 C2
A1 B1 C1
A2 B2 C2
A3 B1 C1
A1 B2 C2
A2 B1 C1
A3 B2 C2
Nach der Hälfte der Einträge werden die Kombinationen also wiederholt.

Erwartet hätte ich (vermutlich jedoch in einer anderen Reihenfolge):

A1 B1 C1 
A2 B2 C2 
A3 B1 C1 
A1 B2 C2 
A2 B1 C1 
A3 B2 C2 
A1 B1 C2 
A2 B2 C1 
A3 B1 C2 
A1 B2 C1 
A2 B1 C2 
A3 B2 C1

Ich habe es bisher noch nicht hinbekommen, den Algorithmus so zu erweitern, dass die untere Ausgabe erzeugt wird. Kann da jemand helfen ? Oder muß man dann doch ganz andere Wege gehen (z.B eine rekursive Funktion) ?

Gruß
J-P

 

[Thomas Darimont]

Hallo,

schau mal hier:
http://www.tutorials.de/coders-talk/363032-permutationen.html

Gruß Tom