Нахождение самой большой отрицательной подматрицы в python - PullRequest
Новая
       42

Нахождение самой большой отрицательной подматрицы в python

0 голосов
/ 11 ноября 2018

Я хочу найти самую большую подматрицу, которая содержит только отрицательные числа в матрице, например:

В 

[[1,  -9, -2,   8,  6,  1],    
 [8,  -1,-11,  -7,  6,  4],    
 [10, 12, -1,  -9, -12, 14],    
 [8, 10, -3,  -5,  17,  8],    
 [6,  4, 10, -13, -16, 19]]

самая большая подматрица, содержащая только отрицательные числа, равна 

[[-11, -7],
 [-1, -9],
 [-3,-5]]

(координаты левого верхнего угла: 1,2, координаты правого нижнего угла: 3,3).

Какой самый эффективный способ сделать это?

1 Ответ

0 голосов
/ 11 ноября 2018

Решение для грубой силы. Будет работать, но может считаться слишком медленным для большей матрицы: 

mOrig = [[1,  -9, -2,   8,  6,  1],
    [8,  -1,-11,  -7,  6,  4],
    [10, 12, -1,  -9, -12, 14],
    [8, 10, -3,  -5,  17,  8],
    [6,  4, 10, -13, -16, 19]]

# reduce the problem
# now we have a matrix that contains only 0 and 1
# at the place where there was a negative number
# there is now a 1 and at the places where a positive
# number had been there is now a 0. 0s are considered
# to be negative numbers, if you want to change this,
# change the x < 0 to x <= 0.
m = [[1 if x < 0 else 0 for x in z] for z in mOrig]

# now we have the problem to find the biggest submatrix
# consisting only 1s.

# first a function that checks if a submatrix only contains 1s
def containsOnly1s(m, x1, y1, x2, y2):
    for i in range(x1, x2):
        for j in range(y1, y2):
            if m[i][j] == 0:
                return False
    return True

def calculateSize(x1, y1, x2, y2):
    return (x2 - x1) * (y2 - y1)

best = (-1, -1, -1, -1, -1)
for x1 in range(len(m)):
    for y1 in range(len(m[0])):
        for x2 in range(x1, len(m)):
            for y2 in range(y1, len(m[0])):
                if containsOnly1s(m, x1, y1, x2, y2):
                    sizeOfSolution = calculateSize(x1, y1, x2, y2)
                    if best[4] < sizeOfSolution:
                        best = (x1, y1, x2, y2, sizeOfSolution)

for x in range(best[0], best[2]):
    print("\t".join([str(mOrig[x][y]) for y in range(best[1], best[3])]))

Будет выводить 

-11 -7
-1  -9
-3  -5

В случае, если что-то еще подразумевается под «самой большой подматрицей», единственная функция, которую необходимо изменить, это следующее: 

def calculateSize(x1, y1, x2, y2):
    return (x2 - x1) * (y2 - y1)

, который вычисляет размер подматрицы.

Редактировать 1 ... первое ускорение 

best = (-1, -1, -1, -1, -1)
for x1 in range(len(m)):
    for y1 in range(len(m[0])):
        if m[x1][y1] == 1: # The starting point must contain a 1
            for x2 in range(x1 + 1, len(m)): # actually can start with x1 + 1 here
                for y2 in range(y1 + 1, len(m[0])):
                    if containsOnly1s(m, x1, y1, x2, y2):
                        sizeOfSolution = calculateSize(x1, y1, x2, y2)
                        if best[4] < sizeOfSolution:
                            best = (x1, y1, x2, y2, sizeOfSolution)
                    else:
                        # There is at least one 0 in the matrix, so every greater
                        # matrix will also contain this 0
                        break

Редактировать 2

Хорошо, после преобразования матрицы в матрицу из 0 и 1 (как я делаю через строку m = [[1 if x < 0 else 0 for x in z] for z in mOrig], проблема та же, что в литературе называется the maximal rectangle problem. Поэтому я немного погуглил об известных алгоритмах для проблема такого рода и встречалась здесь на этом сайте http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529, который описывает очень быстрый алгоритм для решения этой проблемы. Чтобы суммировать точки этого сайта, алгоритм использует структуру. Это может быть сделано с помощью использование стека для запоминания профиля структуры, который позволяет нам пересчитать ширину в случае повторного использования узкого прямоугольника при закрытии более широкого прямоугольника.

...