Algorithm to check if a multidimensional array contains another?

user_15154691 0
Viewed 90

Say I have two multidimensional arrays of equal depth, say:

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

and

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

What sort of algorithm can I follow to determine if the latter is a contiguous subarray of the former?

For example, with the above example, it is:

enter image description here

And also with this pair of 3d arrays:

[ [ [4, 6],
    [5, 7] ],
  [ [2, 8],
    [9, 3] ] ]

[ [ [4, 6] ],
  [ [2, 8] ] ]

enter image description here

Another way of interpreting this is that by removing the first or last item from a dimension of the first array repeatedly, you will eventually get the target array.

multidimensional-array language-agnostic arrays algorithm
2 Answers

The Rabin-Karp string search algorithm can be extended to multiple dimensions to solve this problem.

Lets say your pattern array is M rows by N columns:

  1. Using any rolling hash function, like a polynomial hash, first replace every column of your pattern array with the hash of the column, reducing it to 1 dimension. Then hash the remaining row. This will be your pattern hash.

  2. Now use the rolling hash in your target array to replace all values in rows >= M by the hash of those values with the M-1 values above them.

  3. Then, similarly replace all remaining values in columns >= N-1 with the hash of those values and the N-1 values to the left.

  4. Finally, find any instances of the pattern hash in the resulting matrix. When you find one, compare with your pattern array to see if it's a real match.

This algorithm extends to as many dimensions as you like and, like simple Rabin-Karp, it takes O(N) expected time if the number of dimensions is constant.

user_54835260

The simple and naive approach would be, to look for first (0,0) match and then to compare the sub array.

Example: (Python)

hay=[ [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9] ]
needle=[ [2, 3],
         [5, 6] ]


def get_sub_array(array,i,j,width,height):
    sub_array=[]
    for n in range(i,i+height):
        sub_array.append(array[n][j:j+width])
    return sub_array

def compare(arr1,arr2):
    for i in range(len(arr1)):
        for j in range(len(arr1[0])):
            if arr1[i][j]!=arr2[i][j]:
                return False
    return True


def is_sub_array(hay,needle):
    hay_width=len(hay[0])
    hay_height=len(hay)
    needle_width=len(needle[0])
    needle_height=len(needle)

    for i in range(hay_height-needle_height+1):
        for j in range(hay_width-needle_width+1):
            if hay[i][j]==needle[0][0]:
                if compare(
                    get_sub_array(hay,i,j,needle_width,needle_height),
                    needle
                    ):
                    return True
    return False

print(is_sub_array(hay,needle))

Output:

True
user_136082280
Related