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

Sequência de Langford (Langford Sequence)

+1 voto
43 visitas
perguntada Dez 2, 2020 em Matemática por Luiz Filippe (21 pontos)  

A mais simples sequência de Langford não é apenas bem balanceada; ela é planar, no sentido de que os pares podem ser conectados sem que as linhas se cruzem, como mostrado abaixo:

A imagem será apresentada aqui.

Encontre a sequência planar de Langford na qual \(n \leq 8\):

REFERÊNCIA DA QUESTÃO: KNUTH, Donald. E. "The Art of Computer Programming". 1 ed. Editora: Addison-Wesley Professional. Boston, 2014. v. 4A. (Questão 8, página 36)

Compartilhe

1 Resposta

0 votos
respondida Dez 2, 2020 por Luiz Filippe (21 pontos)  
editado Dez 16, 2020 por Luiz Filippe

"Langford pairing" ou sequência de Langford é uma permutação da sequência de 2n números (1,1,2,2,...,n) na qual os dois valores 1 estão 1 unidade distantes um do outro, os dois valores 2 estão 2 unidades distantes um do outro e, de forma mais geral, os dois valores k estão k unidades de distância um do outro. A imagem a seguir ilustra a dita sequência.

A imagem será apresentada aqui.

Para que haja uma sequência de Langford, é necessário que a lista de valores tenha tamanho "n" múltiplo de 4 ou seja 1 valor abaixo de um múltiplo de 4 (ex.: 7,11,15 etc.) Também é importante atentar que, caso tal sequência tenha "n" distintos valores, seu tamanho deverá ser 2n, pois cada termo se repetirá 2 vezes. Caso definamos a posição de um número dentro da sequência como sendo ak, seu "gêmeo" aparecerá na posição bk. Perceba que bk = ak + k + 1. Caso somemos as posições:

\[ \Sigma a_k + \Sigma b_k = 1+2+3+...+2n \]
Uma outra forma de descrever esta sequência aritmética é:

\[ 2\Sigma a_k + \frac{n(n+1)}{2}+n = n(2n+1) \]

Simplificando, temos:

\[ \Sigma a_k = \frac{(3n^2-n)}{4} \]

Sabemos que o lado esquerdo da equação deve ser um valor inteiro, o que só é permitido se o lado direito também for um inteiro. Quando isto ocorre? Somente se \(3n^2 - n\) for divisível por \(4\) e isto se dá somente se \(n%4 = 0\) ou \(n%4 = -1\); i.e., o resto da divisão de \(n\) por \(4\) deve ser \(0\) ou \(-1\).

Dado o que foi apresentado acima, não é possível criar uma sequência de Langford para todos os valores de \(n\). Por definição, \(n=1\) não gera uma sequência de Langford porque não há um termo gêmeo. Caso \(n=2\), não é possível criar a sequência porque não há gap entre os termos. Para \(n=3\) e \(n=4\), a solução é única. Não há soluções para \(n=5\) ou \(n=6\).

Implementação em Python:

from itertools import permutations

def posicao(k):
        tamanho_langford = 2 * len(k)
'''
 Quando multiplicamos uma lista [] não vazia por um inteiro L, esta lista passa a ter um 
 tamanho da lista original vezes L. O código abaixo fará com que a lista [0] passe a contar 
 com tantos elementos 0 quanto for o valor de "tamanho_langford". Isto é necessário 
  para definirmos nossa sequência.
'''
         sequencia = [0] * tamanho_langford 

         for u in k:                          
    '''
    "enumerate" retorna (posição na lista, objeto da lista). Caso o objeto da lista seja 0, o 
      próximo slot vazio que será ocupado por seu gêmeo é o imediatamente ao lado. Não 
      há gap. Caso contrário, o próximo slot a ser ocupado pelo gêmeo será obtido da 
      forma descrita no texto acima.
    '''
                for i, v in enumerate(sequencia):
                       if v == 0:
                             break 
                else:
                        return  
                 j = i + u + 1

                if j >= tamanho_langford or sequencia[j]:
                     return 
                sequencia[i] = sequencia[j] = u # A posição do gêmeo não pode ultrapassar o 
                                                                             tamanho da sequência 

       return tuple(sequencia)

 def langford(n):
         count = 0
         for t in permutations(range(1, n+1)):
                sequencia = posicao(t)
    '''
    2 sequências de Langford são consideradas a mesma se uma for o inverso da outra. 
    Assim, para não contarmos 2 vezes a mesma sequência, dividimos a contagem por 2.
    '''
                # Caso a sequência seja válida segundo Langford e considerando inversa
                if sequencia and sequencia < sequencia[::-1]: 

                      count += 1
                      print(sequencia, count)
        return count

Vejamos, agora, a sequência de Langford para os valores \(n \leq 8\). Podemos confirmar a teoria contida no texto acima.

 # n=0 (sem solução)
langford(0)

# n=1 (sem solução)
langford(1)

0

# n=2 (sem solução)
langford(2)

 0

# n=3 (1 solução)
langford(3)

(2, 3, 1, 2, 1, 3) 1
1

# n=4 (1 solução)
langford(4)

(2, 3, 4, 2, 1, 3, 1, 4) 1
1

# n=5 (sem solução)
langford(5)

0    

# n=6 (sem solução)
langford(6)

0

# n=7
langford(7)
(1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7) 1
(1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5) 2
(1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7) 3
(1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7) 4
(1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3) 5
(1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6) 6
(1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7) 7
(1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3) 8
(1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4) 9
(1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5) 10
(2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5) 11
(2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4) 12
(2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5) 13
(2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7) 14
(2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7) 15
(2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5) 16
(2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3) 17
(2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6) 18
(3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5) 19
(3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4) 20
(3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5) 21
(4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5) 22
(4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5) 23
(4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5) 24
(5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7) 25
(5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7) 26
26

# n=8
langford(8)
(1, 3, 1, 6, 7, 3, 8, 5, 2, 4, 6, 2, 7, 5, 4, 8) 1
(1, 3, 1, 6, 8, 3, 4, 7, 5, 2, 6, 4, 2, 8, 5, 7) 2
(1, 3, 1, 6, 8, 3, 5, 7, 2, 4, 6, 2, 5, 8, 4, 7) 3
(1, 3, 1, 6, 8, 3, 7, 4, 2, 5, 6, 2, 4, 8, 7, 5) 4
(1, 3, 1, 7, 5, 3, 8, 6, 4, 2, 5, 7, 2, 4, 6, 8) 5
(1, 3, 1, 7, 8, 3, 5, 2, 6, 4, 2, 7, 5, 8, 4, 6) 6
(1, 3, 1, 8, 5, 3, 6, 7, 2, 4, 5, 2, 8, 6, 4, 7) 7
(1, 3, 1, 8, 6, 3, 7, 2, 4, 5, 2, 6, 8, 4, 7, 5) 8
(1, 4, 1, 5, 6, 8, 4, 7, 3, 5, 2, 6, 3, 2, 8, 7) 9
(1, 4, 1, 5, 7, 8, 4, 3, 6, 5, 2, 3, 7, 2, 8, 6) 10
(1, 4, 1, 5, 8, 6, 4, 7, 2, 5, 3, 2, 6, 8, 3, 7) 11
(1, 4, 1, 8, 6, 3, 4, 7, 5, 3, 2, 6, 8, 2, 5, 7) 12
(1, 5, 1, 4, 6, 7, 8, 5, 4, 2, 3, 6, 2, 7, 3, 8) 13
(1, 5, 1, 6, 4, 7, 8, 5, 3, 4, 6, 2, 3, 7, 2, 8) 14
(1, 5, 1, 6, 7, 3, 8, 5, 4, 3, 6, 2, 7, 4, 2, 8) 15
(1, 5, 1, 6, 7, 8, 2, 5, 4, 2, 6, 3, 7, 4, 8, 3) 16
(1, 5, 1, 7, 3, 6, 8, 5, 3, 4, 2, 7, 6, 2, 4, 8) 17
(1, 5, 1, 7, 3, 8, 6, 5, 3, 2, 4, 7, 2, 6, 8, 4) 18
(1, 5, 1, 8, 4, 7, 3, 5, 6, 4, 3, 2, 8, 7, 2, 6) 19
(1, 5, 1, 8, 6, 2, 7, 5, 2, 3, 4, 6, 8, 3, 7, 4) 20
(1, 6, 1, 3, 7, 5, 8, 3, 6, 4, 2, 5, 7, 2, 4, 8) 21
(1, 6, 1, 3, 7, 8, 4, 3, 6, 5, 2, 4, 7, 2, 8, 5) 22
(1, 6, 1, 3, 8, 5, 7, 3, 6, 2, 4, 5, 2, 8, 7, 4) 23
(1, 6, 1, 5, 8, 4, 7, 3, 6, 5, 4, 3, 2, 8, 7, 2) 24
(1, 6, 1, 7, 2, 8, 5, 2, 6, 3, 4, 7, 5, 3, 8, 4) 25
(1, 6, 1, 7, 4, 8, 3, 5, 6, 4, 3, 7, 2, 5, 8, 2) 26
(1, 6, 1, 8, 2, 5, 7, 2, 6, 3, 4, 5, 8, 3, 7, 4) 27
(1, 6, 1, 8, 2, 7, 4, 2, 6, 5, 3, 4, 8, 7, 3, 5) 28
(1, 7, 1, 2, 6, 8, 2, 5, 3, 7, 4, 6, 3, 5, 8, 4) 29
(1, 7, 1, 2, 8, 5, 2, 4, 6, 7, 3, 5, 4, 8, 3, 6) 30
(1, 7, 1, 2, 8, 5, 2, 6, 3, 7, 4, 5, 3, 8, 6, 4) 31
(1, 7, 1, 2, 8, 6, 2, 3, 5, 7, 4, 3, 6, 8, 5, 4) 32
(1, 7, 1, 3, 5, 6, 8, 3, 4, 7, 5, 2, 6, 4, 2, 8) 33
(1, 7, 1, 3, 8, 4, 5, 3, 6, 7, 4, 2, 5, 8, 2, 6) 34
(1, 7, 1, 4, 5, 8, 6, 3, 4, 7, 5, 3, 2, 6, 8, 2) 35
(1, 7, 1, 4, 6, 8, 3, 5, 4, 7, 3, 6, 2, 5, 8, 2) 36
(1, 7, 1, 4, 8, 5, 3, 6, 4, 7, 3, 5, 2, 8, 6, 2) 37
(1, 7, 1, 6, 2, 8, 5, 2, 4, 7, 6, 3, 5, 4, 8, 3) 38
(1, 7, 1, 6, 3, 8, 4, 5, 3, 7, 6, 4, 2, 5, 8, 2) 39
(1, 7, 1, 8, 2, 4, 6, 2, 5, 7, 4, 3, 8, 6, 5, 3) 40
(1, 8, 1, 3, 4, 7, 5, 3, 6, 4, 8, 2, 5, 7, 2, 6) 41
(1, 8, 1, 4, 6, 3, 7, 5, 4, 3, 8, 6, 2, 5, 7, 2) 42
(1, 8, 1, 5, 2, 6, 7, 2, 4, 5, 8, 3, 6, 4, 7, 3) 43
(1, 8, 1, 5, 3, 7, 4, 6, 3, 5, 8, 4, 2, 7, 6, 2) 44
(2, 3, 6, 2, 8, 3, 4, 7, 5, 6, 1, 4, 1, 8, 5, 7) 45
(2, 3, 8, 2, 4, 3, 6, 7, 5, 4, 1, 8, 1, 6, 5, 7) 46
(2, 3, 8, 2, 4, 3, 7, 5, 6, 4, 1, 8, 1, 5, 7, 6) 47
(2, 3, 8, 2, 7, 3, 6, 1, 5, 1, 4, 8, 7, 6, 5, 4) 48
(2, 4, 5, 2, 6, 8, 4, 7, 5, 3, 1, 6, 1, 3, 8, 7) 49
(2, 4, 5, 2, 8, 6, 4, 7, 5, 1, 3, 1, 6, 8, 3, 7) 50
(2, 4, 6, 2, 5, 8, 4, 7, 3, 6, 5, 1, 3, 1, 8, 7) 51
(2, 4, 6, 2, 7, 8, 4, 5, 1, 6, 1, 3, 7, 5, 8, 3) 52
(2, 4, 7, 2, 8, 6, 4, 1, 5, 1, 7, 3, 6, 8, 5, 3) 53
(2, 4, 8, 2, 3, 7, 4, 6, 3, 5, 1, 8, 1, 7, 6, 5) 54
(2, 5, 7, 2, 3, 6, 8, 5, 3, 4, 7, 1, 6, 1, 4, 8) 55
(2, 5, 7, 2, 6, 3, 8, 5, 4, 3, 7, 6, 1, 4, 1, 8) 56
(2, 5, 7, 2, 8, 3, 4, 5, 6, 3, 7, 4, 1, 8, 1, 6) 57
(2, 5, 7, 2, 8, 6, 1, 5, 1, 4, 7, 3, 6, 8, 4, 3) 58
(2, 5, 8, 2, 4, 7, 3, 5, 6, 4, 3, 8, 1, 7, 1, 6) 59
(2, 6, 3, 2, 7, 8, 3, 5, 6, 1, 4, 1, 7, 5, 8, 4) 60
(2, 6, 3, 2, 8, 5, 3, 7, 6, 4, 1, 5, 1, 8, 4, 7) 61
(2, 6, 4, 2, 7, 8, 3, 4, 6, 5, 3, 1, 7, 1, 8, 5) 62
(2, 6, 7, 2, 8, 1, 5, 1, 6, 4, 7, 3, 5, 8, 4, 3) 63
(2, 6, 8, 2, 1, 7, 1, 4, 6, 5, 3, 8, 4, 7, 3, 5) 64
(2, 7, 3, 2, 5, 8, 3, 4, 6, 7, 5, 1, 4, 1, 8, 6) 65
(2, 7, 4, 2, 8, 5, 3, 4, 6, 7, 3, 5, 1, 8, 1, 6) 66
(2, 8, 1, 2, 1, 5, 6, 7, 3, 4, 8, 5, 3, 6, 4, 7) 67
(2, 8, 1, 2, 1, 5, 7, 4, 6, 3, 8, 5, 4, 3, 7, 6) 68
(2, 8, 1, 2, 1, 6, 4, 7, 5, 3, 8, 4, 6, 3, 5, 7) 69
(2, 8, 1, 2, 1, 6, 7, 3, 4, 5, 8, 3, 6, 4, 7, 5) 70
(2, 8, 1, 2, 1, 7, 4, 6, 3, 5, 8, 4, 3, 7, 6, 5) 71
(2, 8, 1, 2, 1, 7, 5, 3, 6, 4, 8, 3, 5, 7, 4, 6) 72
(2, 8, 3, 2, 4, 6, 3, 7, 5, 4, 8, 1, 6, 1, 5, 7) 73
(2, 8, 4, 2, 3, 6, 7, 4, 3, 5, 8, 1, 6, 1, 7, 5) 74
(2, 8, 5, 2, 7, 1, 6, 1, 5, 4, 8, 3, 7, 6, 4, 3) 75
(2, 8, 6, 2, 1, 7, 1, 4, 5, 6, 8, 3, 4, 7, 5, 3) 76
(3, 1, 7, 1, 3, 5, 8, 6, 4, 2, 7, 5, 2, 4, 6, 8) 77
(3, 1, 7, 1, 3, 6, 8, 5, 2, 4, 7, 2, 6, 5, 4, 8) 78
(3, 1, 7, 1, 3, 8, 4, 5, 6, 2, 7, 4, 2, 5, 8, 6) 79
(3, 1, 7, 1, 3, 8, 6, 4, 2, 5, 7, 2, 4, 6, 8, 5) 80
(3, 1, 8, 1, 3, 4, 6, 7, 5, 2, 4, 8, 2, 6, 5, 7) 81
(3, 1, 8, 1, 3, 4, 7, 5, 6, 2, 4, 8, 2, 5, 7, 6) 82
(3, 1, 8, 1, 3, 6, 7, 2, 4, 5, 2, 8, 6, 4, 7, 5) 83
(3, 1, 8, 1, 3, 7, 5, 2, 6, 4, 2, 8, 5, 7, 4, 6) 84
(3, 4, 5, 6, 3, 8, 4, 7, 5, 2, 6, 1, 2, 1, 8, 7) 85
(3, 4, 7, 8, 3, 2, 4, 6, 2, 5, 7, 1, 8, 1, 6, 5) 86
(3, 4, 8, 5, 3, 7, 4, 2, 6, 5, 2, 8, 1, 7, 1, 6) 87
(3, 5, 6, 4, 3, 7, 8, 5, 4, 6, 1, 2, 1, 7, 2, 8) 88
(3, 5, 6, 8, 3, 2, 7, 5, 2, 6, 4, 1, 8, 1, 7, 4) 89
(3, 5, 6, 8, 3, 7, 1, 5, 1, 6, 4, 2, 8, 7, 2, 4) 90
(3, 5, 8, 2, 3, 7, 2, 5, 6, 4, 1, 8, 1, 7, 4, 6) 91
(3, 6, 2, 7, 3, 2, 8, 5, 6, 4, 1, 7, 1, 5, 4, 8) 92
(3, 6, 2, 8, 3, 2, 7, 5, 6, 1, 4, 1, 8, 5, 7, 4) 93
(3, 6, 4, 5, 3, 7, 8, 4, 6, 5, 1, 2, 1, 7, 2, 8) 94
(3, 6, 7, 2, 3, 8, 2, 4, 6, 5, 7, 1, 4, 1, 8, 5) 95
(3, 6, 8, 1, 3, 1, 5, 7, 6, 4, 2, 8, 5, 2, 4, 7) 96
(3, 6, 8, 1, 3, 1, 7, 4, 6, 5, 2, 8, 4, 2, 7, 5) 97
(3, 6, 8, 1, 3, 1, 7, 5, 6, 2, 4, 8, 2, 5, 7, 4) 98
(3, 7, 2, 6, 3, 2, 8, 4, 5, 7, 6, 1, 4, 1, 5, 8) 99
(3, 7, 5, 8, 3, 1, 6, 1, 5, 7, 4, 2, 8, 6, 2, 4) 100
(3, 7, 8, 2, 3, 4, 2, 5, 6, 7, 4, 8, 1, 5, 1, 6) 101
(3, 8, 2, 5, 3, 2, 7, 4, 6, 5, 8, 1, 4, 1, 7, 6) 102
(3, 8, 4, 7, 3, 2, 6, 4, 2, 5, 8, 7, 1, 6, 1, 5) 103
(3, 8, 5, 2, 3, 6, 2, 7, 5, 4, 8, 1, 6, 1, 4, 7) 104
(3, 8, 6, 1, 3, 1, 5, 7, 4, 6, 8, 2, 5, 4, 2, 7) 105
(3, 8, 6, 2, 3, 5, 2, 7, 4, 6, 8, 5, 1, 4, 1, 7) 106
(4, 1, 6, 1, 7, 4, 8, 3, 5, 6, 2, 3, 7, 2, 5, 8) 107
(4, 1, 6, 1, 7, 4, 8, 5, 2, 6, 3, 2, 7, 5, 3, 8) 108
(4, 1, 6, 1, 8, 4, 5, 7, 2, 6, 3, 2, 5, 8, 3, 7) 109
(4, 1, 8, 1, 7, 4, 2, 5, 6, 2, 3, 8, 7, 5, 3, 6) 110
(4, 2, 5, 7, 2, 4, 8, 6, 5, 3, 1, 7, 1, 3, 6, 8) 111
(4, 2, 5, 8, 2, 4, 6, 7, 5, 1, 3, 1, 8, 6, 3, 7) 112
(4, 2, 6, 8, 2, 4, 3, 7, 5, 6, 3, 1, 8, 1, 5, 7) 113
(4, 2, 7, 5, 2, 4, 8, 6, 3, 5, 7, 1, 3, 1, 6, 8) 114
(4, 5, 6, 7, 3, 4, 8, 5, 3, 6, 2, 7, 1, 2, 1, 8) 115
(4, 5, 7, 8, 1, 4, 1, 5, 6, 3, 7, 2, 8, 3, 2, 6) 116
(4, 6, 1, 7, 1, 4, 8, 5, 6, 2, 3, 7, 2, 5, 3, 8) 117
(4, 6, 1, 8, 1, 4, 7, 3, 6, 5, 2, 3, 8, 2, 7, 5) 118
(4, 6, 3, 5, 8, 4, 3, 7, 6, 5, 1, 2, 1, 8, 2, 7) 119
(4, 6, 3, 7, 8, 4, 3, 2, 6, 5, 2, 7, 1, 8, 1, 5) 120
(4, 6, 7, 2, 8, 4, 2, 3, 6, 5, 7, 3, 1, 8, 1, 5) 121
(4, 6, 8, 2, 5, 4, 2, 7, 6, 3, 5, 8, 1, 3, 1, 7) 122
(4, 7, 1, 6, 1, 4, 8, 5, 3, 7, 6, 2, 3, 5, 2, 8) 123
(4, 7, 1, 8, 1, 4, 3, 5, 6, 7, 3, 2, 8, 5, 2, 6) 124
(4, 7, 5, 3, 6, 4, 8, 3, 5, 7, 2, 6, 1, 2, 1, 8) 125
(4, 8, 1, 5, 1, 4, 6, 7, 3, 5, 8, 2, 3, 6, 2, 7) 126
(4, 8, 5, 2, 6, 4, 2, 7, 5, 3, 8, 6, 1, 3, 1, 7) 127
(5, 1, 6, 1, 8, 4, 5, 7, 3, 6, 4, 2, 3, 8, 2, 7) 128
(5, 1, 7, 1, 8, 3, 5, 4, 6, 3, 7, 2, 4, 8, 2, 6) 129
(5, 1, 8, 1, 3, 6, 5, 7, 3, 4, 2, 8, 6, 2, 4, 7) 130
(5, 2, 4, 7, 2, 8, 5, 4, 6, 3, 1, 7, 1, 3, 8, 6) 131
(5, 2, 4, 8, 2, 7, 5, 4, 6, 1, 3, 1, 8, 7, 3, 6) 132
(5, 2, 8, 3, 2, 7, 5, 3, 6, 4, 1, 8, 1, 7, 4, 6) 133
(5, 2, 8, 6, 2, 3, 5, 7, 4, 3, 6, 8, 1, 4, 1, 7) 134
(5, 3, 6, 4, 8, 3, 5, 7, 4, 6, 1, 2, 1, 8, 2, 7) 135
(5, 3, 7, 8, 2, 3, 5, 2, 6, 4, 7, 1, 8, 1, 4, 6) 136
(5, 6, 1, 8, 1, 4, 5, 7, 6, 3, 4, 2, 8, 3, 2, 7) 137
(5, 6, 2, 8, 4, 2, 5, 7, 6, 4, 3, 1, 8, 1, 3, 7) 138
(5, 8, 1, 4, 1, 6, 5, 7, 4, 3, 8, 2, 6, 3, 2, 7) 139
(5, 8, 2, 3, 7, 2, 5, 3, 6, 4, 8, 1, 7, 1, 4, 6) 140
(5, 8, 2, 4, 6, 2, 5, 7, 4, 3, 8, 6, 1, 3, 1, 7) 141
(5, 8, 4, 1, 7, 1, 5, 4, 6, 3, 8, 2, 7, 3, 2, 6) 142
(6, 1, 5, 1, 7, 4, 8, 6, 5, 3, 4, 2, 7, 3, 2, 8) 143
(6, 2, 5, 7, 2, 4, 8, 6, 5, 3, 4, 7, 1, 3, 1, 8) 144
(6, 2, 7, 4, 2, 5, 8, 6, 4, 3, 7, 5, 1, 3, 1, 8) 145
(6, 3, 5, 7, 4, 3, 8, 6, 5, 4, 2, 7, 1, 2, 1, 8) 146
(7, 1, 4, 1, 5, 6, 8, 4, 7, 3, 5, 2, 6, 3, 2, 8) 147
(7, 2, 4, 5, 2, 6, 8, 4, 7, 5, 3, 1, 6, 1, 3, 8) 148
(7, 2, 4, 6, 2, 5, 8, 4, 7, 3, 6, 5, 1, 3, 1, 8) 149
(7, 3, 4, 5, 6, 3, 8, 4, 7, 5, 2, 6, 1, 2, 1, 8) 150
150
comentou Dez 9, 2020 por JOAO PAULO (26 pontos)  
Luiz, sua resposta foi muito boa. Um ponto interessante que você considerou, mas não mencionou explicitamente é o problema de eficiência quando começamos a tratar de “n” grandes. No entanto, como o problema pede para fazermos com n<=8, a eficiência não se torna um problema maior. Outro ponto se refere as sequências geradas. Note que para n=3 ou n=4, por exemplo, as sequências geradas pelos “prints” são inversas uma da outra, o que na realidade representaria apenas uma sequência distinta (você salientou esse ponto na sua resposta). Logo, uma sugestão adicional em relação ao seu código é inserir a seguinte condicional:  
                                             if sequencia and sequencia < sequencia[::-1]:
no lugar de:
                                                                if sequencia:
dentro da função langford

Essa pequena alteração permite visualizarmos apenas as sequências distintas.  Um abraço
comentou Dez 16, 2020 por Luiz Filippe (21 pontos)  
Obrigado pela contribuição, João! Alterei o código com a inclusão da sua sugestão.
...