Получить максимальную матрицу перестановок из логической матрицы

Question

A (m строк, n столбцов) является (0,1) -Матрица (или логическая матрица).

Как получить вложенные матрицы B (р строк, р столбцов) из , удовлетворяющих что B является матрицей перестановок и р является максимальным? Например,

PS: а permutation matrix представляет собой квадратную матрицу двоичное, что имеет ровно одну запись 1 в каждой строке и в каждом столбце и 0s в другом месте.

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 продолжается.