打印二维锯齿状数组中的字符串组合

Question

假设我有一个字符串数组，如下所示：

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

我想打印数组的组合：

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

但是我希望锯齿状数组具有用户指定的行和列。如何以动态和迭代的方式创建 similar approach？此外，我正在使用数组而不是 ArrayList，因为作为初学者，我想在学习 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;
    }
}

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

每个 "digit" 到达相应子列表的末尾时将翻转，例如最后一个子列表只有 4 个元素，所以数字从 3 翻转到 0。

注意： A "digit" 可以计数大于 9。想想十六进制的一种表示方式。

现在，位数也是动态的，即外部列表的大小。使用简单循环执行此操作的一种方法是计算组合总数 (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

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

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

Answer 2

我的想法如下。假设我们有这个 2-d array

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

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

所以首先我们在 table.

中找到最大行 length

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 上的数字是否不高于 table.[=22 中 ith 行上的 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

Answer 3

这是另一种方法，它使用整数索引数组来模拟可变数量的嵌套 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;
        }
    }
}

Answer 4

你可以使用Stream.reduce方法。

Try it online!

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

^{另请参阅：}

打印二维锯齿状数组中的字符串组合

Print combinations of strings in a 2D jagged array

java

arrays

string

multidimensional-array

jagged-arrays