查找 Python 列表中的所有矩形

Question

我有一个 python 列表：

[
[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

一种方法是针对每个唯一值，在该值的所有实例上放置一个矩形。如果该矩形内的所有值都匹配，那么您就满足了您的标准。这里使用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)

Answer 2

另一种方法是考虑使用 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 3

根据 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]

查找 Python 列表中的所有矩形

Finding all rectangles in Python list

python

arrays

algorithm

2d

list