To minimize heavy use of recursion?

Question

I am quite new in programming and JAVA. I have created a simple JAVA code for the generation of S-permutation matrices. S- permutation matrices are the square matrices which have 1 in each row, each column and each block exactly once e.g.

                     1 0 0 * 0 0 0 * 0 0 0 
                     0 0 0 * 1 0 0 * 0 0 0 
                     0 0 0 * 0 0 0 * 1 0 0
                    ***********************
                     0 1 0 * 0 0 0 * 0 0 0 
                     0 0 0 * 0 1 0 * 0 0 0 
                     0 0 0 * 0 0 0 * 0 1 0 
                    ***********************
                     0 0 1 * 0 0 0 * 0 0 0 
                     0 0 0 * 0 0 1 * 0 0 0 
                     0 0 0 * 0 0 0 * 0 0 1

Above is an example of 9 X 9 S-permutation matrix.

4 x 4 example is

                     1 0 * 0 0
                     0 0 * 1 0
                    ***********
                     0 1 * 0 0
                     0 0 * 0 1

I made a Java code for 4 X 4 and it is generating all 4 X 4 S-permutation matrices which are 16 in number. But with the same logic when I did it for 9 X 9 the program is giving some matrices and then showing stackoverflow error.

These 9 X 9 S-permutation matrices are 46656 in number. The program is giving some 2000 matrices and then showing stackoverflow error. I asked some of my friends and searched on google and think either the logic of the program is at fault or it is because of heavy use of recursion in the program.

Would any one please help me regarding this and tell me how can I minimize use of recursion. I read on some site that one way is of using loops but there is no way of using loops for that. Kindly tell me is there any other way for it?

Program which I am gonna share is the second program I made and it is giving only around 300 matrices..http://pastebin.com/2LBCCcE9

Can you share your code? It is hard to tell you how to replace recursion/find your problem, when we don't see your code. Or your code is too long mayby? — Beri, Nov 04 '14 at 10:24
if you have an stackoverflow you may have a excessive recursion or large objects in the stack or more commonly a combination of both. — Picarus, Nov 04 '14 at 10:34
"*I read on some site that one way is of using loops but there is no way of using loops for that.*" Better do your research: http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration. The answer is, no, there is no other (reliable) way, go loops. At least at some level.Sticking to recursion will allow only to increase problem size some extent, but the complexity is quite high so you will hit new limits pretty soon... or you can increase stack size. — luk32, Nov 04 '14 at 10:34
by the way, can you share an example of a 4x4 S-permutation? I can't imagine how is the 4th dimension taken in consideration — Picarus, Nov 04 '14 at 10:34
Unrelated to the question directly, but it might help to simplify things a little. Consider using a list of lists that you generate as needed rather than writing in each list, i.e. ArrayList> with a for loop that adds N lists where N is number of rows. That will allow a lot of your logic later on to be minimised down considerably (for instance all those ifs can go) and as you want to scale up it will be a lot easier. — FelixMarcus, Nov 04 '14 at 10:54
Yeah I need these suggestions to simplify things...Thanks all..:) — parni, Nov 04 '14 at 11:03

score 1 · Answer 1 · answered Nov 04 '14 at 11:07

I think you should go for a different way of representing your matrix.

For example, instead of actually creating array lists of array lists, try to represent the rows with numbers. You know that each row has only one column that is "1", and all the rest are zero. Instead of representing such a row as an array list, just use the index of the column that is 1:

1 0 0 0 0 0 0 0 0 → 0
0 1 0 0 0 0 0 0 0 → 1
0 0 1 0 0 0 0 0 0 → 2
0 0 0 1 0 0 0 0 0 → 3
0 0 0 0 1 0 0 0 0 → 4
0 0 0 0 0 1 0 0 0 → 5
0 0 0 0 0 0 1 0 0 → 6
0 0 0 0 0 0 0 1 0 → 7
0 0 0 0 0 0 0 0 1 → 8

Now, any legal matrix will be a permutation of these numbers, for example,

1 0 2 4 5 8 6 7 3

Is a representation of the matrix

0 1 0 0 0 0 0 0 0 → 1
1 0 0 0 0 0 0 0 0 → 0
0 0 1 0 0 0 0 0 0 → 2
0 0 0 0 1 0 0 0 0 → 4
0 0 0 0 0 1 0 0 0 → 5
0 0 0 0 0 0 0 0 1 → 8
0 0 0 0 0 0 1 0 0 → 6
0 0 0 0 0 0 0 1 0 → 7
0 0 0 1 0 0 0 0 0 → 3

So a simple array of 9 integers can now represent a whole matrix. And this matrix is guaranteed to fulfill the constraints on row and column uniqueness (do you understand why?)

So what you do now is try to generate all the permutations of these nine numbers - it's a much easier problem.

Write a method that accepts such a permutation as parameter, and checks whether it also fulfills the constraints on the blocks.

   private boolean checkBlocks( int[] matrix, int blockWidth ) {
      // Your code for checking here
   }

Inside this method you can reconstruct the matrix as an array of arrays or whatever that will help you check the constraint, and you check it, and return true if the blocks are OK, and false if not.

Now, all you have to do is generate all the permutation of the array [ 0 1 2 3 4 5 6 7 8 9 ], pass each of them to checkBlocks method, and only keep the ones which returned true.

The recursion for the permutations of 9 numbers is no more than 9 deep, and for such small arrays, I'm sure you will have no problem of Stack Overflow.

I had not thought about it in this way...thank you so much...I'll try with this logic now...thanks again...:) — parni, Nov 04 '14 at 11:14

To minimize heavy use of recursion?

1 Answers1