从逻辑矩阵获取最大置换矩阵 [英] Get the maximum permutation matrix from logical matrix

问题描述

A (m行，n列)是(0,1)-矩阵(或逻辑矩阵).

A (m rows, n columns) is a (0,1)-Matrix (or logical matrix).

如何从 A 获取子矩阵 B (p行，p列)，满足 B 是置换矩阵和p最大?例如，

How to get a sub matrix B (p rows, p columns) from A, satisfying that B is a permutation matrix and p is the maximum? For instance,

PS:一个置换矩阵是一个方形二进制矩阵，在其中恰好有一个条目1每行和每一列，其他位置为0.

PS: A permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere.

推荐答案

一种可能性是利用每个排列矩阵一次可以建立一行和一列的可能性. 因此，我们可以采取一定规模的每个置换矩阵，尝试所有可能的行或列，以扩展它， 看看是什么导致排列矩阵大一倍.

One possibility is to exploit that every permutation matrix can be built up one row and column at a time. So we can take every permutation matrix of a certain size, try to extend it by all possible rows or columns, and see what results in a permutation matrix that is one size larger.

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

The running time isn't that great. I think it's something like O(2^(m+n)). (And I've used 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中，我们将执行以下操作:

In Python, a tuple is an immutable array of objects. Because it’s immutable, it can be hashed and made an element of a set. So maximalSubmatrices is a set of the rows and columns needed to make a submatrix. In Java, we’d do something like:

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

但是Python可以自己完成所有这些工作.

but Python can take care of all that by itself.

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

We start with the rows and columns needed to make a submatrix of size 0: both are the empty tuple (). Each time through the while loop, we take all possible row,column pairs and see if that row,column could extend a current permutation matrix (in other words, they’re not already in the matrix). If so, we add the extended matrix to the set moreMaxl. Then we go through moreMaxl and keep only the permutation matrices. If there’s still elements in moreMaxl, then they’re permutation matrices that are one size larger than the matrices in maximalSubmatrices. Since we could extend, the while loop continues.

这篇关于从逻辑矩阵获取最大置换矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！