print combinations of elements in matrix of size m * n.
sample example:
1 3 5
2 6 7
expected output:
2 , 1
2 , 3
2 , 5
6 , 1
6 , 3
6 , 5
7 , 1
7 , 3
7 , 5
rules:
- every combination starts bottom of matrix , proceeds towards top. may switch columns though.
- every combination should have number of elements equal number of rows.
- combination can't have element same row present twice.
i never figure solution out general case. can use 3 loops. want understand recursive solution. use java.
here's non-recursive way solve problem (it's not pretty, works input). know interested in recursion, don't have @ moment. generally, avoid recursion due size of problems work (constant heap space errors due size of recursive stack when -xmx60g). hope helps.
private static list<int[]> combos; public static void main(string[] args){ combos = new arraylist<int[]>(); generate(new int[][]{{1,3,5},{2,6,7}}); for(int[] s : combos){ system.out.println(java.util.arrays.tostring(s)); } } private static void generate(int[][] elements) { int rows = elements.length; int[] elementsindex = new int[rows]; int[] elementstotals = new int[rows]; java.util.arrays.fill(elementstotals, elements[0].length); int curidx = 0; int[] c = new int[rows]; while(true){ while(curidx >= 0){ if(curidx == rows) { addcombo(c); curidx--; } if(elementsindex[curidx] == elementstotals[curidx]){ elementsindex[curidx] = 0; curidx--; } else break; } if(curidx < 0) break; // toggle order: // bottom up: elements[rows-curidx-1][elementsindex[curidx]++] // top down: elements[curidx][elementsindex[curidx]++] c[curidx] = elements[rows-curidx-1][elementsindex[curidx]++]; curidx++; } } private static void addcombo(int[] c){ int[] = new int[c.length]; system.arraycopy(c, 0, a, 0, c.length); combos.add(a); } 