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

Это проблема минимального разреза с ограничением по размеру. Это NP-трудно решить точно.

Поскольку вы задали вопрос с точки зрения матриц, я рискну и предположу, что у вас есть свободный доступ к библиотеке, которая может вычислить частичное разложение по сингулярным значениям. Если да, то позвольте мне предложить дешевую спектральную эвристику.

Найдите сингулярный вектор m-элемента, соответствующий наибольшему сингулярному значению. Предполагая, что элементы этого вектора различны (без потери общности из-за возмущения или использования индексов для разрыва связей), выберите элемент порядка j; элементы с меньшими значениями соответствуют первым j-1 столбцам выходных данных, а элементы с большими значениями соответствуют последним m-j столбцам. При таком расположении столбцов каждая строка «голосует» за то, должна ли она находиться в верхней или нижней половине.

Вот решение «старой школы» для уточнения требований и сравнительного анализа. Если разрешены только операции «перестановка строк и замена столбцов», то матрицу можно разделить только с сортировкой по строкам и по столбцам. Строки сортируются по возрастанию соответствующих столбцов средневзвешенного значения. Столбцы отсортированы по возрастанию соответствующих строк средневзвешенного значения.

import numpy as np
rng = np.random.default_rng()           
N=7
M=15
nbmax=min(N,M)-4
A = rng.integers(0, 4, (N,M))

def getWACols(A,N,M):
    wacols=[]
    colsom=np.sum(A,axis=1)
    for row in range(N):
        wsum=0
        for col in range(M):
            wsum+=A[row,col]*col
        if colsom[row]!=0 :
            wacols.append(wsum/colsom[row])
        else:
            wacols.append((M-1)/2)
    return np.array(wacols)
            
def getWARows(A,N,M):
    warows=[]
    rowsom=np.sum(A,axis=0)
    for col in range(M):
        wsum=0
        for row in range(N):
            wsum+=A[row,col]*row
        if rowsom[col]!=0:
            warows.append(wsum/rowsom[col])
        else:
            warows.append((N-1)/2)
    return np.array(warows)

def sortByRow(A,N,M):
    B=np.zeros((N,M),np.int32)
    wacols_sorted=np.argsort(getWACols(A,N,M))
    bn=True
    for row in range(N):
        for col in range(M):
            B[row,col]=A[wacols_sorted[row],col]
            bn=bn and row==wacols_sorted[row]
    return B,bn

def sortByCol(A,N,M):
    B=np.zeros((N,M),np.int32)
    warows_sorted=np.argsort(getWARows(A,N,M))
    bn=True
    for col in range(M):
        for row in range(N):
            B[row,col]=A[row,warows_sorted[col]]
            bn=bn and col==warows_sorted[col]
    return B,bn    

def partitionMatrix(A,N,M):            
    B,bn=sortByRow(A,N,M)
    bn1=bn and True
    B,bn=sortByCol(B,N,M)
    return B,bn and bn1

print(A)
B=np.copy(A)
bn=False
cntr=0
while not bn and cntr<100:
    B,bn=partitionMatrix(B,N,M)
    cntr+=1
print(B)

j=np.sum(getWACols(B,N,M))/M
i=np.sum(getWARows(B,N,M))/N

print(i,j)
   

Два практических подхода:

1. Создайте задачу оптимизации, которая минимизирует сумму квадратов соответствующих коэффициентов в целевой матрице с учетом двух матриц перестановок: матрица C размеров mxm и матрица R размеров nxn. Добавьте требования RR^T=I и CC^T=I, используя множители Лагранжа. Запустите оптимизацию, чтобы найти оптимальные C и R. Затем добавьте к целевой функции регуляризатор, который преобразует эти матрицы в правильную перестановку (например, 0 и 1).
2. Используйте генетическую оптимизацию.

Ни один из них не гарантирует оптимального решения.