すべての可能な組み合わせnセット

Question

私はn個のセットを持っています。各セットは異なる数の要素を有する。私はセットからすべての可能な組み合わせを与えるアルゴリズムを書こうと思います。例えば ：助けてください

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

組み合わせが

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

のようになります....ので、可能な組み合わせの数に2*3*4 = 24

次のようになります。 は、我々が持っているとしましょう私はJavaでこのアルゴリズムを書く。アドバンス

で

感謝

Answer 1

再帰はあなたの友達です：

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+","); 
     } 
    } 
} 

応答内のオブジェクトのセットに、それを一般化についてはOPからの質問：

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); 
     } 
    } 
} 

そして最後に、反復バリアント。これは、ここでカウンタラップカウンタの配列の増加に基づいており、それはセットのサイズに達したときに担持されている：

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

場合、誰かが代わりに印刷のマトリックスを望んで、私はわずかにコードを変更し：

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; 
    } 
}