J'ai une liste python:

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

J'ai besoin de trouver tous les rectangles (combien de rectangles y a-t-il) dans ce tableau 2D qui répondent à ces critères:
1. Tous les nombres dans ce rectangle doivent être les mêmes
2. Le numéro de ce rectangle ne peut pas être ailleurs dans le tableau
3. Pas vraiment un critère mais quelques informations supplémentaires:
Les dimensions des rectangles peuvent être 1x1, 2x1, 2x2, 3x1, 3x2, 3x3, 3x4 et ainsi de suite.

Dans cet exemple, il y a 5 rectangles pour les nombres:

1, 2, 3, 4

Et les numéros 3, 1, 8 ne répondent pas aux critères car:

5 - Règle la règle numéro 2
7 - Règle la règle numéro 2

J'ai essayé des trucs comme trouver les éléments les plus proches qui les comparaient et s'ils correspondent, descendre d'une ligne et ainsi de suite, mais je ne pouvais pas le faire, alors j'espère que quelqu'un pourrait aider. Merci.

2
Some Guy 27 janv. 2019 à 07:38

3 réponses

Meilleure réponse

Une approche consiste pour chaque valeur unique à ajuster un rectangle sur toutes les instances de cette valeur. Si toutes les valeurs de ce rectangle correspondent, alors vous avez répondu à vos critères. Ici, il est implémenté dans du code utilisant numpy, en imprimant des valeurs qui correspondent aux critères:

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)

Mise à jour

Pas aussi joli mais ce quelque chose comme ça ne nécessiterait pas de 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)
3
busybear 27 janv. 2019 à 06:05

Une autre approche consiste à envisager l'utilisation d'une trame de données pandas.

import pandas as pd

Créez une trame de données à partir de votre liste de nombres comme suit:

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]
])

Ensuite, vous utilisez une boucle for pour tester chaque numéro 1-9 (je suppose que 0 ne figure pas dans votre liste?) Et dans la boucle for vous supprimez les lignes et les colonnes qui n'ont aucun des nombres testés. Si la trame résultante est en effet un rectangle, alors il ne devrait pas y avoir de «NaN».

Par exemple, la trame résultante du chiffre 1 ressemble à:

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

Alors que la trame résultante du chiffre 2 ressemble à:

     1   2
0   2.0 2.0
1   2.0 2.0
2   2.0 2.0

Vérifiez que NaN est == 0 et vous aurez un rectangle. Vous devez également vous assurer que la taille du champ n'est pas nulle, car cela indiquerait un nombre non présent. Voici le code:

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)

Et votre résultat ressemble à ceci:

The numbers that form rectangles are: [2, 4, 5, 7, 9]
0
run-out 27 janv. 2019 à 06:18

Suite au commentaire ci-dessus de user3386109, voici le code python pur qui calculera la taille du rectangle de la coordonnée supérieure gauche à la coordonnée inférieure droite et la comparera au nombre total de chiffres et verra s'ils sont égaux. S'ils le font, alors le chiffre est un rectangle.

# 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)

Le résultat ressemblera à ceci:

The digits that form rectangles are:  [2, 4, 5, 7, 9]
1
run-out 27 janv. 2019 à 07:23