从逻辑矩阵中获取最大置换矩阵

Question

A（m行，n列）是一个（0,1）-矩阵（或逻辑矩阵）。

如何从A得到子矩阵B（p行，p列），满足B 是一个置换矩阵，p是最大值？例如，

PS：一个permutation matrix是一个二进制方阵，每一行和每一列只有一个元素1，其他地方只有一个元素0。

Answer 1

一种可能性是利用每个置换矩阵可以一次构建一行和一列。所以我们可以取每个特定大小的置换矩阵，尝试用所有可能的行或列扩展它，看看是什么导致了大一倍的置换矩阵。

运行时间不是很好。我认为它类似于 O(2^(m+n))。（我用过 Python，FWIW。）

#!/usr/local/bin/python3

import itertools

A = ((0,1,0,0),
     (0,0,1,0),
     (0,1,1,0),
     (1,0,0,1))
maximalSubmatrices = { ( (), () ), }
# each tuple is a tuple of rows and then columns
maxP = 0

def isPerm(rows,cols):
    if ( len(rows) != len(cols) ):
        return False
    for row in rows:
        if not exactlyOne( A[row][col] for col in cols ):
            return False
    for col in cols:
        if not exactlyOne( A[row][col] for row in rows ):
            return False
    return True

def exactlyOne(sequence):
    return sum( 1 for elt in sequence if elt ) == 1

while True:
    moreMaxl = set()
    for submatrix in maximalSubmatrices:
        for row,col in itertools.product(range(len(A)),range(len(A[0]))):
            if ( row not in submatrix[0] and col not in submatrix[1] ):
                moreMaxl.add( ( tuple(sorted(submatrix[0]+(row,))) , tuple(sorted(submatrix[1]+(col,))) ) )
    moreMaxl = set( ( maxl for maxl in moreMaxl if isPerm(*maxl) ) )
    if ( len(moreMaxl) ):
        maxP += 1
        maximalSubmatrices = moreMaxl
    else:
        break

for maxl in maximalSubmatrices:
    print("maximal rows: ",maxl[0],"\nmaximal cols: ",maxl[1],end="\n\n")
print("maximum permutation size is: ",maxP)

输出为：

maximal rows:  (0, 1, 3) 
maximal cols:  (0, 1, 2)

maximal rows:  (0, 1, 3) 
maximal cols:  (1, 2, 3)

maximum permutation size is:  3

解释：

在Python中，tuple是一个不可变的对象数组。因为它是不可变的，所以它可以被散列并成为集合的一个元素。所以 maximalSubmatrices 是构成子矩阵所需的一组行和列。在 Java 中，我们会做类似的事情：

class Submatrix {
    List<Integer> rows;
    List<Integer> columns;
    public int hashCode();
    public boolean equals(Object);
}
Set<Submatrix> maximalSubmatrices;

但是 Python 可以自己解决所有这些问题。

我们从创建大小为 0 的子矩阵所需的行和列开始：两者都是空元组 ()。每次通过 while 循环，我们都会获取所有可能的行、列对，看看该行、列是否可以扩展当前的置换矩阵（换句话说，它们不在矩阵中）。如果是这样，我们将扩展矩阵添加到集合 moreMaxl。然后我们遍历 moreMaxl 并只保留置换矩阵。如果 moreMaxl 中还有元素，则它们是比 maximalSubmatrices 中的矩阵大一维的置换矩阵。由于我们可以扩展，while 循环继续。

从逻辑矩阵中获取最大置换矩阵

Get the maximum permutation matrix from logical matrix

math

permutation

matrix

logical-operators