有没有办法找出A是否是B的子矩阵？

Question

我给出引号,因为我的意思是例如:

B = [[1,2,3,4,5],
     [6,7,8,9,10],
     [11,12,13,14,15],
     [16,17,18,19,20]]

假设我们选择第2,4行和第1,3列,交叉点将给我们

A = [[6,8],
     [16,18]]

我的问题是假设我有A和B,有没有办法可以找出从B中选择哪些行和列来给A？

顺便说一句,如果你能用python/numpy给出答案,那将是最好的.但只是在数学或其他编程语言中也会很好.

Answer 1

这是一个非常困难的组合问题.事实上,子图同构问题可以简化为你的问题(如果矩阵A只有0-1个条目,你的问题恰好是子图同构问题).已知该问题是NP完全的.

这是一个递归回溯解决方案,它比强制执行所有可能的解决方案要好一些.请注意,在最坏的情况下,这仍然需要指数时间.但是,如果您假设存在解决方案且没有歧义(例如,所有条目B都不同),则会以线性时间查找解.

def locate_columns(a, b, offset=0):
    """Locate `a` as a sublist of `b`.

    Yields all possible lists of `len(a)` indices such that `a` can be read
    from `b` at those indices.
    """
    if not a:
        yield []
    else:
        positions = (offset + i for (i, e) in enumerate(b[offset:])
                     if e == a[0])
        for position in positions:
            for tail_cols in locate_columns(a[1:], b, position + 1):
                yield [position] + tail_cols


def locate_submatrix(a, b, offset=0, cols=None):
    """Locate `a` as a submatrix of `b`.

    Yields all possible pairs of (row_indices, column_indices) such that
    `a` is the projection of `b` on those indices.
    """
    if not a:
        yield [], cols
    else:
        for j, row in enumerate(b[offset:]):
            if cols:
                if all(e == f for e, f in zip(a[0], [row[c] for c in cols])):
                    for r, c in locate_submatrix(a[1:], b, offset + j + 1, cols):
                        yield [offset + j] + r, c
            else:
                for cols in locate_columns(a[0], row):
                    for r, c in locate_submatrix(a[1:], b, offset + j + 1, cols):
                        yield [offset + j] + r, c

B = [[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20]]
A = [[6,8], [16,18]]

for loc in locate_submatrix(A, B):
    print loc

这将输出:

([1, 3], [0, 2])