CODEWITHSUNDEEP
javaalgorithmmatrixcombinations
eygrr
eygrr

Reputation: 319

Combinations without repetition of a matrix

I have a matrix contained in a two-dimensional array.

int[][] combinationValues

This array can vary in size, however using the test cases I have right now its maximum size has been 6 by 6.

This matrix is a set of non-distinct integers, an example value would be...

[1][1,2,3]
[2][4,5,6]
[3][7,8,9]

I'm looking to obtain an array/list of all of the combinations of these values without repetitions, taking only one value from each row. So using the previous example value, the result would be...

[1,5,9] , [1,6,8] , [2,4,9] , [2,7,6] , [3,4,8] , [3,5,7]

So the following results would not be correct.

[1,4,7] //three from the first row
[1,5,8] //two from the second row

If you can help me, pseudocode is very welcome, however I am currently using Java for my implementation.

Upvotes: 1

Views: 549

Answers (2)

Serge Ballesta
Serge Ballesta

Reputation: 148965

So you want one element by row and by column ? Simply combinatory analyze says that you should get n! solutions.

You can easily backtrack in java or any other language that can dynamically append to lists

Pseudo-code :

void test(List<List<Integer>> matrix, int row, int column, List<List<Integer>> results,
        List<Integer> current, List<Integer> used)
    // tries to add a new value to current result
    if used does not contain j {
        add matrix[i][j] to list current
        add j to list used
        if i is last row (i == matrix.size() -1) {
            add result to list results
        }
        else {         // processes next row
            for(int k=0, k<matrix[0].size(); k++) {
                test(matrix, i+1, k, results, current, used)
            }
        }
    }
}

Main code : 

List<List<Integer>> results = new ArrayList<List<Integer>>(); // initializes results
for (i=0; i<matrix[0].size(); i++) {  // try each element of first line
    test(matrix, 0, i, results, new ArrayList<Integer>(), new ArrayList<Integer>())
}

Upvotes: 1

Luiggi Mendoza
Luiggi Mendoza

Reputation: 85779

This is a basic idea to solve the problem:

  • Use an array (or another collection) that will store the indexes that are used (the duplicates)
  • For 0 to the last possible index available:
    • Check if the index is already marked as duplicate
    • If it's a duplicate, then move to the next index
    • If it's not a duplicate, then
      • Go to the next possible array
      • Get the element at that index
      • Add the index to the array (or collection) to mark it as duplicate
      • Repeat this same process in the for for the available arrays
      • Remove the index to the array (or collection) to unmark it as duplicate

Upvotes: 1

Related Questions