3

If I have the following multidimensional array (of an arbitrary size):

a,b,c

d,e,f

g,h,i

And I'd like to find all possible vertical traversals (adg, adh, aeh, aeg, aei, bdg, etc), how would I go about doing that in Java?

What's making this difficult for me is the fact that the array is of an arbitrary square size (you don't know if its a 2x2 or a 3x3 or 4x4), so you can't just make N nested for loops, where N = length of multidimensional array. Any help would be great!

Edit: I am defining vertical traversals as either moving down and to the left, directly down, and down and to the right

Anthony
  • 311
  • 1
  • 3
  • 13
  • [See here](https://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java) to get your thinking started. If you phrase your problem as just taking the cartesian cross product between sets, where each set is a row from the 2D array, then the problem becomes tractable. – Tim Biegeleisen Jul 31 '18 at 01:32
  • If you would provide the **input format**, I'd say that's helpful to help you out. What do you mean by **arbitrary size**? input **N** then the matrix? – Hearen Jul 31 '18 at 02:08
  • 1
    It seems like this problem is about two-dimensional arrays, not multi-dimensional arrays in general. – user152468 Jul 31 '18 at 02:20
  • How is vertical traversal defined? Why is "afi" not part of the sample list? – user152468 Jul 31 '18 at 02:23

1 Answers1

3

There are many ways to solve this problem but maybe you can go for a recursive depth-first search.

Try:

public static void main(String[] args) {
    int size = 3;

    String arr[][] = {
            {"a", "b", "c"},
            {"d", "e", "f"},
            {"g", "h", "i"}
    };

    for (int i = 0; i < size; i++) {
        dfs(arr, 0, i, size, arr[0][i]);
    }
}

static void dfs(String[][] arr, int y, int x, int size, String curr) {
    if (y == size - 1) {
        System.out.println(curr);
    } else {
        if (x > 0) {
            dfs(arr, y + 1, x - 1, size, curr + arr[y + 1][x - 1]);
        }
        dfs(arr, y + 1 , x, size, curr + arr[y + 1][x]);
        if (x < size - 1) {
            dfs(arr, y + 1, x + 1, size, curr + arr[y + 1][x + 1]);
        }
    }
}

dfs will move y and x to adjacent cells that is strictly below current cell, and save its contents to curr. If dfs traversed to bottom, it will print curr.

Output:

adg
adh
aeg
aeh
aei
bdg
bdh
beg
beh
bei
bfh
bfi
ceg
ceh
cei
cfh
cfi
shiftpsh
  • 1,926
  • 17
  • 24