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

Quantos Trios de Langford existem para o conjunto \( \{1,2,3,...9 \} \)?

+3 votos
47 visitas
perguntada Mai 10 em Programação Computacional por Stuart Mill (1,084 pontos)  
editado Mai 10 por Stuart Mill

A imagem será apresentada aqui.

Pares de Langford

  • Explicarei primeiro o que é um Par de Langford para depois ir ao problema de gerar os trios de Langford. Um Par de Langford de tamanho n (denotado \( L(2,n) \) ) é uma permutação da sequência 1,1,2,2,...,9,9 de modo que entre cada k, haja k números diferentes de k. Por exemplo, para o caso mais simples em que n=3 (L(2,3)), só há uma possibilidade, a saber:
  • 2 3 1 2 1 3
  • Note que entre o par de 2 existem dois números diferentes de 2 (i.e. 3 e 1); entre o par de 1, apenas um número diferente de 1 (i.e. 1); e entre o par de 3, 3 números diferentes de 3 (i.e. 1,2 e 1 novamente).

Trios de Langford

  • Um trio de Langford de tamanho n (L(3,n)) é uma extensão direta do Par de Langford. As condições para os números dois a dois na sequência são as mesmas; a diferença é que a sequência original que devemos ordenar tem 3 elementos de cada número, a saber 1,1,1,2,2,2,...,n,n,n

Problema

  • O problema consiste, portanto, em encontrar o número de sequências de Langford para L(3,9).
Compartilhe

1 Resposta

+4 votos
respondida Mai 10 por Stuart Mill (1,084 pontos)  
editado Mai 10 por Stuart Mill

Força Bruta?

  • Perceba que a primeira solução possível, gerar todas as permutações possíveis e depois checar quais delas são Langford é bastante ineficiente para n grandes. Knuth faz uma estimativa do número de sequências de Pares de Langford como sendo da ordem \( {\frac{4n}{e^3}}^{n+0.5} \) . Portanto, gerar todas as permutações e depois checar, para cada permutação, todos os trios (ou até encontrar um trio que falhe) seria um desastre.

Backtracking

  • Uma outra possibilidade é a seguinte. Imagine criar uma pilha com i=1,...9, tendo 9 no topo. Seria possível também ter 1 no topo da pilha, mas escolher o maior número minimiza a possibilidade de nós iniciais, i.e., a quantidade de posições legais para colocar o trio numa sequência de 27 espaços vazios (pode-se pensar que são zeros). Por exemplo, enumerando as posições de 1 a 27, a primeira possibilidade seria colocar o primeiro nove em 1, o segundo em 11 e o terceiro em 21. A segunda possibilidade colocaria o primeiro nove em 2, o segundo em 12 e o terceiro em 22, e assim por diante. Cobrindo todos esses deslocamentos unitários do par até 27, temos todas as possibilidades de nós iniciais.
  • Uma vez que o trio-9 foi colocado com sucesso (facilita muito pensarmos na operação de colocar o trio inteiro de uma vez, em vez dos números em separado), passamos para o 8. Dada a posição do trio-9, o programa registraria todas as posições legais para o trio-8, escolheria uma primeira, e passaríamos para o 7. Agora, imagine que dada a configuração anterior, não há posições legais para o 7. Então o 7 seria colocado de volta na pilha, e tentaríamos a próxima posição legal para o 8, jogando fora a utilizada anteriormente. Com essa nova posição para o 8, passaríamos para o 7. Se houver posições legais, selecionamos a primeira e partimos para o próximo número, o 6. Se não, voltamos para o 8 e sua próxima posição legal. Se o 8 não tiver mais posições legais, voltamos para a segunda posição legal do 9, e assim por diante. Essa é essencialmente a estratégia do backtracking.
  • Para o Python, existe uma solução bem simples que usa a ideia descrita anteriormente, mas se dá de forma recursiva, e será discutida abaixo.

Solução

Segue abaixo o código para a solução.

def langford(n, seq):

# O próximo valor da sequência 9,8,7,...,1
next_n = n - 1
# Primeiro, vai procurar para cada valor (começando do 9), as posições
#legais. No loop for, ele procura quais as posições possíveis para o trio
#que ainda ficam dentro do range da sequência.
for i in range(0, len(seq) - 2*(n+1)):
    j = i + n + 1
    k = j + n + 1
    #Agora, o programa testa se todos os números estão vazios. Se algum deles
    #não for vazio (diferente de 0), não entra nesse if, e tenta outro i
    #no for de cima.
    if not (seq[i] or seq[j] or seq[k]):
        # Caso os três espaços estejam vazios, são preenchidos com n.
        #Assim, o trio-n está colocado.
        seq[i] = seq[j] = seq[k]= n
        # Se o próximo n for diferente de 0 (isto é, falta espaços na sequência)
        # chamamos a função no próximo número.
        if not(next_n==0):
            # Passo importante: Aqui, salvamos tudo o que já imprimimos na sequência
            # e repetimos os passos anteriores para o próximo número.
            # Perceba que aqui é onde o backtracking é executado de fato.
            yield from langford(next_n, seq)
        else:
            # Se a sequência estiver completa, retorna-se uma cópia dessa sequência.
            # Perceba que o programa NÃO PARA aqui. Ele vai continuar seguindo os loops
            #para encontrar todas as soluções.
            yield seq[:]
        #Agora, se este nó inicial para esse n foi tentado (todos os próximos nós explorados)
        #apagamos as posições da sequência para tentar a próxima posição legal (próximo i no loop de cima).
        # Note que este nó inicial ser frutífero ou não vai depender dos resultados das recursões.
        # Se foi frutífero, vai ter retornado a sequência-solução.

        seq[i] = seq[j] = seq[k]= 0

Para printar os resultados, temos:

def lang_triples(n):
   solucoes = list(langford(n,[0]*3*n))
   count = 1
   for i in solucoes:
       print("Esta é a solução número " + str(count))
       print(i)
       count = count + 1
   print("Foram encontradas " + str(len(solucoes)) + " soluções.")
lang_triples(9)

O output é:

   Esta é a solução número 1
[1, 9, 1, 6, 1, 8, 2, 5, 7, 2, 6, 9, 2, 5, 8, 4, 7, 6, 3, 5, 4, 9, 3, 8, 7, 4, 3]
Esta é a solução número 2
[1, 9, 1, 2, 1, 8, 2, 4, 6, 2, 7, 9, 4, 5, 8, 6, 3, 4, 7, 5, 3, 9, 6, 8, 3, 5, 7]
Esta é a solução número 3
[1, 8, 1, 9, 1, 5, 2, 6, 7, 2, 8, 5, 2, 9, 6, 4, 7, 5, 3, 8, 4, 6, 3, 9, 7, 4, 3]
Esta é a solução número 4
[3, 4, 7, 9, 3, 6, 4, 8, 3, 5, 7, 4, 6, 9, 2, 5, 8, 2, 7, 6, 2, 5, 1, 9, 1, 8, 1]
Esta é a solução número 5
[7, 5, 3, 8, 6, 9, 3, 5, 7, 4, 3, 6, 8, 5, 4, 9, 7, 2, 6, 4, 2, 8, 1, 2, 1, 9, 1]
Esta é a solução número 6
[3, 4, 7, 8, 3, 9, 4, 5, 3, 6, 7, 4, 8, 5, 2, 9, 6, 2, 7, 5, 2, 8, 1, 6, 1, 9, 1]
Foram encontradas 6 soluções.

Obs.: O comando yield from não está disponível no Python 2. Essa sintaxe permite delegar de um gerador para um subgerador, ou de um iterador para um sub iterador. No nosso caso, cada vez que a função é chamada e coloca um trio com sucesso, ela delega para a próxima recursão colocar o próximo trio.

Portanto, a resposta a pergunta é que temos 6 Trios de Langford para n=9. Há um pequeno detalhe em relação a esse resultado, mas irei deixar para o aluno que for comentar a resposta. :)

comentou Mai 28 por Pablo Castro (286 pontos)  
Ótima resposta. Vale observar que para uma sequência de Langford, a sua inversa também é uma sequência de Langford. Neste exercício, por exemplo, a solução 1 é igual a inversa da solução 6, a solução 2 é igual a inversa da solução 5 e a solução 3 é igual a inversa da solução 4.

Então, para dado n que gere k sequências de Langford, estamos interessados apenas nas k/2 primeiras sequências geradas.
...