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

Ache todas os pares de Langford em que n é <= 8

+2 votos
116 visitas
perguntada Dez 7, 2020 em Ciência da Computação por leonardocarvalho (21 pontos)  

A mais simples sequência de Langford não é apenas balanceada, ela é planar, no senso que seus pontos podem se conectar sem serem cortados. Ache todas os pares de Langford para os quais n <= 8. (Exercício 8, página 36, The Art of Computer Programming, volume 4A, Donald Knuth).

Compartilhe

1 Resposta

+1 voto
respondida Dez 18, 2020 por leonardocarvalho (21 pontos)  

Os pares de langford são números organizados em uma lista de forma que, um número k esteja a k+1 posições de sua cópia. Dado um número n qualquer, devemos encontrar os pares de langford da forma n, n-1, n-2 ... 1.
Um exemplo pode ser visto abaixo, para n = 4:

A imagem será apresentada aqui.

Ou seja, temos que para o 4, seu par estará localizado a 5 posições distante. Supondo que a posição i de 4 seja 0, então ele deverá estar na posição 5 novamente. Se 1 está na posição número 1, então seu par estará na posição 3, e assim por diante.
Para fazer isso, foi usado o algoritmo abaixo.

from itertools import permutations
import copy


from itertools import permutations
import copy


def langford(n):
    sequence = [i for i in range(1, n+1)]
    permutation = permutations(sequence)
    finalSeqTemp = []  # [0, 0, 0, 0 ... 0]
    langSequence = []
    occupiedTemp = set()
    for i in range(0, n*2):
        occupiedTemp.add(i)  # {0, 1, 2 ... n*2}
        finalSeqTemp.append(0)
    for perm in permutation:
        finalSeq = copy.copy(finalSeqTemp)
        occupied = copy.copy(occupiedTemp)
        broke, nextEmpty = False, 0
        for number in perm:
            try:
                if nextEmpty in occupied and nextEmpty+number+1 in occupied:
                    finalSeq[nextEmpty] = number
                    finalSeq[nextEmpty+number+1] = number
                    occupied.remove(nextEmpty)
                    occupied.remove(nextEmpty+number+1)
                    if len(occupied) > 0:
                        # O(1) por que só seleciona o proximo elemento de set
                        nextEmpty = next(iter(occupied))
                else:
                    broke = True
                    break
            except IndexError:
                broke = True
                break
        if broke == False:
            langSequence.append(finalSeq)
    return langSequence

Supondo um n = 3, a ideia do algoritmo é pegar todas as permutações de [1, 2, 3] e verificar se é possível criar pares de langford com cada uma dessas permutações. Exemplo:
Para [1, 2, 3], temos que o 1 deveria estar a k+n+1 (sendo k o índice onde 1 está localizado e n o valor desse número) posições dele, que, no caso seria a posição 2. Porém, na posição 2 dessa lista temos o 3, ou seja, é impossível criar um par de langford com 1. O algoritmo, então, tentará gerar o par com a próxima permutação, que é [1, 3, 2], que também é impossível. Dessa forma, ele irá rodar para todas as permutações de [1, 2, 3] para achar os pares de langford.

Primeiro é importado permutations de itertools para gerar todas as permutações de n que precisamos. A biblioteca copy também é usada para evitar cópia por referência que é padrão no Python.

Após isso é definida a função langford, que tem como argumento o n que desejamos criar os pares. Uma lista chamada sequence é criada, tendo os números de 1 até o n que desejamos criar os pares de langford. A variável langSequence guardará todos os pares de langford encontrados.

Criamos as permutações dessa sequência de [1, 2, ... , n] usando a biblioteca itertools.
Com finalSeqTemp é criado uma lista temporária de 0, que servirá como um backup do formato [0, 0, 0, ..., 0] em que desejamos criar os pares de langford.
A variável occupiedTemp é outro backup que irá ter as posições de cada número dentro da lista [0, 1, 2, ... n-1]. Ela será usada para registrar a próxima posição vazia de finalSeq. Ambas as listas tem tamanho n*2.

Após isso, iniciamos um loop dentro das permutações criadas. Copiamos finalSeq e occupied de acordo com seus backups. A variável broke serve para verificar se o algoritmo tenta acessar um índice não disponível em finalSeq. Por exemplo, supondo pares de langford para n = 3, temos que a lista teria tamanho 6. Caso seja colocado um 2 na posição 5, o algoritmo irá tentar acessar a posição 8 da lista, mas é impossível dele existir, já que o tamanho máximo é de 5. Dessa forma, broke é colocado com um valor de True e o algoritmo retorna para o ínicio do loop de permutações.

A variável nextEmpty verifica qual o próximo índice que está com valor de zero em finalSeq. Ela começa em 0 e vai até n*2-1.
É iniciado então o loop dos números dentro das permutações. Primeiro o algoritmo verifica se é possível acessar esse valor na lista por meio do chamado de try ... except. Caso não seja possível, o que é capturado por meio do IndexError, broke é colocado como True e volta para a próxima permutação. Se existir, o algoritmo verifica se o índice em nextEmpty e nextEmpty+number+1 estão disponíveis em occupied, caso falso, broke será True e o algoritmo irá voltar para a próxima permutação.

Caso contrário, ele irá colocar nesse índice de finalSeq o número em questão, assim como na posição k+n+1. Depois, removemos esses dois índices da lista occupied, para indicar que essas posições não estão mais disponíveis.

Depois disso, é verificado se o tamanho de occupied é maior que zero, caso seja, o próximo vazio será o próximo valor de occupied. Isso é feito utilizando a função next(iter(occupied)), que selecionará o próximo elemento em complexidade O(1).
O algoritmo continua rodando até que tenha achado o par de langford ou encontre algum erro no caminho. Por fim, ele retorna os pares.
Um exemplo com n = 3:

lang = langford(3)
print(lang)

O output será:

[[2, 3, 1, 2, 1, 3], [3, 1, 2, 1, 3, 2]]
comentou Dez 18, 2020 por Lucas Lourenço (91 pontos)  
Oi Leonardo, parabéns pela resposta. Achei o código muito eficiente e o texto explica com clareza cada etapa. Tenho somente duas observações:

Talvez você possa comentar que nem todos os inteiros n possuem sequências de Langford. Eu fui descobrir isso pois tentei gerar a lista para n = 5, o que retornou uma lista vazia. Note que "os emparelhamentos de Langford só existem quando n é congruente a 0 ou 3 módulo 4; por exemplo, não há pareamento de Langford quando n = 1, 2, ou 5."

Para brincar com isso, gerei o número de emparelhamentos para cada n de 1 a 10 (código abaixo). Aí que vem o meu segundo ponto: o seu código está gerando uma dada sequência e a sua inversa. No caso do n=3, [2, 3, 1, 2, 1, 3] é a sequência inversa de [3, 1, 2, 1, 3, 2]. Não sei se teríamos ganhos de eficiência se tentássemos contabilizar somente uma dessas sequências. Note que para achar n = 11, em que o número de emparelhamentos é igual a 17.792, o processo já fica um pouco lento. De qualquer forma, isso pode também ser pouco relevante, pois a quantidade de emparelhamentos cresce exponencialmente. Quando n=19, o número de emparelhamentos está na ordem de 2.6 trilhões! Então não devemos nos preocupar muito com esses valores altos de n. O mais importante do exercício, você executou perfeitamente. Obrigado pela solução.


lenghts = {}
for i in range (1,11):
    lang=langford(i)
    lenghts[i] = len(lang)/2
comentou Dez 18, 2020 por Lucas Lourenço (91 pontos)  
Pensando melhor aqui, acho que as sequências inversas fazem parte da solução. Apenas comentei isso pois a sequência A014552 da Enciclopédia de Sequências não está contabilizando as inversas. Anyway...

https://oeis.org/A014552
...