如何跟踪两个矩阵之间发生的交换？

Question

我有两个矩阵，A 和 B。A 不是唯一矩阵。当你对A进行一些行交换和列交换时，你可以得到B。但是只给出了A和B，所以我想找到交换了哪些列和行。 但 A 和 B 并不总是相同，那么我必须找到最接近 B 的行/列交换矩阵。 A 和 B 的大小均为 N*N。 我找不到这个问题的子问题..

A       B         output
1 1 1   1 2 1     swap row 1 2
1 1 2   1 1 1     swap col 2 3
1 1 2   1 2 1  

我尝试计算矩阵的元素数量，例如）第一行有三个 1。第二行有两个 1 和一个 2。并将其与 B 进行比较，找到 A 行的正确位置。然后在A的列上重复这个操作，但是太花时间了。

Answer 1

据我了解，您正在尝试追踪 dp 解决方案的“有效”交换。

我会使用堆栈（通过引用传递）。在每次递归调用之前压入，当函数返回到该调用堆栈时检查有效性，如果无效则弹出。

def IsValid( num, s : list[int] ) -> bool:
    # s = [] if s is None else s
    
    # Do Some operation here to get the next step
    nextNum = someoperation( num )
    
    s.append( nextNum )
    
    x = IsValid( nextNum )
    
    if x is False:
        s.pop()
    
    return x

理想情况下，绘制一个递归树来指导这个过程。

对于 C，您可以仅使用一个辅助数组来保存封装数据的结构。