Recursive divide array

Question

I need to get a number of all possible ways to divide array into small sub-arrays. We can divide array verticaly and horizontaly. My algorithm works very good, but time complexity is too bad. Can you have a look how to improve it?

Parameters

nStart - first row of sub-array

nEnd - last row of sub-array

mStart, mEnd - are for second dimension (columns).

check() - functions checking end condition

return - numbers of different ways to divide array. We divide while function check return true.

public static long divide(int nStart, int nEnd, int mStart, int mEnd) {
    long result = 0;

    for(int i = 1; i < nEnd - nStart; i++) {
        if(check(nStart, nStart + i, mStart, mEnd) && check(nStart + i, nEnd, mStart, mEnd))
            result += divide(nStart, nStart + i, mStart, mEnd) * divide(nStart + i, nEnd, mStart, mEnd);
    }

    for(int i = 1; i < mEnd - mStart; i++) {
        if(check(nStart, nEnd, mStart, mStart + i) && check(nStart, nEnd, mStart + i, mEnd)) 
            result += divide(nStart, nEnd, mStart, mStart + i) * divide(nStart, nEnd, mStart + i, mEnd);
    }

    return (result == 0 ? 1 : result) % 1000000000; 
}

Example

Input

2 2 10 01

Output 2

Input

3 2 101 010

Output 5

I think you need to know how check() function works. We stop dividing when next subarray have only ones or only zeros. Here is code:

public static boolean check(int nStart, int nEnd, int mStart, int mEnd) {
    if((nEnd - nStart) + (mEnd - mStart) == 2) 
        return false;
    for(int i = mStart; i < mEnd; i++) {
        for(int j = nStart; j < nEnd; j++) {
            if(bar[i][j] != bar[mStart][nStart])
                return true;
        }
    }
    return false;
}

Answer 1

By looking at your code I can see that in each step of the recursion you divide your two-dimensional array into two arrays with a single horizontal or vertical cut. Then you verify that both of these parts fulfil some condition of yours defined by the check-method and, if so, then you put these two parts into a recursion. When the recursion can no longer be continued, you return 1. Below I assume that your algorithm always produces the result you want.

I'm afraid that an effective optimization of this algorithm is highly dependent on what the check-condition does. In the trivial case it would always retuns true, when the problem collapsed into a straightforward mathematical problem that propably has a general non-recursive solution. A bit more complex, but still effectively solvable would be a scenario where the condition would only check the shape of the array, meaning that e.g. check(1,5,1,4) would return the same result as check(3,7,5,8).

The most complex is of course a general solution, where the check-condition can be anything. In this case there is not much that can be done to optimize your brute force solution, but one thing that comes to my mind is adding a memory to you algorithm. You could use the java.awt.Rectangle class (or create your own class) that would hold the dimensions of a sub-array and then have a java.util.HashMap to store the results of the executions of the divide-method for furure reference, if the method is called again with the same parameters. This would prevent duplicate work that will propaply occur.

So you define the haspmap as a static variable in you class:

static HashMap<Rectangle,Long> map = new HashMap<Rectangle,Long>();

then in the beginning of the divide-method you add the following code:

Rectangle r = new Rectangle(nStart,mStart,nEnd,mEnd);
Long storedRes = map.get(r);
if (storedRes != null) {
    return storedRes;
}

and then you change the ending of the method into form:

result = (result == 0 ? 1 : result) % 1000000000;
map.put(r, result);
return result;

This should give a performance-boost for your algorithm.

To return to my earlier tought, if the check-condition is simple enough, this same optimization can be done even more effectively. For example, if your check-condition only checks the shape of the array, you will only need to have its width and height as a key to the map, which will decrease the size of the map and multiple the number of positive hits in it.