How to concatenate the columns in an two dimensional array?

Question

How to concatenate the columns in an two dimensional array ?

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

Check the count of columns automatically.

For example:

If four columns are there then it should consider three combination.

Output should be:

First take two combination:

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

Then take three combination:

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

How should I code this?

Below is the code I tried to get the two combinations. How do I need to change it to get the above output?

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

I found this problem quite interesting, so I ended up spending some time with it. :)

A couple of observations:

• The same combinations are performed for each row, so the problem can be simplified to combining the columns of one row, and then apply the same method for each row.
• It seems that you are not looking for all permutations, but for the subset where the columns are combined with later columns in the array. I.e. you don't want both ab & ba, just ab.
• The result should consist of combinations of 2..n-1 columns (where n is the number of columns). I.e. you seem to not want only 1 column (the original columns) or n columns (the combination of all columns).

Finding a solution is much simpler if we divide the problem according to the observations:

1. Find all combinations of the columns in a single row. This problem can be divided in two as well:

   a) Iterate from 2..n-1 (number of columns to combine) - i called this for the level. Perhaps not the best name, but it made sense to me.

   b) Find all combinations for the current level and add these to the result.

2. Apply this to each row in the array to produce the final resulting array.

If these observations have given you some ideas, you may want to stop reading here and try for it yourself. It is much more fun to solve these kinds of problems yourself rather than look at a finished solution. However, if you are stuck -- or you have already solved and want to look at another (possibly different) solution, read ahead.

The algorithm

Step 1: Combine columns in one row.

a) Iterate over the levels 2..n-1. The level indicates the number of columns to combine.

b) Find the value of the combined columns.

Note that the first column is chose from the range 0..n-level. The second from the range c1+1..n-level+1 (where c1 is the index of the first chosen column). The third from the range c2+2..n-level+2. And so on, until we have added the correct number of columns.

c) Add the value of the combined columns to the result.

Step 2: Apply step 1 to each row in the input array.

a) Iterate over each row in the input array.

b) Apply step 1 to the row.

c) Add resulting row to output array.

The implementation

Step 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);
        }
    }
}

Step 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();
        }
    }
}

Testing

Running

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

produces

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 

It also works for higher dimensions, e.g:

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

produces

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