C'è un modo per scoprire se A è una sottomatrice di B?

Question

Io do virgolette perché quello che voglio dire è, ad esempio:

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

supponiamo selezioniamo fila 2,4 e Col 1,3, le intersezioni ci darà

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

La mia domanda è supponiamo Ho A e B, c'è un modo per scoprire quali righe e colonne sono selezionate da B per dare A?

In ogni caso sarebbe meglio se tu potessi dare la risposta in python/numpy. Ma solo in matematica o in altri linguaggi di programmazione andrà bene.

Answer 1

Questo è un problema combinatorio molto difficile. Infatti lo Subgraph Isomorphism Problem può essere ridotto al tuo problema (nel caso in cui la matrice A abbia solo 0-1 voci, il tuo problema è esattamente un problema di isomorfismo del sottografo). Questo problema è noto per essere NP-completo.

Ecco una soluzione di backtracking ricorsivo che fa un po 'meglio di brute-forzando tutte le possibili soluzioni. Si noti che questo richiede ancora tempo esponenziale nel caso peggiore. Tuttavia, se si presuppone che esista una soluzione e che non vi siano ambiguità (ad esempio che tutte le voci in B siano distinte), questa trova la soluzione in tempo lineare.

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 

Questo stamperà:

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

Answer 2

Ecco una soluzione di forza bruta, se questo è tutto ciò che serve:

rows = [i for aa in A for i,bb in enumerate(B) if np.in1d(aa, bb).all()] 
cols = [i for aa in A.T for i,bb in enumerate(B.T) if np.in1d(aa, bb).all()] 

submatrix = B[np.ix_(rows, cols)] 

E 'controllando ogni fila di A contro ogni fila di B a assicurarsi che tutti gli elementi della sottomatrice siano presenti. Quindi, fa la stessa cosa per le colonne.

Si potrebbe velocizzare la parte di colonna conoscitiva limitando al solo le righe rilevanti:

cols = [i for aa in A.T for i,bb in enumerate(B[rows].T) if np.equal(aa, bb).all()] 

Answer 3

Se tutto quello che volete sapere è quali righe e colonne sono selezionati da B per dare A e non attenzione all'efficienza ecco un metodo di forza bruta che memorizza i risultati in un array res res [N] indica tutte le posizioni di A [N] in B. Funziona anche se A [N] esiste in più posizioni di B.

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]] 
res = [] 

for subsetIndex, subset in enumerate(A): 
    k = [] 
    res.append(k) 
    for supersetIndex, superset in enumerate(B): 
     loc = [] 
     try: 
      loc = [(supersetIndex, superset.index(item)) for item in subset] 
      k.append(loc) 
      print A[subsetIndex], "is at ", loc, "in B" 
     except ValueError: 
      pass 
print res 

output:

[6, 8] is at [(1, 0), (1, 2)] in B 
[16, 18] is at [(3, 0), (3, 2)] in B 
result = [[[(1, 0), (1, 2)]], [[(3, 0), (3, 2)]]] 

Answer 4

Sono tutti/la maggior parte dei valori nella matrice unica IE: Appaiono solo una volta nella matrice B?

Più i valori sono univoci, migliore è il miglioramento che si può ottenere rispetto all'isomorfismo del sottografo (SI). Se tutti i valori sono univoci, è sufficiente eseguire una ricerca inversa su ciascun valore per determinarne la coppia di righe/colonne, unione l'elenco di righe e colonne (separatamente).

Il risultato è un semplice algoritmo O(N), dove N = number of rows * number of columns.Naturalmente, meno i valori sono unici, più i falsi positivi si ottengono che è necessario controllare e più si avvicina a SI e meno le cose semplici ottengono.