ค้นหาว่าเมทริกซ์สมมาตรสองตัวเท่ากันหรือไม่โดยขึ้นอยู่กับการเรียงสับเปลี่ยนของแถว/คอลัมน์

นี่คือโซลูชันแบบเวกเตอร์ตาม sorting และการใช้ประโยชน์ searchsorted -

import pandas as pd

# Sort rows for a and b
aS = np.sort(a,axis=1)
bS = np.sort(b,axis=1)

# Scale down each row to a scalar each
scale = np.r_[(np.maximum(aS.max(0),bS.max(0))+1)[::-1].cumprod()[::-1][1:],1]
aS1D = aS.dot(scale)
bS1D = bS.dot(scale)

# Use searchsorted to get the correspondence on indexing
sidx = aS1D.argsort()
searchsorted_idx = np.searchsorted(aS1D,bS1D,sorter=sidx)
searchsorted_idx[searchsorted_idx==len(aS1D)] = len(aS1D)-1
df = pd.DataFrame({'A':searchsorted_idx})
new_order = sidx[df.groupby('A').cumcount().values+searchsorted_idx]
# new_order is the permuted order, i.e. [5, 7, 1, 3, 2, 4, 6]

# Finally index into a with the new_order and compare against b
out = np.array_equal(a[new_order[:,None], new_order],b)

ฉันจะถือว่าคุณมีรายการการเรียงสับเปลี่ยนของแถว/คอลัมน์ของ a ซึ่งให้ b เช่น บางอย่างเช่นนี้

p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1

จากนั้น คุณสามารถทำสิ่งต่อไปนี้บน a

a_p = a[p]
a_p = a_p[:, p]

และตรวจสอบว่า b และ a_p ที่ดัดแปรแล้วเท่ากันหรือไม่:

(a_p == b).all()

แก้ไข: เนื่องจากคุณไม่มีรายการเหมือนที่ด้านบน p คุณจึงสามารถ (อย่างน้อยสำหรับอาร์เรย์ขนาดเล็ก a และ b) สร้างการเรียงสับเปลี่ยนของดัชนีและตรวจสอบแต่ละรายการ:

from itertools import permutations

def a_p(a, b, p):
    p = np.array(p)
    a_p = a[p]
    a_p = a_p[:, p]
    return a_p

for p in permutations(range(a.shape[0])):
    if (a_p(a, b, p) == b).all():
        print('True')
        break
else:
    print('False')

โปรดทราบว่าวิธีเดรัจฉานบังคับนี้ใช้ได้กับเมทริกซ์ที่ไม่สมมาตรเช่นกัน แต่เนื่องจากจำนวนการเรียงสับเปลี่ยนมีมากสำหรับอาร์เรย์ขนาดใหญ่ a และ b วิธีนี้อาจช้ามาก ดังนั้นวิธีแก้ปัญหาของคุณด้วยค่าลักษณะเฉพาะในการคำนวณจึงดีกว่ามาก

นี่คือเกณฑ์มาตรฐาน:

def Yduqoli(a, b):
    ''' I suppose your solution is similar'''
    if (np.array(np.unique(a, return_counts=True)) == np.array(np.unique(b, return_counts=True))).all():
        a_eigs = np.sort(np.linalg.eigvals(a))
        b_eigs = np.sort(np.linalg.eigvals(b))
        return np.allclose(a_eigs, b_eigs)
    else:
        return False

def AndyK(a, b):
    for p in permutations(range(a.shape[0])):
        if (a_p(a, b, p) == b).all():
            return True
    return False  

%timeit AndyK(a,b)
103 ms ± 4.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit Yduqoli(a,b)
408 µs ± 65.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

โดยที่ฉันใช้เมทริกซ์สมมาตร a และ b ที่ได้รับจาก OP

อัปเดต: ตามที่ Paul Panzer กล่าวไว้ เพียงการตรวจสอบค่าลักษณะเฉพาะก็สามารถให้ผลลัพธ์ที่ไม่ถูกต้องได้ในบางกรณี เช่น a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) มีค่าลักษณะเฉพาะที่เหมือนกัน แต่ไม่สามารถสับเปลี่ยนค่าลักษณะเฉพาะเป็นค่าอื่นได้ ดังนั้นก่อนอื่นเราจำเป็นต้องตรวจสอบก่อนว่าอาร์เรย์ a และ b มีองค์ประกอบเดียวกันหรือไม่ (ไม่ว่าตำแหน่งจะเป็นอย่างไร)

คุณสามารถเรียงลำดับเมทริกซ์ตามบรรทัดฐานแถวและดูว่ามันต่างกันหรือไม่ หากสองแถวมีบรรทัดฐานเดียวกัน คุณจะต้องตรวจสอบการเรียงสับเปลี่ยนของแถวที่มีบรรทัดฐานเดียวกัน แต่สิ่งนี้จะช่วยลดปัญหาให้เหลือเฉพาะแถวที่มีบรรทัดฐานเดียวกันเท่านั้น ในหลายกรณี คุณสามารถเรียงลำดับตาม 2-บรรทัดฐาน จากนั้นจึงใช้ 1-บรรทัดฐาน และสุดท้ายก็ใช้การเรียงสับเปลี่ยนที่เหลือแบบเดรัจฉาน

import numpy as np

def get_row_norm(a):
    """
    Sort by 2-norm
    """
    row_norms = np.sum(a**2, axis=1)
    return row_norms

def sort(a):
    """
    Return the matrix a sorted by 2-norm
    """
    n = a.shape[0]
    # Get the norms
    row_norms = get_row_norm(a)
    # Get the order
    order = np.argsort(row_norms)[::-1]

    sorted_a = a.copy()

    for m in range(n):
        i = order[m]
        for k in range(m+1): 
            j = order[k]
            sorted_a[m, k] = a[i, j]
            sorted_a[k, m] = a[i, j]

    return sorted_a


a = np.array([
    #1 #2 #3 #4 #5 #6 #7
    [0, 1, 1, 0, 0, 0, 1], #1
    [1, 0, 1, 2, 1, 1, 2], #2
    [1, 1, 0, 0, 0, 0, 1], #3
    [0, 2, 0, 0, 4, 0, 4], #4
    [0, 1, 0, 4, 0, 1, 2], #5
    [0, 1, 0, 0, 1, 0, 0], #6
    [1, 2, 1, 4, 2, 0, 0]  #7
])  
b = np.array([
    #5 #7 #1,3#3,1#2 #4 #6 
    [0, 2, 0, 0, 1, 4, 1], #5
    [2, 0, 1, 1, 2, 4, 0], #7
    [0, 1, 0, 1, 1, 0, 0], #1,3 could be either
    [0, 1, 1, 0, 1, 0, 0], #1,3 could be either
    [1, 2, 1, 1, 0, 2, 1], #2
    [4, 4, 0, 0, 2, 0, 0], #4
    [1, 0, 0, 0, 1, 0, 0]  #6
])

# Sort a and b
A = sort(a)
B = sort(b)
# Print the norms
print(get_row_norm(a)) # [ 3. 12.  3. 36. 22.  2. 26.]
print(get_row_norm(A)) # [36. 26. 22. 12.  3.  3.  2.]
print(get_row_norm(B)) # [36. 26. 22. 12.  3.  3.  2.]
# Assert that they are equal
print( (A == B).all())

โปรดทราบว่าหากไม่เท่ากัน คุณยังต้องตรวจสอบการเรียงสับเปลี่ยนของแถวที่ห้าและหก เนื่องจากบรรทัดฐานเท่ากัน