所有可能的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)+"}";

    }
}