Results 1 to 20 of 24
 08262013, 02:06 AM #1Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
optimise recursive method that prints all possible rows in a 2D array
Hi, I have a method below that takes an int[][] array (column,row) and creates a new int[] array for every possible combination of rows in the grid, this method works even if the column lengths are different.
The problem is that It creates too much garbage for the GC when using a big grid due to the creation of new array Objects inside each loop of each recursion. I would like to dispense with the "new TIntArrayList" but I don't know how to do it without ruining the logic of the method. Ideally I would like to change the method so it uses only loops instead of recursion to eliminate the method call overhead as I don't think the VM is inlineing the compiled code.
Java Code:public static void AllRowCombinations(int[][] grid, int column, TIntArrayList aRow, ArrayList<int[]> finalRows) { if (column > grid.length  1) { finalRows.add(aRow.toArray()); return; } for (int k : grid[column]) { TIntArrayList row = new TIntArrayList(aRow.toArray()); row.add(k); AllRowCombinations(grid, column + 1, row,finalRows); } }
 08262013, 04:58 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
Re: optimise recursive method that prints all possible rows in a 2D array
Can you give an example (a small matrix and its result)?
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 08262013, 11:07 PM #3Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
Re: optimise recursive method that prints all possible rows in a 2D array
here you go>
Java Code:int[][] grid = new int[][]{{1,2,3},{4,5},{6,7,8}}; ArrayList<int[]> result = new ArrayList<>(); AllRowCombinations(grid,0,new TIntArrayList(),result); for(int[] ary : result) System.out.println(Arrays.toString(ary));
[1, 4, 6]
[1, 4, 7]
[1, 4, 8]
[1, 5, 6]
[1, 5, 7]
[1, 5, 8]
[2, 4, 6]
[2, 4, 7]
[2, 4, 8]
[2, 5, 6]
[2, 5, 7]
[2, 5, 8]
[3, 4, 6]
[3, 4, 7]
[3, 4, 8]
[3, 5, 6]
[3, 5, 7]
[3, 5, 8]
 08272013, 10:02 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
Re: optimise recursive method that prints all possible rows in a 2D array
Yes, it can be done iteratively; a few observations; if the original matrix has n rows, each combination has n elements. Have another array ready with n elements, where each element is a column index in a row of the original matrix. Obviously element i of that other matrix has to be in the range [0, m) where m is the length of the corresponding row in the original matrix. This is how one combination is generated:
Java Code:int[] comb(int[] index, int[][] matrix) { int[] c= new int[index.length]; for (i= 0; i < index.length; i++) c[i]= matrix[i][index[i]]; return c; }
Java Code:boolean next(int[] index, int[][] matrix) { for (int i= index.length ; i > 0) if (++index[i] >= matri[i].length) index[i]= 0; else return true; return false; }
Java Code:int[] index= new int[matrix.length]; do { process(comb(index, matrix); } while (next(index, matrix);
JosBuild a wall around Donald Trump; I'll pay for it.
 08282013, 12:05 AM #5Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
Re: optimise recursive method that prints all possible rows in a 2D array
Thanks, jos, the code works a treat. Its much faster than the recursive version and the garbage collector hardly ever runs, thanks again.
 08282013, 08:58 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
Re: optimise recursive method that prints all possible rows in a 2D array
You're welcome of course; you can even do better than my implementation if you don't want to keep all those combinations (just print them or process them once). My comb( ... ) method builds a new array 'c' each time it is called (where the combination is stored). You could also pass in an array for the storage and use it over and over again.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 08282013, 05:56 PM #7Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,152
 Rep Power
 12
Re: optimise recursive method that prints all possible rows in a 2D array
Here was my approach. Parts are similar to Jos' (no insult intended). I wrote down the required indices on paper and saw a pattern and then tried to produce the pattern.
Java Code:public class Combo { public static void main(String... args) { int [][] g = {{1,2,3},{4,5},{6,7,8}}; int n = 1; for (int j = 0; j < g.length; j++) { n *= g[j].length; } int i[] = new int[g.length]; for (int k = 0; k < n; k++) { for (int rr = 0; rr < g.length; rr++) { System.out.print(g[rr][i[rr]] + " "); } System.out.println(); i[g.length1]++; for (int j = g.length1; j > 0; j) { if (i[j] >= g[j].length) { i[j] = 0; i[j  1]++; } else break; } } } }
Regards,
JimLast edited by jim829; 08282013 at 06:57 PM.
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08292013, 02:39 AM #8Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
Re: optimise recursive method that prints all possible rows in a 2D array
Thanks for the input jim.
I tested both of your algorithms on a 7x16 matrix producing 260 million rows. The jos version takes 39.794 seconds and jims version takes 40.193 seconds (on one core @ 4.2Ghz) so they are the same pretty much.
I recon the additional loop in jims version adds a tiny bit of overhead and the VM seems to be inlineing the two methods of joses version which would eliminate the method call overhead but i'm nit picking really.
Both versions are at least twice as fast as my initial recursive version, which is mostly due to not needing to create new objects for each element.
Thank you for both for your contributions they are most welcome.
 08292013, 02:46 AM #9Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,152
 Rep Power
 12
Re: optimise recursive method that prints all possible rows in a 2D array
Yeah! I went back to this just after I posted it and eliminated my initial loop of creating n. It isn't needed. So lines 4 thru 7 can be eliminatated. Actually I couldn't figure a real way to implement recursion for this. I had to pass references so nothing was really saved on the stack. So my recursive algorithm was more or less nothing but a loop.
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08292013, 09:03 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
 08292013, 09:11 AM #11
Re: optimise recursive method that prints all possible rows in a 2D array
Add the 0.4 seconds it takes Jos to down a Grolsch and Jim's version is faster ...
If you're forever cleaning cobwebs, it's time to get rid of the spiders.
 08292013, 09:38 AM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
 08292013, 12:13 PM #13Just a guy
 Join Date
 Jun 2013
 Location
 Netherlands
 Posts
 5,114
 Rep Power
 10
Re: optimise recursive method that prints all possible rows in a 2D array
"Syntactic sugar causes cancer of the semicolon."  Alan Perlis
 08292013, 04:25 PM #14Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,152
 Rep Power
 12
Re: optimise recursive method that prints all possible rows in a 2D array
And subtract .7 seconds for the fact the Jos probably wrote it in a stupor and he still wins!
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08292013, 04:57 PM #15
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
 08292013, 10:19 PM #16Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
Re: optimise recursive method that prints all possible rows in a 2D array
The problem is not the warm up but the GC pauses and heap reSizes. I set java to use 20GB of heap from the start with the xms flag to stop the reSizes but It will still do a collection of the young generation (stops the world and clears the cpus L2 cache) a few times even when its only using 5gb of the 20GB heap which is not something you can control. 260 million int[7] arrays is about 30 bytes per int[7] for a total of 7.8GB not including the ArrayList<int[]> with 265 million elements.
On my first try I forgot to give the arrayList 265 million elements at creation time resulting in twice the run time, just shows how inefficient the arrayList reSize operation is.
What strikes me as funny is that the algorithms of jos and jims to create every combination of rows in a matrix is much more elegant than the somewhat simpler task i'm now faced with, which is creating every combination of values from a single int[] array (each unique row from the matrix). I've seen impementations of the Steinhaus–Johnson–Trotter algorithm which is most commonly use for this task but they are not very compact to say the least.
eg, PermutationUtils xref
Maybe the approach that jos used by having an index array and then modifying the index Array separately to the main loop might be quicker than the Steinhaus–Johnson–Trotter algorithm but I haven't got round to testing it yet.
 08302013, 12:18 AM #17Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,152
 Rep Power
 12
Re: optimise recursive method that prints all possible rows in a 2D array
If your interested, here is my final version. I documented the changes with explanations.
Java Code:private static List<int[]> toRows(int[][] g) { int i[] = new int[g.length]; List<int[]> list = new ArrayList<>(); /** In stead of calculating max number of entries, just loop until the first index exceeds number of "rows" of supplied matrix */ while (i[0] < g.length) { int[] v = new int[g.length]; for (int rr = 0; rr < g.length; rr++) { v[rr] = g[rr][i[rr]]; } list.add(v); int j = g.length  1; i[j]++; /** Earlier for loop with break is basically a while loop */ while (j > 0 && i[j] >= g[j].length) { i[j] = 0; i[j]++; } } return list; }
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08302013, 03:47 AM #18Member
 Join Date
 Sep 2008
 Posts
 14
 Rep Power
 0
Re: optimise recursive method that prints all possible rows in a 2D array
thanks again jim, it certainly makes it easier to read and it might be a bit faster without that loop.
 08302013, 04:51 AM #19Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,152
 Rep Power
 12
Re: optimise recursive method that prints all possible rows in a 2D array
Well, nuts! I thought I did the boundary case testing but my second "improved" version seems to have problems. My first one is better (takes care of null lists and other poorly formed matrices because they are 0 length and no iteration will happen). I just read an article about "optimizing" ones code. It goes something like this. Don't optimize! Unless you are sure of your solution. And then don't optimize. I clearly violated that tenet.
Note to self: leave well enough alone!
Regards,
JimLast edited by jim829; 08302013 at 05:16 AM.
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08302013, 09:01 AM #20
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
Re: optimise recursive method that prints all possible rows in a 2D array
That stuff is about permutations, not combinations. The particular algoarithm generates permutations by swapping adjacent elements (only two of them) for each permutation. If you're interested, I can give you a much shorter iterative algorithm that also generates all permutations (no additional storage needs, just one method boolean nextPermutation(int[] perm);)
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

Recursive method to sort array
By artur in forum New To JavaReplies: 2Last Post: 03192012, 01:49 PM 
Recursive method that checks if the first n elements of an array is sorted?
By matrixcool in forum New To JavaReplies: 8Last Post: 01152011, 10:39 PM 
Array out of bound Recursive Method
By hpayandah in forum New To JavaReplies: 2Last Post: 11122010, 09:02 PM 
Recursive method using int array, help needed
By chupalo17 in forum New To JavaReplies: 4Last Post: 09082009, 12:15 AM 
Recursive Method ==> find minimum value from array
By NatNat in forum New To JavaReplies: 1Last Post: 02162008, 10:10 PM
Bookmarks