All possible combinations of numbers of length 5 in a 4X4 matrix

i have a matrix

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

I need to find all possible combinations of numbers of length 5.

constraints:

1. Starting form a any position in the matrix you can only move to your next immediate neighbor i.e if u start form say (0,0) your neighbor must be (0,1),(1,1),(1,0) and if you pick a position then form that position you can only move to its immediate neighbor and so on.

2. The length of the number must be 5 digit's i.e for example if i start from (0,0) with value 1 i can produce a sequence 15151 or 19232 or 10063 so on you can move in any sequence with the constraint 1 applied.

3. The solution must produce the output in 7sec and python is preferred since its my favorite. ;)

OK i missed some things开发者_运维知识库 the program must use all 16 numbers i.e it must use all the 16 numbers as initial and produce the 5 digit sequence.

Here is a solution in Scala (for the 5x5 version with 9 digits, starting from the middle) (with an ideone.com demo). It took 5 seconds to execute on my (fairly slow) computer.

object Main {

    val matrix = List(List("1", "9", "2", "3", "1"),
                      List("5", "0", "0", "6", "1"),
                      List("8", "4", "4", "8", "1"),
                      List("8", "4", "4", "8", "1"),
                      List("2", "3", "7", "8", "1"))

    def main(args: Array[String]) : Unit = nums(2, 2, 9) map println

    def nums(r: Int, c: Int, left: Int) : List[String] =
        if (!(matrix isDefinedAt r) || !(matrix(r) isDefinedAt c)) List()
        else if (left == 0) List("")
        else for ((dr, dc) <- List((0,1), (1,0), (-1,0), (0,-1));
                  tail <- nums(r + dr, c + dc, left - 1))
                yield matrix(r)(c) + tail
}

Here is a solution in Java (with an ideone.com demo).

import java.util.*;

public class Test {

    static String[][] matrix = {{"1", "9", "2", "3"},
                                {"5", "0", "0", "6"},
                                {"8", "4", "4", "8"},
                                {"2", "3", "7", "8"}};

    public static void main(String[] args) {
        for (String i : nums(0, 0, 5))
            System.out.println(i);
    }

    public static List<String> nums(int r, int c, int left) {

        if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[r].length)
            return Collections.emptyList();

        if (left == 1)
            return java.util.Arrays.asList(matrix[r][c]);

        ArrayList<String> result = new ArrayList<String>();
        for (int[] delta : new int[][] {{0,1}, {1,0}, {-1,0}, {0,-1}})
            for (String tail : nums(r + delta[0], c + delta[1], left-1))
                result.add(matrix[r][c] + tail);

        return result;
    }
}

Execution took 8 ms on my computer.

If you want to speed it up, you should definitely cache the results. There are several ways of getting two steps down, and two steps to the right using 4 digits. All of which will share same possible tails (namely nums(row + 2, col + 2, x)).

First, you have to think about how to start at one position in the matrix and move to an adjacent one.

The brute force method is simply to list all available cells and all adjacent cells for each:

nextpos = {
    (0,0): [(1,0), (1,1), (0,1)],
    (0,1): [(0,0), (1,0), (1,1), (1,2), (0,2)],
    (0,2): [(0,1), (1,1), (1,2), (1,3), (0,3)],
    (0,3): [(0,2), (1,2), (1,3)],
    # etc
}
allpos = nextpos.keys()

For a problem this small, this is pretty simple; however, there is always a chance of typos. Another solution is to write a generator function:

def nextpos(p,w=4,h=4):
    """
    @param p     Current position tuple (x,y)
    @param w     Width of matrix
    @param h     Height of matrix

    Generate all matrix cells adjacent to the current one
    """
    rel = ((-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1))

    x,y = p
    for dx,dy in rel:
        nx,ny = x+dx, y+dy
        if 0<=nx<w and 0<=ny<h:
            yield (nx,ny)

Once we know which cells are next to each other, we can proceed to seek valid paths:

def matrix_path(pathLen, startFrom=None):
    """
    @param pathLen    Length of path to return
    @param startFrom  Initial location

    Generate all adjacency paths through the matrix
    """

    # bad path length - quit gracefully
    if pathLen<1:
        yield []
        return

    # no starting point specified - start at any point
    if startFrom is None:
        for pos in allpos:
            for res in matrix_path(pathLen, pos):
                yield res
        return

    # end of path
    if pathLen==1:
        yield [startFrom]
        return

    # from current point, recurse to find rest of path
    for pos in nextpos[startFrom]:
        for morePath in matrix_path(pathLen-1, pos):
            yield [startFrom]+morePath

We can find out how long this takes by profiling:

import cProfile

def test():
    sols = [i for i in matrix_path(5)]
    print len(sols), "paths found"

cProfile.run("test()")

which returns

16860 paths found 121497 function calls (16865 primitive calls) in 0.678 CPU seconds

This returns a list of lists of cell-positions; we want to turn this into the actual values from the matrix,

def path_vals(mx, path):
    """
    @param mx    Matrix data
    @param path  List of cell positions

    Return list of values from list of cell positions
    """

    return tuple([mx[x][y] for x,y in path])

Then

mx = [
    [1,9,2,3],
    [5,0,0,6],
    [8,4,4,8],
    [2,3,7,8]
]

def test():
    sols = [path_vals(mx, i) for i in matrix_path(5)]

We also want to reduce the list to unique results:

def test():
    usol = list(set([path_vals(mx, i) for i in matrix_path(5)]))
    print len(usol),"unique results"

cProfile.run("test()")

which gives us

8651 unique results 138357 function calls (33725 primitive calls) in 0.845 CPU seconds

Look at itertools combinatoric generators for inspiration:

• product()
• permutations()
• combinations()
• combinations_with_replacement()

You could write this rather easily with recursion and backtracking.

Have a recursive function along the lines of:

foo(x,y,depth)

and then recursively try moving each direction that is inbounds and valid. When the max depth (5) is reached, you have a number. Then it is just bookkeeping to build and combine lists.

Edit

A little more info..

foo( x, y, depth, seq )

where seq is a string of the sequence up to this point. It returns a list of strings which are the solutions.

Base case: the depth is 5, in which case just return a list with the current number concatenated onto seq.

Otherwise check the bound for each direction, and if it is valid, call foo with the proper coordinates, depth +1, and the current number concatenated onto seq. Combine all the resulting lists together and return that.

Invoke this function for each initial spot with a depth of one, a sequence of "", and then combine all 16 of these results together.

Note that because this is recursive it works fine for this problem size, but can get slow very quickly. Although because it is depth-limited I would not expect it to be as much of an issue.

1503 unique solutions

Edit 2

my search function is pretty similar to what you had, but look at what bounds are being checked and what values are returned etc..

def foo(x,y,depth,seq):
    if depth == 5: return [seq + str(matrix[x][y])]

    cur = []
    seq = seq + str(matrix[x][y])
    if (y - 1) >= 0: cur.extend(search(x,y-1,depth+1,seq))
    if (x + 1) < len(matrix[0]): cur.extend(search(x+1,y,depth+1,seq))
    if (y + 1) < len(matrix): cur.extend(search(x,y+1,depth+1,seq))
    if (x - 1) >= 0: cur.extend(search(x-1,y,depth+1,seq))

    return cur  

The way I check the four directions could be cleaned up and made more 'pythonic', but this was more just a proof of concept that you could solve the problem sufficiently fast.

Edit def foo(x,y,depth,seq):

def search(x,y,depth,seq):

if depth == 8: 

    return [seq + str(matrix[x][y])]

cur = []

seq = seq + str(matrix[x][y])

if (y - 1) >= 0: 

    cur.extend(search(x,y-1,depth+1,seq))

if (x + 1) < len(matrix[0]): 

    cur.extend(search(x+1,y,depth+1,seq))

if (y + 1) < len(matrix): 

    cur.extend(search(x,y+1,depth+1,seq))

if (x - 1) >= 0: 

    cur.extend(search(x-1,y,depth+1,seq))

if (x + 1) < len(matrix[0]) and (y + 1) < len(matrix): 

    cur.extend(search(x+1,y+1,depth+1,seq))

if (x - 1) >= 0 and (y - 1) >=0: 

    cur.extend(search(x-1,y-1,depth+1,seq))

if (x + 1) < len(matrix[0]) and (y - 1) >= 0: 

    cur.extend(search(x+1,y-1,depth+1,seq))

if (x - 1) >= 0 and (y + 1) < len(matrix): 

    cur.extend(search(x-1,y+1,depth+1,seq))

return cur

matrix = [[1,1,2,3,5],

    [2,3,4,5,5],

    [5,5,2,3,3],

    [9,9,5,4,2],

    [9,9,5,4,2],

    ]

if name == "main":

print search(0,0,0,"")

I ran this code it took 19~20 sec to stop. that too just for one initial location, also it produced a lot of duplicate results. I ran this on 2.2Ghz core 2 duo processor my old pc got hung and python.exe crashed :p.