java - 从交错数组的每一行添加元素

Question

我试图通过仅使用每行中的 1 个元素来获取 n 行、锯齿状二维字符串数组中的每一个元素组合。

一个示例数组（每行代表数组中的一行）：

“A”、“B”、“C”

"D","E"

"F","G","H","I","J"

对于上述数组，将有 30 种可能的组合。欢迎使用递归解决方案，但出于内存使用原因，我更喜欢迭代解决方案。

Answer 1

这是一个使用模数的有趣的小方法：

public static void main(String args[]) {
    iterate(new String[][]{{"a","b","c"},{"d","e"},{"f","g","h","i"}});
}
static void iterate(String[][] jagged) {
    int count = 1;
    int[] divisors = new int[jagged.length];
    for (int j = 0; j < jagged.length; j++) {
        divisors[j] = count;
        count *= jagged[j].length;
    }
    for (int i = 0; i < count; i++) {
        String[] combination = new String[jagged.length];
        for (int j = 0; j < jagged.length; j++) {
            int mod = jagged[j].length;
            combination[j] = jagged[j][(i/divisors[j])%mod];
        }
        process(combination);
    }
}
static void process(String[] combination) {
    System.out.println(Arrays.toString(combination));
    // Do whatever you want here. Process as you go to save memory,
    // or add to a list to process later.
}

它的核心是combination[j] = jagged[j][(i/divisors[j])%mod]; divisors[j]早期长度的乘积，即使用较低索引数组可能的组合数量。mod是当前数组的长度。

如果您希望最后一个元素迭代得更快而第一个元素迭代得更慢，请在计算divisors/时颠倒顺序count，即j从jagged.length0 倒数。

Answer 2

n如果是一个变量，我想不出任何迭代解决您的问题的方法。

递归解决方案：

ArrayList<String> permutations = new ArrayList<String>();
generatePermutations ("", 0);

/** Where the function generatePermutations is defined as: **/

void generatePermutations (String s, int index) {
    if (index >= n) {
        permutations.add(s);
        return;
    }
    for (String a : myJaggedArray[index]) {
        generatePermutations (s + a, index + 1)
    }
}

Answer 3

这应该可以处理任何大小的锯齿状数组，但我只测试了大约 5 个案例。

我们的基本策略是使用数组来跟踪我们将从子数组中获取下一个元素的当前索引，一旦我们将一个序列放入 permutationArray，我们将增加最右边的索引。如果该索引等于最右边子数组的大小，那么我们将最右边的索引设为 0 并增加倒数第二个最右边的索引。如果该索引等于该子数组的大小，我们将该索引设为 0 并增加前一个索引。这个过程冒泡到第一个索引，直到我们没有更多的排列。

    char list[][] = new char[][] { { 'a', 'b', 'c' }, { 'd', 'e' },
            { 'f', 'g', 'h', 'i', 'j' } };

    int permutations = 1;
    for (int i = 0; i < list.length; ++i)
        permutations *= list[i].length;

    char permutationArray[][] = new char[permutations][list.length];

    // list of lengths of each subarray
    int listlength[] = new int[list.length];
    for (int i = 0; i < list.length; ++i)
        listlength[i] = list[i].length;

    // traverse list in a permutation, once this gets to the length then we
    // increase indicies starting from the right side
    int listindicies[] = new int[list.length];

    for (int i = 0; i < permutations; ++i) {
        for (int j = 0; j < list.length; ++j) {
            permutationArray[i][j] = list[j][listindicies[j]];

            if (j == (list.length - 1))
                listindicies[j]++;
        }

        // reset indicies if they are equal to the length of the array
        for (int k = list.length - 1; k >= 0; --k) {
            if (listindicies[k] == (listlength[k])) {
                listindicies[k] = 0;
                if (k != 0)
                    listindicies[k - 1]++;
            } else {
                break;
            }
        }

    }

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