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

Como arranjos de pares de Langford dispostos em círculo se distinguem dos arranjos dispostos em linha?

0 votos
22 visitas
perguntada Jun 30 em Ciência da Computação por Carlos A T Haraguchi (16 pontos)  

Referente ao exercício 3 da página 36 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms - Donald E. Knuth.

Compartilhe

1 Resposta

0 votos
respondida Jun 30 por Carlos A T Haraguchi (16 pontos)  
editado 6 dias atrás por Carlos A T Haraguchi

Me parece claro que a diferença entre dispor uma sequência Langford em linha ou em círculo é que i) numa solução em linha, necessariamente haverá \(k\) elementos entre as duas ocorrências do algarismo \(k\) e ii) num círculo, uma solução implica que haverá também \(2n-k-2\) elementos entre as mesmas ocorrências a depender do ponto inicial - trata-se do "complemento" por conta da circularidade.

A figura abaixo representa uma solução para \(n=4\). Perceba que os algarismos \(2\), se olharmos no sentido horário a partir daquele que está no ponto mais alto, estão separados por outros 2 algarismos. Porém, por ser circular, se olharmos no mesmo sentido horário a partir do outro algarismo \(2\), eles estão separados por 4 outros algarismos.

A imagem será apresentada aqui.

O "complemento" é \(2n-k-2\) porque é o que sobra de \(2n\) números na sequência menos \(k\), do requisito, e o próprio par.

Imagine o círculo como um colar de miçangas. Se rompermos o colar em um ponto qualquer e o esticarmos, teremos uma solução em linha em que os algarismos \(k\) não terão necessariamente \(k\) algarismos entre eles. Alguns terão \(k\) elementos e, possivelmente, outros terão \(2n-k-2\) elementos. Logo, uma estratégia para criar uma sequência Langford é seguir o mesmo procedimento de geração de sequências em linha, porém com possibilidade de também haver \(2n-k-2\) elementos entre os algarismos.

Uma dúvida que surge é: será que toda sequência em círculo pode ser "rompida" de forma a gerar uma sequência Langford em linha? Se sim, toda solução em círculo poderia ser gerada a partir de uma solução em linha. Nesse caso, não haveria de fato uma distinção significativa entre os arranjos em linha e os arranjos em círculo.

Para verificar se há alguma possibilidade de uma solução em círculo "rompida" em qualquer ponto não ser uma solução em linha, criei um gerador de sequências Langford em círculo.

A solução parte das soluções para as sequências em linha:
Quantos Trios de Langford existem para o conjunto {1,2,3,...9}?
Como fazer arranjos de pares de Langford para n, de modo que obtenhamos arranjos para n+1 com uma simples modificação?
Para quais n's posso rearranjar {0, 0, 1, 1, ..., n-1, n-1} como pares de Langford?

A ideia dessas soluções é usar força bruta e backtracking, armazenando todas as soluções encontradas. Em vez de se construir todos os arranjos possíveis e depois filtrar aqueles que atendam às restrições, cada arranjo é construído obedecendo às restrições e, ao chegar a um "beco sem saída", retornar ao ponto imediatamente anterior e buscar um novo caminho ainda não explorado. Assim, a quantidade de processamento é reduzido substancialmente.

Essencialmente, a busca de soluções em círculo não é diferente. A diferença é que o algoritmo é executado para cada diferente critério, ou seja, mais de uma vez. A quantidade de algarismos entre o par \(k\) pode ser \(k\) ou \(2n-k-2\). Logo, há \(2^n\) critérios diferentes e por isso é necessário rodar \(2^n\) vezes o algoritmo.
Além disso, uma solução em linha "rompida" em pontos diferentes representam diferentes sequências em linha, ou seja, estas diferentes sequências em linha correspondem a uma única solução em círculo.

O gerador de sequências foi desenvolvido em Python. Segue o código.

class Langford():
    # Construtor da classe
    def __init__(self, n):
        self.n = n
    # Método privado: busca uma sequência Langford
    def __sequence(self, k, seq, slots):
        pos = len(seq) - slots[k-1] - 1
        for slot1 in range(0, pos):
            slot2 = slot1 + slots[k-1] + 1
            if not (seq[slot1] or seq[slot2]):
                seq[slot1] = seq[slot2] = k
                if not(k==1):
                    yield from self.__sequence(k-1, seq, slots)
                else:
                    yield seq[:]
                seq[slot1] = seq[slot2] = 0
    # Método privado: elimina sequências Langford duplicadas
    def __unique(self, list2filter):
        # Elimina listas duplicadas
        listfiltered = list()
        for l in list2filter:
            if (l not in listfiltered): listfiltered.append(l)
        # Elimina listas circulares duplicadas
        listfiltered2 = list()
        strfiltered = ''
        for l in listfiltered:
            if '-'.join(map(str,l)) not in strfiltered:
                listfiltered2.append(l)
                strfiltered += '+' + '-'.join(map(str,2*l))
        # Elimina listas invertidas
        listfiltered = list()
        for l in listfiltered2:
            if l[::-1] not in listfiltered: listfiltered.append(l)
        return listfiltered
    # Método: gera todas sequências Langford em LINHA possíveis para n pares 
    def line(self):
        arranges = list(self.__sequence(self.n,[0]*2*self.n,range(1,self.n+1)))
        return arranges[0:int(len(arranges)/2)]
    # Método: gera todas sequências Langford em CÍRCULO possíveis para n pares 
    def circle(self):
        arranges=list()
        slots_comb = list(bin(i)[2:].zfill(self.n) for i in range(2**self.n))
        for comb in slots_comb:
            c=list(map(int,list(comb)))
            slots=list((i+1)*(1-c[i]) + (self.n*2-i-3)*c[i] for i in range(self.n))
            arranges += list(self.__sequence(self.n,[0]*2*self.n,slots))
        return self.__unique(arranges)

Foi criada a classe Langford que gera tanto sequências em linha como em círculo. O core da geração é a função privada __sequence que tem os parâmetros \(k\), a sequência seq a ser utilizada e os números de posições slots entre cada par de algarismos. Essa função é praticamente copiada dos exemplos já citados, exceto pela inclusão do parâmetro slots, importante para permitir sequências com critérios diferentes aos utilizados na solução em linha.

A função circle implementa o loop pelos diversos critérios. Cada par deve ter a distância de \(k\) ou de \(2n-k-2\) algarismos, o que representa duas possibilidades. Portanto, para n algarismos serão \(2^n\) possibilidades. Veja que usei a notação binária para auxiliar na construção do critério. Assim, cada possível critério pode ser calculado por: \(k\overline{b}+(2n-k-2)b\), onde \(b\) é um vetor de um binário e \(\overline{b}\) é o vetor do inverso do mesmo binário. Como exemplo, para \(n=4\), o binário \(0101\) geraria um critério
\[ k\left[\begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \end{array} \right] + (6-k)\left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 1 \end{array}\right] = \left[\begin{array}{c} k \\ 6-k \\ k \\ 6-k \end{array}\right] \]
que significa distância \(k\) para os algarismos \(1\) e \(3\), e \(6-k\) para os algarismos \(2\) e \(4\).

A função privada __unique cuida do filtro necessário para eliminar sequências repetidas, sequências invertidas e aquelas que em linha representam a mesma solução em círculo. O algoritmo que utilizei da solução em linha gera uma lista simétrica. Como uma sequência inversa é, do ponto de vista de uma sequência Langford, igual à sequência não invertida, a eliminamos. A função line simplesmente elimina a metade final dos resultados obtidos no algoritmo. No caso das soluções em círculo, em razão do loop por todos os critérios, foi preciso um filtro mais trabalhoso. Primeiro, são eliminadas as sequências duplicadas em linha, ou seja, sequências com mesma ordem. Em seguida, são eliminadas sequências duplicadas em círculo, ou seja, em que as sequências em linha representam a mesma sequência em círculo. Para isso, a estratégia foi verificar se a sequência analisada poderia estar contida, obedecendo a ordem, em uma das demais sequências duplicadas. Por exemplo, na figura já mostrada de uma solução para \(n=4\), podemos retirar as sequências \(42131423\) e \(23421314\). Essas sequências são, em linha, diferentes e, por também não serem inversas, nenhuma delas seria eliminada. Mas, se duplicarmos a segunda sequência para \([23\overline{421314][23}421314]\), podemos verificar que a primeira sequência está contida nela e, desse modo, a eliminamos. Por fim, eliminamos as sequências inversas (deixei esse passo por último, pois as inversas ajudam a eliminar as sequências duplicadas em círculo).

As linhas seguintes geram as sequências Langford, em linha e em círculo.

# Cria uma instância Langford para n pares e gera sequências em linha e em círculo
n = 7
langford = Langford(n)
list_line = langford.line()
list_circle = langford.circle()

Os resultados, para \(n=3\) e \(n=4\), foram que também existe apenas uma solução em círculo, formada obviamente pela solução em linha. Já para \(n=7\), verificamos \(49\) soluções em círculo, contra \(26\) soluções em linha. Um exemplo de solução em círculo que não é em linha está na figura abaixo. Veja que se "rompermos" o círculo em qualquer ponto, a sequência em linha não será uma sequência Langford.

A imagem será apresentada aqui.

Observações finais.
1. Esta solução não está elegante e certamente pode ser otimizada. Gerar arranjos duplicados no sentido da sequência Langford (sequência invertida igual à sequência não-invertida) consome recursos computacionais desnecessariamente. Além disso, talvez o atalho em Como fazer arranjos de pares de Langford para n, de modo que obtenhamos arranjos para n+1 com uma simples modificação? também possa ser utilizado quando n for par.
2. Como não era o foco da solução, não me dediquei na geração das figuras dos círculos em Python. Gerei no Word somente para auxiliar esta explicação toda.

comentou 5 dias atrás por Daniel Castro (46 pontos)  
Tanto o problema quanto a solução são muito interessantes, especialmente a utilização do paradigma orientado a objetos para resolvê-lo.

Como evolução, sugiro adotar as convenções de codificação de um guia de estilo como o PEP 8 (https://www.python.org/dev/peps/pep-0008/#naming-conventions) para melhorar a manutenibilidade e o entendimento.

Sugiro também utilizar o teste condicional if __name__ == "__main__": para evitar que a chamada principal seja executada caso o código seja utilizado como um módulo.

Sugiro também avaliar a substituição das iterações em listas por "list comprehensions" (https://python-3-patterns-idioms-test.readthedocs.io/en/latest/Comprehensions.html). A leitura do código pode não ficar tão fácil como em um loop for, mas o desempenho em geral é bastante superior.

Por fim, para desenho dos círculos, se for de interesse, sugiro utilizar o módulo turtle, simples mas completo o suficiente para desenhá-los.
comentou 5 dias atrás por Carlos A T Haraguchi (16 pontos)  
Muito obrigado pelos comentários, Daniel! Suas sugestões são ótimas. Eu realmente estou precisando de seguir um guia de estilo e aprender a usar "comprehensions". Quanto ao turtle, pensei em usar, mas fiquei na dúvida em como integrar com caracteres e acabei desistindo...
...