java - 组合发电机

Question

我有一个多维数组，其大小是动态的。

String[][] array=new String[][]{{"1","2","3"},{"4","5","6"},{"7","8","9"},{"10","11","12"} };

我需要生成组合，例如每个组合长度必须位于 1-array.length 之间，并且每个组合在一行中最多可以有一个元素。如果使用行中的一列，则该行中的其他列不能用于该组合。

例如 长度为 1 的组合是:

1
2
3
4
5
6
7
8
9
10
11
12

长度为 2 的组合为:

1,4
1,5
1,6
1,7
1,8
1,9
1,10
1,11
1,12

目前我只能得到 length = array.length 的组合，但我需要长度从 1 到 array.length

private String[][] generateCombinations(String[]... arrays) throws Throwable       {
    if (arrays.length == 0) {
        return new String[][]{{}};
    }
    int num = 1;
    for (int i = 0; i < arrays.length; i++) {
        num *= arrays[i].length;
    }

    String[][] result = new String[num][arrays.length];
    // array containing the indices of the Strings
    int[] combination = new int[arrays.length];

    for (int i = 0; i < num; i++) {
        String[] comb = result[i];
        // fill array
        for (int j = 0; j < arrays.length; j++) {
            comb[j] = arrays[j][combination[j]];
        }

        // generate next combination
        for (int j = 0; j < arrays.length; j++) {
            int n = ++combination[j];
            if (n >= arrays[j].length) {
                // "digit" exceeded valid range -> back to 0 and continue incrementing
                combination[j] = 0;
            } else {
                // "digit" still in valid range -> stop
                break;
            }
        }
    }
    return result;
}

Answer 1

你喜欢 1 个字母的变量名吗...？ :D 我什至不知道它现在是如何工作的。它使用位掩码来查找长度为 n 的子数组的每个组合；然后它使用一些 mod 数学从每个子数组中查找 1 的每个组合；然后它会吐出这个数字。排序顺序并不理想。

public class Perms {
    private static String[][] array = new String[][] {
        { "1", "2", "3" },
        { "4", "5", "6" },
        { "7", "8", "9" },
        { "10", "11", "12" }
    };
    private static int combinationLength = 2;
    public static void main(String[] args) {
        // Get combinations of subarrays
        for (int i = 0; i < Math.pow(2, array.length); ++i) {
            int c = 0;
            for (int j = 1; j <= Math.pow(2, array.length); j <<= 1)
                if ((i & j) != 0)
                    ++c;
            if (c == combinationLength) {
                String[][] maskedArray = new String[combinationLength][];
                for (int l = 1, j = 0, k = 0; l <= Math.pow(2, array.length); l <<= 1, ++j)
                    if ((i & l) != 0) {
                        maskedArray[k] = array[j];
                        ++k;
                    }
                // Get combinations of one element per subarray
                int l = 1;
                for (int j = 0; j < maskedArray.length; ++j)
                    l *= maskedArray[j].length;
                for (int j = 0; j < l; ++j) {
                    String s = "";
                    int m = j;
                    for (int k = maskedArray.length-1; k >= 0; --k) {
                        s = maskedArray[k][m % maskedArray[k].length] + "," + s;
                        m /= maskedArray[k].length;
                    }
                    // Spit out a result
                    System.out.println(s.substring(0, s.length()-1));
                }
            }
        }
    }
}