java - 如何连接二维数组中的列？

Question

如何连接二维数组中的列？

a b c d
1 3 9 6
4 2 7 1

自动检查列数。

例如:

如果有四列那么应该考虑三种组合。

输出应该是:

先取两个组合:

ab ac ad bc bd cd
13 19 16 39 36 96
42 47 41 27 21 71

然后取三个组合:

abc abd bcd acd
139 136 396 196
427 421 271 471

我应该如何编码？

下面是我试图获得这两种组合的代码。我需要如何更改它才能获得上述输出？

for (int i = 0; i < row.size(); i++) {
    for (int j = 0; j < col.size(); j++) {
        for (int k = j + 1; k < col.size(); k++) {
            array1.add(col[j]);
            array2.add(col[k]);
            array.add(array1.get(j) + array2.get(k));
        }
    }
    System.out.println("array");
}

Answer 1

我发现这个问题很有趣，所以我最终花了一些时间来解决这个问题。 :)

一些观察:

• 对每一行执行相同的组合，因此问题可以简化为组合一行的列，然后对每一行应用相同的方法。
• 您似乎不是在寻找所有 排列，而是在寻找列与数组中后面的列组合的子集。 IE。您不需要 ab 和 ba，只需要 ab。
• 结果应包含 2..n-1 列的组合(其中 n 是列数)。 IE。您似乎不只想要 1 列(原始列)或 n 列(所有列的组合)。

如果我们根据观察来划分问题，找到解决方案会简单得多:

1. 查找一行中所有列的组合。这个问题也可以分为两个:

   a) 从 2..n-1(要组合的列数)迭代 - 我为 level 调用了它。也许不是最好的名字，但对我来说很有意义。

   b) 查找当前级别的所有组合并将它们添加到结果中。

2. 将其应用于数组中的每一行以生成最终结果数组。

如果这些观察给了你一些想法，你可能想停止阅读这里并自己尝试。自己解决这类问题比查看完成的解决方案要有趣得多。但是，如果您遇到困难 - 或者您已经解决了问题并想查看另一个(可能不同的)解决方案，请继续阅读。

算法

第 1 步:将列组合成一行。

a) 遍历级别 2..n-1。级别表示要合并的列数。

b) 找出组合列的值。

请注意，第一列是从 0..n 级范围中选择的。第二个来自 c1+1..n-level+1 范围(其中 c1 是第一个选择的列的索引)。 c2+2..n-level+2 范围内的第三个。依此类推，直到我们添加了正确数量的列。

c) 将组合列的值添加到结果中。

第 2 步:将第 1 步应用于输入数组中的每一行。

a) 遍历输入数组中的每一行。

b) 将步骤 1 应用到该行。

c) 将结果行添加到输出数组。

实现

第 1 步:RowCombine

import java.util.ArrayList;
import java.util.List;

public class RowCombine {

    String[] row;
    List<String> result = new ArrayList<String>();

    public RowCombine(String[] row) {
        this.row = row;
    }

    public String[] combine() {
        if (result.isEmpty()) {
            for (int level = 2; level < row.length; level++) {
                combine(level, 0, row.length - level, "");
            }
        }
        return result.toArray(new String[result.size()]);
    }

    private void combine(int level, int lower, int upper, String value) {
        if (level > 0) {
            for (int c = lower; c <= upper; c++) {
                combine(level - 1, c + 1, upper + 1, value + row[c]);
            }
        } else {
            result.add(value);
        }
    }
}

第 2 步:ArrayCombine

public class ArrayCombine {
    String[][] input;
    String[][] output;

    public ArrayCombine(String[][] input) {
        this.input = input;
    }

    public String[][] combineColumns() {
        if (output == null) {
            output = new String[input.length][];
            for (int i = 0; i < input.length; i++) {
                RowCombine rowCombine = new RowCombine(input[i]);
                output[i] = rowCombine.combine();
            }
        }
        return output;
    }

    public void print() {
        combineColumns();
        for (String[] row : output) {
            for (String value : row) {
                System.out.print(value + ' ');
            }
            System.out.println();
        }
    }
}

测试

运行

new ArrayCombine(new String[][]{
        { "a", "b", "c", "d"},
        { "1", "3", "9", "6"},
        { "4", "2", "7", "1"},
}).print();

产生

ab ac ad bc bd cd abc abd acd bcd 
13 19 16 39 36 96 139 136 196 396 
42 47 41 27 21 71 427 421 471 271 

它也适用于更高的维度，例如:

new ArrayCombine(new String[][]{
        { "a", "b", "c", "d", "e"},
        { "1", "3", "9", "6", "5"},
        { "4", "2", "7", "1", "1"},
}).print();

产生

ab ac ad ae bc bd be cd ce de abc abd abe acd ace ade bcd bce bde cde abcd abce abde acde bcde 
13 19 16 15 39 36 35 96 95 65 139 136 135 196 195 165 396 395 365 965 1396 1395 1365 1965 3965 
42 47 41 41 27 21 21 71 71 11 427 421 421 471 471 411 271 271 211 711 4271 4271 4211 4711 2711