Segue o texto do problema original descrito no livro do Knuth
Suppose n = 4m – 1. Construct arrangements of Langford pairs for the numbers {1, 1, . . ., n, n}, with the property that we also obtain a solution for n = 4m by changing the first ‘2m – 1’ to ‘4m’ and appending ‘2m – 1 4m’ at the right. Hint: Put the m – 1 even numbers 4m – 4, 4m – 6, . . ., 2m at the left.
Na análise combinatória , um emparelhamento de Langford , também chamado de sequência de Langford , é uma permutação da sequência de 2n números 1, 1, 2, 2, ..., n , n em que os dois 1s estão separados por uma unidade, dois 2s estão separados por duas unidades e, mais geralmente, as duas cópias de cada número k estão separadas por k unidades. Emparelhamentos Langford são denomindos desta forma em homenagem a C. Dudley Langford, que apresentou o problema em 1958.
Primeiro ponto interessante deste problema é que dada a equação de formação de n = 4m - 1 sempre teremos um valor de n cujo valor de n%4=3 isso faz com que seja sempre possível a construção de uma de uma sequencia de Langford ou pares de LangFord.
Nessa solução começamos com uma seqüência de zeros. Começando com o número mais alto, tentamos colocar um par de números em um par de "slots" que satisfaçam a regra, e se formos bem-sucedidos, avançamos para colocar o próximo par de números, se não houver mais números para colocar no array, encontramos solução e podemos armazená-la.
Caso o número não preencha nenhum espaço possível, usamos o backtracking e realocamos os números anteriores.
Algumas referências interessantes sobre o tema podem ser vistas abaixo:
#Esse método construí a sequência para 4m pares de números.
def arranjo4m(m, lista):
B = lista + [2*m - 1, 4*m]
C = [(n, B[n]) for n, x in enumerate(B) if x ==(2*m - 1)]
B[C[0][0]]=4*m
return B
# O método abaixo gera a sequencia de langfor de forma recursiva usando backtracking
def langford(n, seq):
# o próxim valor de N
n1 = n - 1
# Verifica se a posição do par é válida para um n específico
for i in range(0, len(seq) - n - 1):
j = i + n + 1
if not (seq[i] or seq[j]):
#insere o valor de na na sequência
seq[i] = seq[j] = n
if n1:
# chamada recursiva para adicionar o próximo valor de n.
yield from langford(n1, seq)
else:
#Condição de parada, não existe mais nada para inserir, retorna a sequência
yield seq
# Remove o valor de n da sequência que estamos montando
# para tentar a próxima posição
seq[i] = seq[j] = 0
def main():
m = 3
n = 4 * m - 1
for i, A in enumerate(langford(n, [0] * 2 * n), 1):
print (i) # cardinalidade da solução encontrada
print(A) # solução para 4m-1
B = arranjo4m(m, A) # Arranjo para 4m construido a partir de A.
print(B)
#permite que você veja o progresso quando ele né grande.
if i % 1000 == 0:
print(' ', i, end='\r', flush=True)
#a divisão por 2 ocorre pois, convencionalmente, duas sequências de Langford são
# consideradas iguais se uma for inversa da outra.
print('\n', i // 2) #imprime o total de sequências
main()