tất cả các tổ hợp có thể có của n bộ

Question

Tôi có n Bộ. mỗi Bộ có số lượng phần tử khác nhau. Tôi muốn viết một thuật toán cung cấp cho tôi tất cả các kết hợp có thể có từ các bộ. ví dụ: phép nói rằng chúng ta có:

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

một sự kết hợp sẽ giống như

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

.... và như vậy về số lượng các kết hợp có thể sẽ 2*3*4 = 24

Xin vui lòng giúp tôi viết thuật toán này trong Java.

Nhiều cảm ơn trước

Answer 1

Đệ quy là bạn của bạn:

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

Đáp lại câu hỏi từ OP về khái quát hóa nó để bộ Objects:

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

Và cuối cùng một biến thể lặp đi lặp lại . Nó dựa vào việc tăng một loạt các quầy nơi quầy kết thúc tốt đẹp và mang khi nó đạt đến kích thước của tập:

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

Trong trường hợp ai đó muốn ma trận thay vì in ấn, tôi chút thay đổi mã:

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