alle mögliche Kombination von n Sätze

Question

Ich habe n Sets. Jedes Set hat eine unterschiedliche Anzahl von Elementen. Ich möchte einen Algorithmus schreiben, der mir alle möglichen Kombinationen aus den Sets gibt. zum Beispiel: Können sagen, wir haben:

S1={1,2}, S2={A,B,C}, S3={$,%,£,!} 

eine Kombination wie

C1={1,A,$} 
C2={1,A,%} 

.... und so auf die Anzahl der möglichen Kombinationen 2*3*4 = 24

Bitte um Hilfe wird aussehen sollte Ich schreibe diesen Algorithmus in Java.

Vielen Dank im Voraus

Answer 1

Rekursion ist dein Freund:

public class PrintSetComb{ 
    public static void main(String[] args){ 
     String[] set1 = {"1","2"}; 
     String[] set2 = {"A","B","C"}; 
     String[] set3 = {"$", "%", "£", "!"}; 
     String[][] sets = {set1, set2, set3}; 

     printCombinations(sets, 0, ""); 
    } 

    private static void printCombinations(String[][] sets, int n, String prefix){ 
     if(n >= sets.length){ 
      System.out.println("{"+prefix.substring(0,prefix.length()-1)+"}"); 
      return; 
     } 
     for(String s : sets[n]){ 
      printCombinations(sets, n+1, prefix+s+","); 
     } 
    } 
} 

Als Antwort von OP in Frage zu stellen, darüber zu Gruppen von Gegenständen zu verallgemeinern:

import java.util.Arrays; 

public class PrintSetComb{ 

    public static void main(String[] args){ 
     Integer[] set1 = {1,2}; 
     Float[] set2 = {2.0F,1.3F,2.8F}; 
     String[] set3 = {"$", "%", "£", "!"}; 
     Object[][] sets = {set1, set2, set3}; 

     printCombinations(sets, 0, new Object[0]); 
    } 

    private static void printCombinations(Object[][] sets, int n, Object[] prefix){ 
     if(n >= sets.length){ 
      String outp = "{"; 
      for(Object o: prefix){ 
       outp = outp+o.toString()+","; 
      } 
      System.out.println(outp.substring(0,outp.length()-1)+"}"); 
      return; 
     } 
     for(Object o : sets[n]){ 
      Object[] newPrefix = Arrays.copyOfRange(prefix,0,prefix.length+1); 
      newPrefix[newPrefix.length-1] = o; 
      printCombinations(sets, n+1, newPrefix); 
     } 
    } 
} 

Und schließlich eine iterative Variante . Es basiert auf einer Reihe von Zählern zu erhöhen, wo der Zähler Wraps und trägt, wenn sie die Größe der Menge erreicht:

import java.util.Arrays; 

public class PrintSetCombIterative{ 

    public static void main(String[] args){ 
      String[] set1 = {"1","2"}; 
      String[] set2 = {"A","B","C"}; 
      String[] set3 = {"$", "%", "£", "!"}; 
      Object[][] sets = {set1, set2, set3}; 

      printCombinations(sets); 
    } 


    private static void printCombinations(Object[][] sets){ 
     int[] counters = new int[sets.length]; 

     do{ 
      System.out.println(getCombinationString(counters, sets)); 
     }while(increment(counters, sets)); 
    } 

    private static boolean increment(int[] counters, Object[][] sets){ 
      for(int i=counters.length-1;i>=0;i--){ 
       if(counters[i] < sets[i].length-1){ 
        counters[i]++; 
        return true; 
       } else { 
        counters[i] = 0; 
       } 
      } 
      return false; 
    } 

    private static String getCombinationString(int[] counters, Object[][] sets){ 
     String combo = "{"; 
     for(int i = 0; i<counters.length;i++){ 
      combo = combo+sets[i][counters[i]]+","; 
     } 
     return combo.substring(0,combo.length()-1)+"}"; 

    } 
} 

Answer 2

In dem Fall, dass jemand wünscht, die Matrix anstelle von Druck, I leicht modifiziert den Code:

public class TestSetCombinations2 { 

    public static void main(String[] args) { 
     Double[] set1 = {2.0,3.0}; 
     Double[] set2 = {4.0,2.0,1.0}; 
     Double[] set3 = {3.0, 2.0, 1.0, 5.0}; 
     Double[] set4 = {1.0,1.0}; 
     Object[][] sets = {set1, set2, set3, set4}; 

     Object[][] combinations = getCombinations(sets); 

     for (int i = 0; i < combinations.length; i++) { 
      for (int j = 0; j < combinations[0].length; j++) { 
       System.out.print(combinations[i][j]+" "); 
      } 
      System.out.println(); 
     } 
    } 

    private static Object[][] getCombinations(Object[][] sets) { 

     int[] counters = new int[sets.length]; 
     int count = 1; 
     int count2 = 0; 

     for (int i = 0; i < sets.length; i++) { 
      count *= sets[i].length; 
     } 

     Object[][] combinations = new Object[count][sets.length]; 

     do{ 
      combinations[count2++] = getCombinationString(counters, sets); 
     } while(increment(counters, sets)); 

     return combinations; 
    } 

    private static Object[] getCombinationString(int[] counters, Object[][] sets) { 

     Object[] o = new Object[counters.length]; 
     for(int i = 0; i<counters.length;i++) { 
     o[i] = sets[i][counters[i]]; 
     } 
     return o; 

    } 

    private static boolean increment(int[] counters, Object[][] sets) { 
     for(int i=counters.length-1;i>=0;i--) { 
      if(counters[i] < sets[i].length-1) { 
       counters[i]++; 
       return true; 
      } else { 
       counters[i] = 0; 
      } 
     } 
     return false; 
    } 
}