Existe-t-il un bon algorithme pour vérifier s'il y a 5 mêmes éléments dans une ligne ou une colonne ou en diagonale avec une matrice carrée, disons 6x6?

Il y a bien sûr l'algorithme naïf d'itération à travers chaque point puis pour chaque point de la matrice, itère à travers cette ligne, col puis la diagonale. Je me demande s'il y a une meilleure façon de le faire.

6
randomThought 11 nov. 2011 à 12:08

7 réponses

Meilleure réponse

Vous pouvez vérifier s'il y a k mêmes éléments dans une matrice d'entiers dans un passage unique .

Supposons que n est la taille de la matrice et m est le plus grand élément. Nous avons n colonne, n ligne et 1 diagonale. Pour chaque colonne, rangée ou diagonale, nous avons au plus n élément distinct.

Nous pouvons maintenant créer un histogramme contenant (n + n + 1) * (2 * m + 1) élément. Représentant les lignes, les colonnes et la diagonale contenant chacune au plus n élément distinct.

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

Maintenant, la partie délicate est de savoir comment mettre à jour cet histogramme?

Considérez cette fonction dans un pseudo-code:

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

Il ne vous reste plus qu'à parcourir l''histogramme et vérifier s'il y a un élément> k

1
Ghassen Hamrouni 11 nov. 2011 à 14:06

Pour les lignes, vous pouvez conserver un compteur, qui indique le nombre d'éléments identiques dans une ligne que vous avez actuellement. Pour ce faire, parcourez la ligne et

  • si l'élément actuel correspond à l'élément précédent, augmentez le compteur de un. Si le compteur est 5, alors vous avez trouvé les 5 éléments que vous vouliez.
  • si l'élément actuel ne correspond pas à l'élément précédent, définissez le compteur sur 1.

Le même principe peut également être appliqué aux colonnes et aux diagonales. Vous souhaiterez probablement utiliser un tableau de compteurs pour les colonnes (un élément pour chaque colonne) et les diagonales afin de pouvoir parcourir la matrice une fois.

J'ai fait le petit exemple pour un petit boîtier, mais vous pouvez facilement le changer:

n = 3
matrix = [[1, 2, 3, 4], 
          [1, 2, 3, 1], 
          [2, 3, 1, 3],
          [2, 1, 4, 2]]
col_counter = [1, 1, 1, 1]
for row in range(0, len(matrix)):
    row_counter = 1
    for col in range(0, len(matrix[row])):
        current_element = matrix[row][col]

        # check elements in a same row
        if col > 0:
            previous_element = matrix[row][col - 1]
            if current_element == previous_element:
                row_counter = row_counter + 1
                if row_counter == n:
                    print n, 'in a row at:', row, col - n + 1
            else:
                row_counter = 1

        # check elements in a same column
        if row > 0:
            previous_element = matrix[row - 1][col]
            if current_element == previous_element:
                col_counter[col] = col_counter[col] + 1;
                if col_counter[col] == n:
                    print n, 'in a column at:', row - n + 1, col
            else:
                col_counter[col] = 1

J'ai omis les diagonales pour garder l'exemple court et simple, mais pour les diagonales, vous pouvez utiliser le même principe que vous utilisez sur les colonnes. L'élément précédent serait l'un des suivants (selon la direction de la diagonale):

matrix[row - 1][col - 1]
matrix[row - 1][col + 1]

Notez que vous devrez faire un petit effort supplémentaire dans le deuxième cas. Par exemple, parcourez la ligne dans la boucle intérieure de droite à gauche.

0
Avo Muromägi 11 nov. 2011 à 09:16

Vous pouvez conserver un histogramme dans un dictionnaire (type d'élément de mappage -> int). Ensuite, vous parcourez votre ligne, votre colonne ou votre diagonale, et vous incrémentez histogram[element], et vérifiez à la fin si vous avez des 5 dans l'histogramme, ou si vous pouvez autoriser plus de 5 copies, vous pouvez simplement arrêtez une fois que vous avez atteint 5 pour n'importe quel élément.

Exemple simple et unidimensionnel:

m = ['A', 'A', 'A', 'A', 'B', 'A']

h = {}
for x in m:
    if x in h:
        h[x] += 1
    else:
        h[x] = 1

print "Histogram:", h

for k in h:
    if h[k]>=5:
        print "%s appears %d times." % (k,h[k])

Production:

Histogram: {'A': 5, 'B': 1}
A appears 5 times.

Essentiellement, h[x] stockera le nombre de fois que l'élément x apparaîtra dans le tableau (dans votre cas, ce sera la ligne ou la colonne ou la diagonale actuelle). Les éléments ne doivent pas apparaître consécutivement, mais les décomptes sont réinitialisés chaque fois que vous commencez à envisager une nouvelle ligne / colonne / diagonale.

3
Vlad 11 nov. 2011 à 17:30

Votre meilleure approche peut dépendre du contrôle de l'emplacement des éléments.

Par exemple, si vous construisez un jeu et que vous venez de placer l'élément le plus récent sur la grille, vous pouvez capturer en quatre chaînes les bandes verticales, horizontales et diagonales qui coupent ce point, et utiliser le même algorithme sur chaque bande, en comptant chacune élément et évaluer les totaux. L'algorithme peut être légèrement différent selon que vous comptez cinq éléments contigus sur les six, ou autorisez des écarts tant que le total est de cinq.

0
phatfingers 11 nov. 2011 à 08:29

Je ne pense pas que vous puissiez éviter l'itération, mais vous pouvez au moins faire un XOR de tous les éléments et si le résultat est 0 => ils sont tous égaux, alors vous n'avez pas besoin de faire de comparaisons.

0
dmn 11 nov. 2011 à 09:16

Vous pouvez essayer d'améliorer votre méthode avec quelques heuristiques: utilisez la connaissance de la taille de la matrice pour exclure les séquences d'éléments qui ne correspondent pas et suspendre les calculs inutiles. Dans le cas où la taille de vecteur donnée est 6, vous voulez trouver 5 éléments égaux et les 3 premiers éléments sont différents, un calcul supplémentaire n'a aucun sens.

Cette approche peut vous donner un avantage significatif, si 5 éléments égaux d'affilée se produisent rarement assez.

0
eugene_che 11 nov. 2011 à 19:06

Si vous codez les lignes / colonnes / diagonales en tant que bitmaps, "cinq dans une rangée" signifie "mask% 31 == 0 && mask / 31 == power_of_two"

  • 00011111: = 0x1f 31 (cinq d'affilée)
  • 00111110: = 0x3e 62 (cinq de suite)
  • 00111111: = 0x3f 63 (six de suite)

Si vous souhaitez également traiter le cas de six dans une rangée comme cinq dans une rangée, la façon la plus simple est probablement de:

for ( ; !(mask & 1) ; mask >>= 1 ) {;}
return (mask & 0x1f == 0x1f) ? 1 : 0;

Peut-être que le service de modification de bits de Stanford a une meilleure solution ou suggestion qui n'a pas besoin d'une boucle?

0
wildplasser 13 nov. 2011 à 15:17