क्या यह पता लगाने का कोई तरीका है कि ए बी का सबमिट्रिक्स है या नहीं?

Question

मैं उद्धरण चिह्न देना, क्योंकि जो मेरा मतलब है, उदाहरण के लिए है:

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

हम पंक्ति 2,4 और col 1,3 चयन लगता है, चौराहों हमें दे देंगे

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

मेरा प्रश्न लगता है मेरे पास ए और बी है, क्या कोई तरीका है कि मैं यह पता लगा सकता हूं कि बी से कौन सी पंक्तियां और कोल्स का चयन किया जाता है?

अगर आप पाइथन/numpy में जवाब दे सकते हैं तो यह सबसे अच्छा होगा। लेकिन सिर्फ गणित में या अन्य प्रोग्रामिंग भाषा में भी ठीक रहेगा।

Answer 1

यह एक बहुत ही कठिन संयोजन समस्या है। वास्तव में Subgraph Isomorphism Problem आपकी समस्या में कम किया जा सकता है (यदि मैट्रिक्स A में केवल 0-1 प्रविष्टियां हैं, तो आपकी समस्या बिल्कुल एक उप-आइसोमोर्फिज्म समस्या है)। यह समस्या एनपी-पूर्ण होने के लिए जाना जाता है।

यहां एक रिकर्सिव बैकट्रैकिंग समाधान है जो सभी संभावित समाधानों को ब्रूट करने के लिए थोड़ा बेहतर करता है। ध्यान दें कि यह अभी भी सबसे खराब मामले में घातीय समय लेता है। हालांकि, यदि आप मानते हैं कि कोई समाधान मौजूद है और अस्पष्टता (उदाहरण के लिए 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]) 

Answer 2

यहाँ एक जानवर बल समाधान करता है, तो बस इतना ही है, तो आप की जरूरत है:

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

यह करने के लिए B के हर पंक्ति के खिलाफ A के हर पंक्ति की जाँच कर रहा है सुनिश्चित करें कि submatrix के सभी तत्व मौजूद हैं। फिर, यह कॉलम के लिए एक ही बात करता है।

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

Answer 3

यदि सब आप जानना चाहते है जो पंक्तियों और कॉलम बी से चुने गए हैं एक देने के लिए और नहीं है:

आप केवल प्रासंगिक पंक्तियों को यह सीमित करके स्तंभ खोजने भाग में तेजी लाने सकता है यहां दक्षता की देखभाल एक क्रूर बल तरीका है जो परिणामों को एक सरणी में संग्रहीत करता है res res [N] बी में ए [एन] के सभी स्थानों को बताता है। भले ही ए [एन] बी

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 

के कई स्थानों में मौजूद है

आउटपुट:

[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

मैट्रिक्स अद्वितीय आईई में सभी/अधिकांश मान हैं: वे केवल मैट्रिक्स बी में दिखाई देते हैं?

सबग्राफ आइसोमोर्फिज्म (एसआई) पर बेहतर सुधार जितना बेहतर होगा उतना ही अद्वितीय होगा। यदि सभी मान अद्वितीय हैं, तो आप अपनी पंक्ति/कॉलम जोड़ी निर्धारित करने के लिए प्रत्येक मान पर एक रिवर्स लुक-अप कर सकते हैं, पंक्तियों और स्तंभों (अलग से) की सूची को संघबद्ध करते हैं।

परिणाम एक साधारण O(N) एल्गोरिदम है, जहां N = number of rows * number of columns है।बेशक, मूल्यों को कम अनूठा मानते हैं, आपको जितना अधिक झूठा सकारात्मक लगता है उसे जांचने की आवश्यकता होती है और आप एसआई के करीब पहुंच जाते हैं और कम सरल चीजें मिलती हैं।