有没有办法找出A是否是B的子矩阵? [英] Is there a way to find out if A is a submatrix of B?

问题描述

我用引号引起来是因为例如:

I give quotation mark because what I mean is for example:

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行，则相交会给我们

suppose we select row 2,4 and col 1,3, the intersections will give us

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

我的问题是假设我有A和B，有没有办法找出从B中选择哪些行和列给出A?

My question is suppose I have A and B, is there a way that I can find out which rows and cols are selected from B to give A?

如果可以用python/numpy给出答案，那将是最好的选择.但是，无论是数学还是其他编程语言，也都可以.

By the way it would be best if you can give the answer in python/numpy. But just in math or in other programming language will be fine as well.

推荐答案

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

This is a very hard combinatorial problem. In fact the Subgraph Isomorphism Problem can be reduced to your problem (in case the matrix A only has 0-1 entries, your problem is exactly a subgraph isomorphism problem). This problem is known to be NP-complete.

这是一个递归回溯解决方案，它比蛮力强行解决所有可能的解决方案要好一些.请注意，在最坏的情况下，这仍然需要花费指数时间.但是，如果您假设存在一个解决方案并且没有歧义(例如，B中的所有条目都是唯一的)，则可以在线性时间内找到解决方案.

Here is a recursive backtracking solution which does a bit better than brute-forcing all possible solutions. Note that this still takes exponential time in the worst case. However, if you assume that a solution exists and that there are no ambiguities (for example that all the entries in B are distinct), this finds the solution in linear time.

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])

这篇关于有没有办法找出A是否是B的子矩阵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！