Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como construir Quadrados Latinos Mutuamente Ortogonais de ordem 4

0 votos
27 visitas
perguntada Set 29 em Programação Computacional por Renata Oliveira (46 pontos)  

Exercício 11, pg. 36 do livro ``The Art of Computer Programming, vol. 4A: Combinatorial Algorithms'' de Donald E. Knuth.

Estenda o quadrado greco-latino

A imagem será apresentada aqui.

com letras hebraicas de modo que nenhum par de letras (latina, grega), (latina, hebraica), (grega, hebraica) aparece mais de uma vez no quadrado.

Compartilhe

1 Resposta

0 votos
respondida Set 29 por Renata Oliveira (46 pontos)  
editado Set 29 por Renata Oliveira

Um quadrado latino de ordem \(n\) é uma matriz quadrada \(n\times n\) tal que cada coluna e cada linha contém exatamente uma vez cada algarismo \(k=1,...,n\).
Um exemplo clássico de quadrado latino utiliza as cartas de um baralho.
Tomando quatro cartas de cada naipe (Paus, Ouros, Copas e Espadas) e arranjando-as em uma matriz \(4\times4\) de modo que cada naipe aparece exatamente uma vez em cada linha e uma vez em cada coluna, obtemos:

A imagem será apresentada aqui.

Podemos construir outro quadrado latino tomando quatro cartas de cada valor: Ás, Rei, Dama e Valete. Uma possibilidade é:

A imagem será apresentada aqui.

Dois quadrados latinos de ordem \(n\) são chamados de ortogonais se a sobreposição dos dois quadrados resulta em uma matriz de ordem \(n\) cujas entradas são os pares ordenados formados pelas entradas de cada quadrado e tal que cada par ordenado aparece exatamente uma vez na matriz.

No exemplo das cartas, é possível dispor as 16 cartas em uma matriz \(4\times4\) de modo que cada linha e cada coluna contém todos os quatro valores e todos os quatro naipes:

A imagem será apresentada aqui.

Os naipes e valores no exemplo anterior podem ser substituídos por quaisquer valores, simbolos ou letras. O termo "quadrado latino" foi inspirado no trabalho de Leonhard Euler, que usou caracteres latinos em seus estudos sobre o tema. Dois quadrados latinos ortogonais recebem o nome de quadrado "greco-latino" devido ao uso dos caracteres do alfabeto latino em um dos quadrados e do alfabeto grego no outro.

O exercício proposto no livro parte de um quadrado greco-latino formado pelos quadrados

A imagem será apresentada aqui.

Este quadrado greco-latino deve ser estendido de modo a incorporar um terceiro quadrado latino formado com caracteres do alfabeto hebraico. Este terceiro quadrado deve ser mutuamente ortogonal a ambos os quadrados já definidos. Isto significa que nenhum par de caracteres (latino, grego), (latino, hebraico) ou (grego-hebraico) aparece mais de uma vez quando os quadrados são sobrepostos dois a dois.

Já foi provado que no caso de quadrados \(4\times4\) existem apenas 3 quadrados que atendem à condição de ortogonalidade mútua. Logo, existe apenas uma possível disposição dos caracteres hebraicos em uma matriz que satisfaz à condição.

O código abaixo constrói quadrados latinos mutuamente ortogonais (Mutually Orthogonal Latin Squares - MOLS) de números, mas estes números podem ser posteriormente substituídos pelos caracteres gregos, latinos e hebraicos.

O primeiro passo para encontrar os MOLS é encontrar o primeiro quadrado latino. A função que gera este quadrado (latin_sq) começa com uma matriz \(4\times4\) de zeros. A ideia é pegar cada algarismo k=1,2,3,4 e testar cada posição da matriz que satisfaça às duas condições: não repetir o número na linha nem na coluna. Estas condições são testadas pelas funções "linhaOK" e "colunaOK", reunidas na função "position _ check" que verifica se ambas são satisfeitas (não basta apenas uma condição ser satisfeita). Se a posição é legal, ou seja, se satisfaz às condições e se a posição está disponível (se o valor que está na posição é zero), então podemos colocar o algarismo nesta posição. Caso contrário, testamos a próxima posição. O loop termina quando cada algarismo aparece exatamente uma vez em cada linha e cada coluna. Formamos assim o QUADRADO1.

O segundo passo é construir um segundo quadrado latino ortogonal ao QUADRADO 1. Para isso, precisamos verificar uma terceira condição: as coordenadas formadas pela sobreposição dos quadrados não podem se repetir. A função "coordinate_check" verifica se uma coordenada já aparece em uma lista de coordenadas que será construída à medida que as posições do segundo quadrado forem preenchidas. A função "ortogonal" gera uma matriz ortogonal a outra matriz que deve ser dada como argumento (no caso o argumento será o QUADRADO 1). Da mesma forma que na construção do primeiro quadrado latino, começamos com uma matriz \(4\times4\) de zeros. Iniciamos também com uma lista vazia de coordenadas que já existem na matriz de coordenadas. Pegamos cada algarismo e testamos cada posição primeiro para a condição de não repetição na linha e na coluna e depois para a condição de não repetição da coordenada. Se a posição é legal e está disponível, colocamos o algarismo nesta posição. Verificamos então se a coordenada formada nesta posição já existe em algum lugar da matriz de coordenadas. Se não existe, a condição é satisfeita e adicionamos esta coordenada à lista de coordenadas que já foram formadas. Se a coordenada já existe, retiramos o algarismo colocado na posição e testamos a próxima posição. Este algoritmo forma o QUADRADO2.

O terceiro passo é construir uma terceira matriz (QUADRADO3) que seja ao mesmo tempo ortogonal ao QUADRADO 1 e ao QUADRADO 2. Isto é feito com a função "MOLS_generator". O processo é semelhante: primeiro testamos se a posição satisfaz às duas restrições de não repetição em linhas e colunas, colocando o algarismo na posição se a condição é satisfeita. Desta vez, contudo, testamos duas vezes a coordenada formada. Primeiro testamos se a coordenada se repete na matriz formada pela sobreposição dos quadrados 1 e 3 e depois testamos se a coordenada formada se repete quando se sobrepõem os quadrados 2 e 3. Somente se a coordenada não se repete em ambos os casos podemos manter o algarismo nesta posição. Caso contrário retiramos e testamos a próxima posição.

A função "print_orthogonal_matrix" revela os quadrados latinos mutuamente ortogonais, assim como a matriz que sobrepõe os três quadrados.

import numpy as np

class MOLS:
@staticmethod
def linhaOK(matriz, linha, algarismo):
    '''
    Verifica se o algarismo já aparece na linha da matriz. Se não aparece: ok
    '''
    for l in range(4):
        if matriz[linha][l]==algarismo:
            return False
    return True

@staticmethod
def colunaOK(matriz, coluna, algarismo):
    '''
    Verifica se o algarismo já aparece na coluna da matriz. Se não aparece: ok
    '''
    for c in range(4):
        if matriz[c][coluna]==algarismo:
            return False
    return True

def position_check(self, matriz, linha, coluna, algarismo): 
    '''
    Verifica ambas as condições (linha e coluna)
    '''
    if self.linhaOK(matriz, linha, algarismo)==True:
        if self.colunaOK(matriz, coluna, algarismo)==True:
            return True
        return False
    return False


def latin_sq(self):
    '''
    Gera um quadrado latino de ordem 4
    '''
    matriz=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]])
    for e in range(1,5): #cada algarismo de 1 a 4
        for lin in range(0,4): #para cada linha da matriz
            for col in range(0,4): #para cada coluna da matriz
                if self.position_check(matriz, lin, col, e) == True: #se a posição é "legal"
                    if matriz[lin][col]==0: # e se a posição está disponível
                        matriz[lin][col]=e #coloca o algarismo nesta posição
    return matriz

@staticmethod
def coordinate_check(conj_coord, coordinate):
    '''
    Verifica se a coordenada já existe

    conj_coord é uma lista de coordenadas que já estão na matriz de coordenadas
    '''
    if (coordinate in conj_coord):
        return False
    return True


def ortogonal(self, matrix):
    '''
    Constroi a matriz ortogonal a uma matriz dada
    '''
    matrix1=matrix #a matriz em relação à qual será construída a matriz ortogonal
    matrix2=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]) #inicializa a matriz ortogonal - vazia
    conj_coordinates=[] #lista de coordenadas que já existem. Começa vazia.
    for f in range (1,5): #para cada algarismo de 1 a 4
        for linha in range (0,4): #para cada linha
            for coluna in range(0,4): #para cada coluna
                if self.position_check(matrix2, linha, coluna, f) == True: #se a posição é "legal"
                    if matrix2[linha][coluna]==0: # e se a posição está disponível
                        matrix2[linha][coluna]=f # coloca o algarismo nesta posição
                        if self.coordinate_check(conj_coordinates, [matrix1[linha][coluna],matrix2[linha][coluna]]) == True:
                            # se a coordenada formada é "legal"
                            conj_coordinates.append([matrix1[linha][coluna],matrix2[linha][coluna]])
                            #adiciona à lista de coordenadas que já existem
                        else: 
                            matrix2[linha][coluna]=0 #se a coordenada é "ilegal", retira o algarismo colocado
    return matrix2


def MOLS_generator(self, matrix1, matrix2):
    '''
    Gera quadrados latinos mutuamente ortogonais (Mutually Orthogonal Latin Squares)
    '''
    matrix1=self.latin_sq() #gera o primeiro quadrado latino
    matrix2=self.ortogonal(matrix1) #gera o segundo quadrado latino, ortogonal ao primeiro
    matrix3=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]) #inicializa o terceiro quadrado latino - vazio

    conj_coordinates1=[] #lista de coordenadas que já existem quadrados 1 e 3
    conj_coordinates2=[] #lista de coordenadas que já existem quadrados 2 e 3
    for f in range (1,5): #para cada algarismo de 1 a 4
        for linha in range (0,4): #para cada linha
            for coluna in range(0,4): #para cada coluna
                if self.position_check(matrix3, linha, coluna, f) == True: #se a posição é "legal"
                    if matrix3[linha][coluna]==0: # e se a posição está disponível
                        matrix3[linha][coluna]=f # coloca o algarismo nesta posição
                        if (self.coordinate_check(conj_coordinates1, [matrix1[linha][coluna],matrix3[linha][coluna]]) == True) and ((self.coordinate_check(conj_coordinates2, [matrix2[linha][coluna],matrix3[linha][coluna]]) == True)):
                                # se a coordenada formada é "legal" 
                            conj_coordinates1.append([matrix1[linha][coluna],matrix3[linha][coluna]])
                            conj_coordinates2.append([matrix2[linha][coluna],matrix3[linha][coluna]])
                                #adiciona à lista de coordenadas que já existem
                        else: 
                            matrix3[linha][coluna]=0 #se a coordenada é "ilegal", retira o algarismo colocado
    return matrix3


def print_orthogonal_matrix(self):
    '''
    Gera a matriz ortogonal
    '''
    quadrado=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]])
    matrix1=self.latin_sq()
    print("Quadrado Latino #1:")
    print(matrix1)
    matrix2=self.ortogonal(matrix1)
    print("Quadrado Latino #2: ")
    print(matrix2)
    matrix3=self.MOLS_generator(matrix1, matrix2)
    print("Quadrado Latino #3: ")
    print(matrix3)

    orthogonal_matrix=[[[0,0,0],[0,0,0],[0,0,0],[0,0,0]], #inicia com uma matriz de zeros.
                      [[0,0,0],[0,0,0],[0,0,0],[0,0,0]], #cada entrada da matriz é uma lista com 3 valores
                      [[0,0,0],[0,0,0],[0,0,0],[0,0,0]], 
                      [[0,0,0],[0,0,0],[0,0,0],[0,0,0]]]
    for i in range(0,4):
        for j in range(0,4):
            orthogonal_matrix[i][j][0] = matrix1[i][j] # o primeiro valor vem da primeira matriz
            orthogonal_matrix[i][j][5] = matrix2[i][j] # o segundo valor vem da segunda matriz
            orthogonal_matrix[i][j][6] = matrix3[i][j] # o terceiro valor vem da terceira matriz
    print("Matriz de MOLS")
    print(orthogonal_matrix)

Usando esta classe:

if __name__ == '__main__':
    LatinSquares=MOLS()
    LatinSquares.print_orthogonal_matrix()

obtemos:

Quadrado Latino #1:
[[1 2 3 4]
 [2 1 4 3]
 [3 4 1 2]
 [4 3 2 1]]
Quadrado Latino #2: 
[[1 2 3 4]
 [3 4 1 2]
 [4 3 2 1]
 [2 1 4 3]]
Quadrado Latino #3: 
[[1 2 3 4]
 [4 3 2 1]
 [2 1 4 3]
 [3 4 1 2]]
Matriz de MOLS
[[[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]], 
 [[2, 3, 4], [1, 4, 3], [4, 1, 2], [3, 2, 1]], 
 [[3, 4, 2], [4, 3, 1], [1, 2, 4], [2, 1, 3]], 
 [[4, 2, 3], [3, 1, 4], [2, 4, 1], [1, 3, 2]]]

É possível notar que o Quadrado Latino #2 representa o quadrado com as letras gregas da questão, fazendo \(\gamma=1, \delta=2, \beta=3, \alpha=4\). O Quadrado Latino #3 é aquele com as letras latinas, fazendo \(d=1, a=2, b=3, c=4\). O Quadrado Latino 1, então, deve ser aquele que possui os caracteres hebraicos. Fazendo as devidas substituições, o resultado é o quadrado greco-latino-hebraico da figura abaixo.

A imagem será apresentada aqui.

...