Поиск всех прямоугольников в списке Python

Question

У меня есть список питонов:

[
[1, 1, 2],
[1, 1, 2],
[7, 4, 5],
[5, 3, 7],
]

Мне нужно найти все прямоугольники (сколько существует прямоугольников) в этом двумерном массиве, которые соответствуют этим критериям:
1. Все числа в этом одном прямоугольнике должны быть одинаковыми
2. Число из этого прямоугольника не может быть больше нигде в массиве
3. Не совсем критерий, но дополнительная информация:
Размеры прямоугольников могут быть 1x1, 2x1, 2x2, 3x1, 3x2, 3x3, 3x4 и т. Д.

В этом примере для чисел есть 5 прямоугольников:

1, 2, 3, 4

и цифры 3, 1, 8 не соответствуют критериям, потому что:

5 - Правило № 2
7 - нарушает правило № 2

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

Answer 1

Другой подход заключается в рассмотрении использования фрейма данных pandas.

import pandas as pd

Создайте кадр данных из списка чисел следующим образом:

df = pd.DataFrame([
[3, 2, 2, 1, 4],
[3, 2, 2, 7, 4],
[8, 2, 2, 1, 3],
[8, 8, 9, 9, 9],
[8, 8, 1, 5, 1]
])

Затем вы используете цикл for для проверки каждого числа 1-9 (я предполагаю, что 0 нев вашем списке?) и в цикле for вы удаляете строки и столбцы, в которых нет проверяемого числа.Если результирующий кадр действительно является прямоугольником, то не должно быть никакого присутствия NaN.

Например, результирующий кадр цифры 1 выглядит следующим образом:

      2   3   4
0    NaN 1.0 NaN
2    NaN 1.0 NaN
4    1.0 NaN 1.0

В то время как результирующий кадр цифры 2 выглядит следующим образом:

     1   2
0   2.0 2.0
1   2.0 2.0
2   2.0 2.0

Проверка наличия NaN ==0 и у тебя будет прямоугольник.Вы также должны убедиться, что размер поля не равен нулю, так как это означает, что число отсутствует.Вот код:

result = []
for num in range(1, 10):
    df_dna = df[df == num].dropna(how="all", axis=0).dropna(how="all", axis=1)
    if df_dna.isnull().sum().sum() == 0 and df_dna.size != 0:
        result.append(num)
print("The numbers that form rectangles are:", result)

И ваш результат выглядит так:

The numbers that form rectangles are: [2, 4, 5, 7, 9]

Answer 2

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

# create an empty result array
result = []

# check each digit one through nine
for num in range(1, 10):
    # create a list to store the coordinates of each found digit
    coords = []
    # rows loop
    for r in range(len(li)):
        # columns loop
        for c in range(len(li[0])):
            if li[r][c] == num:
                coords.append([r,c])
    # check for null coords list which means the digit is not in the matrix
    if len(coords) == 0:
        pass
    else:
        tl = coords[0]
        br = coords[-1]
        total = (br[0] - tl[0] + 1) * (br[1] - tl[1] + 1)
        if total == len(coords):
            result.append(num)
print('The digits that form rectangles are: ', result)

Результат будет выглядеть так:

The digits that form rectangles are:  [2, 4, 5, 7, 9]

Answer 3

Один подход для каждого уникального значения, поместите прямоугольник на все экземпляры этого значения.Если все значения в этом прямоугольнике совпадают, значит, вы соответствуете вашим критериям.Здесь это реализовано в коде с использованием numpy, печатая значения, которые соответствуют критериям:

import numpy as np

arr = np.array([
    [3, 2, 2, 1, 4],
    [3, 2, 2, 7, 4],
    [8, 2, 2, 1, 3],
    [8, 8, 9, 9, 9],
    [8, 8, 1, 5, 1]
])
for n in np.unique(arr):
    y, x = np.where(arr == n)
    if (arr[y.min():y.max()+1, x.min():x.max()+1] == n).all():
        print(n)

---

Обновление

Не так красиво, но для чего-то подобного не потребуется numpy:

lst = [
    [3, 2, 2, 1, 4],
    [3, 2, 2, 7, 4],
    [8, 2, 2, 1, 3],
    [8, 8, 9, 9, 9],
    [8, 8, 1, 5, 1]
]

for val in set([x for sub in lst for x in sub ]):
    y = [n for n, sub in enumerate(lst) if val in sub]
    if any(y):
        x = []
        for sub in [lst[n] for n in y]:
            x.extend([m for m, v in enumerate(sub) if v == val])

        rect = [i for sub in lst[min(y):max(y)+1] for i in sub[min(x):max(x)+1]]
        if all([i == val for i in rect]):
            print(val)