Разбить неквадратную матрицу на квадратные подматрицы

Question

Учитывая любую неквадратную матрицу. Я ищу алгоритм, чтобы разбить его на N квадратных подматриц. Не нужно, чтобы все элементы исходной матрицы находились в новых подматрицах (на самом деле это не всегда возможно), но их должно быть как можно меньше. Также мне просто нужно одно решение, а не все возможные комбинации.

Например, если N=2 и матрица 2x4, одно деление может быть:

1 1 2 2
1 1 2 2

Если это будет 2x5, то:

1 1 2 2 -
1 1 2 2 -

Теперь последний столбец не назначен ни одной субматрице.

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

Есть идеи?

Answer 1

Я реализовал рекурсивный подход сверху вниз.

Учитывая матрицу (x,y,h,w)||(Top Left x-coord, Top Left y-coord, Height, Width), я сделал следующее: -

Предположим, матрица =

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

I выбранные квадраты всех возможных размеров из верхнего левого угла: -

Возможность 1:

1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Возможность 2:

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0

Возможность 3:

1 1 1 0 0
1 1 1 0 0
1 1 1 0 0

Затем я разделил оставшееся пространство на 2 прямоугольника и рекурсировал для одного и того же.

Для примера Возможность # 2 можно разбить двумя способами, x и y обозначают два новых рабочих пополам:

Путь 1:

1 1 y y y
1 1 y y y
x x y y y

Путь 2:

1 1 y y y
1 1 y y y
x x x x x

Вот реализация в Python:

import sys,copy
sys.setrecursionlimit(10**4)


def display_final_matrix(arr_matrix):
    temp =[['-' for i in range(init_matrix[3])] for j in range(init_matrix[2])]
    ctr=ord('a')
    for matrix in arr_matrix:
        for i in range(matrix[1],matrix[1]+matrix[2]):
            for j in range(matrix[0],matrix[0]+matrix[3]):
                temp[i][j]=chr(ctr)
        ctr+=1
    for i in temp:
        print(i)

def find_min_leftover(matrix,n):
    x = matrix[0]
    y = matrix[1]
    h = matrix[2]
    w = matrix[3]
    if  n==0:
        return h*w, []

    min_left=1<<64
    result_arr=[]
    for i in range(1,min(h,w)+1):
        current_selection = [x,y,i,i]

        # Possibility 1
        mtr1 = [x+i,y+0,h,w-i]
        mtr2 = [x+0,y+i,h-i,i]
        for j in range(n):
            left_mtr1 , mtr1_subselection = find_min_leftover(mtr1,j)
            left_mtr2 , mtr2_subselection = find_min_leftover(mtr2,n-1-j)
            if left_mtr1 + left_mtr2 < min_left:
                min_left = left_mtr1+left_mtr2
                result_arr =[current_selection]+mtr1_subselection+mtr2_subselection

        # Possibility 2

        mtr1 = [x+i,y+0,i,w-i]
        mtr2 = [x+0,y+i,h-i,w]
        for j in range(n):
            left_mtr1 , mtr1_subselection = find_min_leftover(mtr1,j)
            left_mtr2 , mtr2_subselection = find_min_leftover(mtr2,n-1-j)
            if left_mtr1 + left_mtr2 < min_left:
                min_left = left_mtr1+left_mtr2
                result_arr =[current_selection]+mtr1_subselection+mtr2_subselection

    return min_left,result_arr




# Top Left x-coord, Top Left y-coord, Height, Width
init_matrix = [0,0,6,6]

min_left,final_matrix = find_min_leftover(init_matrix,5)


print(min_left)
print(final_matrix)
display_final_matrix(final_matrix)

Выходные данные для заполнения матрицы 6x6 5 квадратами:

4
[[0, 0, 2, 2], [2, 0, 2, 2], [2, 2, 4, 4], [0, 2, 2, 2], [0, 4, 2, 2]]
['a', 'a', 'b', 'b', '-', '-']
['a', 'a', 'b', 'b', '-', '-']
['d', 'd', 'c', 'c', 'c', 'c']
['d', 'd', 'c', 'c', 'c', 'c']
['e', 'e', 'c', 'c', 'c', 'c']
['e', 'e', 'c', 'c', 'c', 'c']

Возможно запоминание, начиная с 0<=x,y,h,w<=Max Size.

Таблица 4D DP будет работать быстрее и может хранить все результаты сразу но я реализовал рекурсивный подход, поскольку он более интуитивен и его будет легче понять.

Answer 2

Нетрудно показать, что жадный алгоритм всегда будет покрывать столько, сколько может.

Так что просканируйте свою матрицу на предмет первого элемента, который еще не покрыт (например, слева направо сверху вниз -низу), и создайте новую квадратную подматрицу 1 × 1 здесь. Продолжайте расширять его по направлению к нижнему праву до подматрицы 2 × 2, 3 × 3 и т. Д. c, пока она вписывается в исходную матрицу. Застряв, начните с начала, пока не создадите N подматриц.