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

Como resolver o problema dos pares de Langford?

0 votos
11 visitas
perguntada Dez 20, 2018 em Ciência da Computação por rcthiago (11 pontos)  

O problema abaixo está descrito cuidadosamente na página 36 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

[tradução própria] Suponha que n = 4m - 1. Construa arranjos de pares Langford para os números {1, 1,. . ., n, n}, com a propriedade que também obtemos uma solução para n = 4m # alterando o primeiro "2m - 1" para "4m" e acrescentando "2m - 1 4m" no lado direito. Dica: Coloque os números pares m - 1 4m - 4, 4m - 6,. . ., 2m à esquerda.

Compartilhe

1 Resposta

0 votos
respondida Dez 20, 2018 por rcthiago (11 pontos)  
editado Dez 20, 2018 por rcthiago

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.

A imagem será apresentada aqui.

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:

http://datagenetics.com/blog/october32014/index.html

https://arxiv.org/pdf/1602.08879.pdf

https://tinyurl.com/langford-paring

#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()
...