Optimizing an algorithm java

Given a graph of length M x N, all paths from (0,0) to (M-1, N-1) that only involve rightward and downward moves are guaranteed to contain exactly M-1 moves rightward and N-1 moves downward.

This presents us with an interesting property: we can represent a path from (0,0) to (M-1, N-1) as a binary string (0 indicating a rightward move and 1 indicating a downward move).

So, the question becomes: how fast can we print out a list of permutations of that bit string?

Pretty fast.

public static void printPaths(char[][] arr) {
    /* Get Smallest Bitstring (e.g. 0000...111) */
    long current = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        current <<= 1;
        current |= 1;
    }

    /* Get Largest Bitstring (e.g. 111...0000) */
    long last = current;
    for (int i = 0; i < arr[0].length - 1; i++) {
        last <<= 1;
    }

    while (current <= last) {
        /* Print Path */
        int x = 0, y = 0;
        long tmp = current;
        StringBuilder sb = new StringBuilder(arr.length + arr[0].length);
        while (x < arr.length && y < arr[0].length) {
            sb.append(arr[x][y]);
            if ((tmp & 1) == 1) {
                x++;
            } else {
                y++;
            }
            tmp >>= 1;
        }
        System.out.println(sb.toString());

        /* Get Next Permutation */
        tmp = (current | (current - 1)) + 1;
        current = tmp | ((((tmp & -tmp) / (current & -current)) >> 1) - 1);
    }
}

You spend a lot of time on string memory management.
Are strings in Java mutable? If you can change chars inside string, then set length of string as n+m, and use this the only string, setting (i+j)th char at every iteration. If they are not mutable, use array of char or something similar, and transform it to string at the end

For a given size N×M of the array all your paths have N+M+1 items (N+M steps), so the first step of optimization is getting rid of recursion, allocating an array and running the recursion with while on explicit stack.

Each partial path can be extended with one or two steps: right or down. So you can easily make an explicit stack with positions visited and a step taken on each position. Put the position (0,0) to the stack with phase (step taken) 'none', then:

while stack not empty {
    if stack is full /* reached lower-right corner, path complete */ {
        print the path;
        pop;
    }
    else if stack.top.phase == none {
        stack.top.phase = right;
        try push right-neighbor with phase none;
    }
    else if stack.top.phase == right {
        stack.top.phase = down;
        try push down-neighbor with phase none;
    }
    else /* stack.top.phase == down */ {
        pop;
    }
}

If you make a few observations about your requirements you can optimise this drastically.

1. There will be exactly (r-1)+(c-1) steps (where r = rows and c = columns).
2. There will be exactly (c-1) steps to the right and (r-1) steps down.

You therefore can use numbers where a zero bit could (arbitrarily) indicate a down step while a 1 bit steps across. We can then merely iterate over all numbers of (r-1)+(c-1) bits containing just (c-1) bits set. There's a good algorithm for that at the Stanford BitTwiddling site Compute the lexicographically next bit permutation.

First a BitPatternIterator I have used before. You could pull out the code in hasNext if you wish.

/**
 * Iterates all bit patterns containing the specified number of bits.
 *
 * See "Compute the lexicographically next bit permutation" http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
 *
 * @author OldCurmudgeon
 */
public static class BitPattern implements Iterable<BigInteger> {

    // Useful stuff.
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = ONE.add(ONE);
    // How many bits to work with.
    private final int bits;
    // Value to stop at. 2^max_bits.
    private final BigInteger stop;

    // All patterns of that many bits up to the specified number of bits.
    public BitPattern(int bits, int max) {
        this.bits = bits;
        this.stop = TWO.pow(max);
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return new BitPatternIterator();
    }

    /*
     * From the link:
     *
     * Suppose we have a pattern of N bits set to 1 in an integer and
     * we want the next permutation of N 1 bits in a lexicographical sense.
     *
     * For example, if N is 3 and the bit pattern is 00010011, the next patterns would be
     * 00010101, 00010110, 00011001,
     * 00011010, 00011100, 00100011,
     * and so forth.
     *
     * The following is a fast way to compute the next permutation.
     */
    private class BitPatternIterator implements Iterator<BigInteger> {

        // Next to deliver - initially 2^n - 1 - i.e. first n bits set to 1.
        BigInteger next = TWO.pow(bits).subtract(ONE);
        // The last one we delivered.
        BigInteger last;

        @Override
        public boolean hasNext() {
            if (next == null) {
                // Next one!
                // t gets v's least significant 0 bits set to 1
                // unsigned int t = v | (v - 1);
                BigInteger t = last.or(last.subtract(BigInteger.ONE));
                // Silly optimisation.
                BigInteger notT = t.not();
                // Next set to 1 the most significant bit to change,
                // set to 0 the least significant ones, and add the necessary 1 bits.
                // w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
                // The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros.
                next = t.add(ONE).or(notT.and(notT.negate()).subtract(ONE).shiftRight(last.getLowestSetBit() + 1));
                if (next.compareTo(stop) >= 0) {
                    // Dont go there.
                    next = null;
                }
            }
            return next != null;
        }

        @Override
        public BigInteger next() {
            last = hasNext() ? next : null;
            next = null;
            return last;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported.");
        }

        @Override
        public String toString() {
            return next != null ? next.toString(2) : last != null ? last.toString(2) : "";
        }

    }

}

Using that to iterate your solution:

public void allRoutes(char[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    BitPattern p = new BitPattern(rows - 1, cols + rows - 2);
    for (BigInteger b : p) {
        //System.out.println(b.toString(2));
        /**
         * Walk all bits, taking a step right/down depending on it's set/clear.
         */
        int x = 0;
        int y = 0;
        StringBuilder s = new StringBuilder(rows + cols);
        for (int i = 0; i < rows + cols - 2; i++) {
            s.append(grid[y][x]);
            if (b.testBit(i)) {
                y += 1;
            } else {
                x += 1;
            }
        }
        s.append(grid[y][x]);
        // That's a solution.
        System.out.println("\t" + s);
    }
}

public void test() {
    char[][] grid = {{'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}};
    allRoutes(grid);
    char[][] grid2 = {{'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}};
    allRoutes(grid2);
}

printing

ADGHI
ADEHI
ABEHI
ADEFI
ABEFI
ABCFI
ADGJKL
ADGHKL
ADEHKL
ABEHKL
ADGHIL
ADEHIL
ABEHIL
ADEFIL
ABEFIL
ABCFIL

which - to my mind - looks right.