在一个二维锯齿数组中打印字符串的组合。

Question

假设我有一个字符串数组，看起来像这样：

{{"blue", "red"}, {"1", "2", "3"}, {"dog", "cat", "fish", "bird"}}

我想要打印数组的组合：

blue 1 dog
blue 1 cat
...
...
red 3 bird

然而我希望这个不规则数组的行和列是用户指定的。我如何用一种动态迭代的方式创建 类似的方法 呢？另外，由于作为初学者我想先看看我能在数组中做什么，所以我使用的是数组而不是 ArrayList。我的代码如下：

Scanner input = new Scanner(System.in);
System.out.print("Enter number of arrays: ");
int arrays = input.nextInt();
String[][] array = new String[arrays][];

for (int i = 0; i < x; i++) {
    System.out.print("Enter number of elements for array: ");
    int elements = input.nextInt();
    input.nextLine();
    arrays[i] = new String[elements];

    for (int j = 0; j < elements; j++) {
        System.out.print("Enter string: ");
        String word = input.nextLine();
        arrays[i][j] = word;
    }
}

- dollaza

---

因为程序每次运行时都会有不同的行数和列数，所以数组并不是一个用户友好的对象。使用ArrayList将使您的工作变得更加轻松。由于您是一名新手程序员，我建议您花费额外的10-30分钟来了解ArrayList，这可能会节省您与数组一起工作的时间。这只是一个建议。 - RAZ_Muh_Taz

Answer 1

这个答案将打印所有的组合，不使用递归，但是如果组合的总数超过Long.MAX_VALUE，则会失败。由于打印那么多行永远不会结束，所以这实际上不是问题。

要按顺序打印组合，请考虑一个递增的数字，其中数字的每个位是相应子列表中的索引。

示例（使用问题中的列表）：

000: blue 1 dog
001: blue 1 cat
002: blue 1 fish
003: blue 1 bird
010: blue 2 dog
...
121: red 3 cat
122: red 3 fish
123: red 3 bird

每个“数字”在到达相应子列表的末尾时都会翻转，例如：最后一个子列表只有4个元素，所以数字从3翻转到0。

注意：一个“数字”可以计数高于9。比如16进制的表示方法。

现在，“数字”的数量也是动态的，即外部列表的大小。使用简单循环的一种方法是计算组合总数（2 * 3 * 4 = 24），然后使用除法和余数来计算数字。

例如：

Combination #10 (first combination is #0):
  10 % 4                 = 2 (last digit)
  10 / 4 % 3     = 2 % 3 = 2 (middle digit)
  10 / 4 / 3 % 2 = 0 % 2 = 0 (first digit)
  Digits: 022 = blue 3 fish

为了帮助实现这一点，我们首先构建一个除数数组，例如div[] = { 12, 4, 1 }，并找到组合的总数（24）。

long[] div = new long[array.length];
long total = 1;
for (int i = array.length - 1; i >= 0; i--) {
    div[i] = total;
    if ((total *= array[i].length) <= 0)
        throw new IllegalStateException("Overflow or empty sublist");
}

现在我们可以循环遍历组合并打印结果：

for (long combo = 0; combo < total; combo++) {
    for (int i = 0; i < array.length; i++) {
        int digit = (int) (combo / div[i] % array[i].length);
        if (i != 0)
            System.out.print(' ');
        System.out.print(array[i][digit]);
    }
    System.out.println();
}

根据问题提供的信息：

String[][] array = {{"blue", "red"}, {"1", "2", "3"}, {"dog","cat", "fish", "bird"}};

我们得到以下输出：

blue 1 dog
blue 1 cat
blue 1 fish
blue 1 bird
blue 2 dog
blue 2 cat
blue 2 fish
blue 2 bird
blue 3 dog
blue 3 cat
blue 3 fish
blue 3 bird
red 1 dog
red 1 cat
red 1 fish
red 1 bird
red 2 dog
red 2 cat
red 2 fish
red 2 bird
red 3 dog
red 3 cat
red 3 fish
red 3 bird

它可以处理任何子数组的组合，例如具有大小为2、3、2和2的4个子数组:

String[][] array = {{"small", "large"}, {"black", "tan", "silver"}, {"lazy", "happy"}, {"dog", "cat"}};

small black lazy dog
small black lazy cat
small black happy dog
small black happy cat
small tan lazy dog
small tan lazy cat
small tan happy dog
small tan happy cat
small silver lazy dog
small silver lazy cat
small silver happy dog
small silver happy cat
large black lazy dog
large black lazy cat
large black happy dog
large black happy cat
large tan lazy dog
large tan lazy cat
large tan happy dog
large tan happy cat
large silver lazy dog
large silver lazy cat
large silver happy dog
large silver happy cat

- Andreas

Answer 2

这里有另一种方法，它使用整数索引数组来模拟可变数量的嵌套for循环：

Scanner input = new Scanner(System.in);
System.out.print("Enter number of arrays: ");
int arrays = input.nextInt();
String[][] array = new String[arrays][];

for (int i = 0; i < arrays; i++) {
    System.out.print("Enter number of elements for array #" + i + ": ");
    int elements = input.nextInt();
    input.nextLine();
    array[i] = new String[elements];

    for (int j = 0; j < elements; j++) {
        System.out.print("Enter string: ");
        String word = input.nextLine();
        array[i][j] = word;
    }
}

int[] indices = new int[array.length];
while (indices[0] < array[0].length) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < indices.length; ++i) {
        if (i > 0) {
            sb.append(' ');
        }
        sb.append(array[i][indices[i]]);
    }
    System.out.println(sb.toString());
    for (int i = indices.length - 1; i >= 0; --i) {
        if (++indices[i] < array[i].length) {
            break;
        }
        if (i != 0) {
            indices[i] = 0;
        }
    }
}

- Kevin Anderson

Answer 3

我的想法如下。假设我们有这个2维数组

String[][] strings = {{"blue", "red"},
                      {"1", "2", "3"},
                      {"dog", "cat", "bird", "fish"}};

我们可以在数组内生成排列，但需要包含一些条件。

首先，我们要找到表格中最大行的长度。

int max = 0;
for (int i = 0; i < strings.length; i++) {
    if(max < strings[i].length) {
        max = strings[i].length;
    }
}

然后我们只需生成排列。

int[] permutations = new int[strings.length];

void permute(int k) {
    for(int i = 0; i < max; i++) {
        permutations[k] = i;
        if(valid(k)) {
            if(k == strings.length - 1) {
                printSolution();
            } else {
                permute(k + 1);
            }
        }
    }
}

valid函数检查在我们的表格中第i行上，位置为i的数字不超过length。

boolean valid(int k) {
    for(int i = 0; i < k; i++) {
        if(permutations[i] >= strings[i].length) return false;
    }
    return true;
}

打印解决方案的方法：

void printSolution() {
    for(int i = 0; i < strings.length; i++) {
        System.out.print(strings[i][permutations[i]] + " ");
    }
    System.out.println();
}

并且结果是：

blue 1 dog 
blue 1 cat 
blue 1 bird 
blue 1 fish 
blue 2 dog 
blue 2 cat 
blue 2 bird  
blue 2 fish 
blue 3 dog 
blue 3 cat 
blue 3 bird 
blue 3 fish 
red 1 dog 
red 1 cat 
red 1 bird 
red 1 fish 
red 2 dog 
red 2 cat 
red 2 bird 
red 2 fish 
red 3 dog 
red 3 cat 
red 3 bird 
red 3 fish 

- Schidu Luca

Answer 4

你可以使用 Stream.reduce 方法。

在线试用！

// original array
String[][] array = {
        {"blue", "red"},
        {"1", "2", "3"},
        {"dog", "cat", "fish", "bird"}};

// array of combinations
String[] combinations = Arrays.stream(array)
        // pairs of a 1D arrays into a single array
        .reduce((arr1, arr2) -> Arrays.stream(arr1)
                // concatenate pairs of strings from two arrays
                .flatMap(str1 -> Arrays.stream(arr2)
                        .map(str2 -> str1 + " " + str2))
                .toArray(String[]::new))
        .orElse(new String[0]);

// column-wise output
int rows = 4;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < combinations.length; j++) {
        if (j % rows == i)
            System.out.print(
                    (combinations[j] + ";   ").substring(0, 13));
    }
    System.out.println();
}

按列输出：

blue 1 dog;  blue 2 dog;  blue 3 dog;  red 1 dog;   red 2 dog;   red 3 dog;   
blue 1 cat;  blue 2 cat;  blue 3 cat;  red 1 cat;   red 2 cat;   red 3 cat;   
blue 1 fish; blue 2 fish; blue 3 fish; red 1 fish;  red 2 fish;  red 3 fish;  
blue 1 bird; blue 2 bird; blue 3 bird; red 1 bird;  red 2 bird;  red 3 bird;  

---

^{另请参阅：如何生成两个数组的组合？}

- user16649492