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

Como fazer arranjos de pares de Langford para n, de modo que obtenhamos arranjos para n+1 com uma simples modificação?

+5 votos
41 visitas
perguntada Mai 26 em Ciência da Computação por Stuart Mill (1,159 pontos)  

O problema a seguir está presente na na página 36 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth. Para entender melhor sequências de Langford, sugiro dar uma olhada nesta pergunta.

Problema: Suponha que \(n=4m-1\). Construa sequências de Langford para n (L(2,n)), de modo que podemos criar, a partir desses, sequências de Langford de ordem superior (\( n+1\) ) colocando na penúltima posição o primeiro número \(2m - 1 \) que aparecer, substituindo por sua vez esse \( 2m - 1 \) por \(4m\) e adicionando \(4m \) na última posição.

A dica que Knuth dá é muito importante (na verdade, é o caminho direto para a solução do problema).

Dica: Adicione os \(m-1\) números pares específicos, a saber, \(4m-4\), \(4m-6\),....,\(2m\) à esquerda da sequência (nas primeiras \(m-1\) posições).

Compartilhe

1 Resposta

+6 votos
respondida Mai 26 por Stuart Mill (1,159 pontos)  

Para entender melhor o problema, vamos começar com o caso mais simples. Suponha \(n=3 \implies m=1 \because m := \frac{n+1}{4}\). Só temos uma sequência de Langford a partir do conjunto \( \{1,1,2,2,3,3 \} \), a saber, \(2-3-1-2-1-3 \). Seguindo a dica de Knuth, deveríamos adicionar os \(m-1=0\) números pares à esquerda. Neste caso, portanto, esse passo pode ser pulado. O primeiro \(2m-1 = 1\) que aparece está na segunda posição. Levando o problema para a dimensão posterior \(n+1=4\), devemos adicionar \(1\) na penúltima posição, um \(4\) na posição de onde tiramos o \(1\) e outro \(4\) na última posição. O processo é mais ou menos o seguinte então:

Langford original: \(2-3-1-2-1-3 \)
Próxima dimensão (passo auxiliar): \(2-3-1-2-1-3-4-4 \)
Nova Langford: \(2-3-4-2-1-3-1-4 \)

De fato, é simples verificar que a nova sequência na dimensão superior continua sendo de Langford.

Uma condição necessária para tudo isso dar certo é que o resto da divisão de n por 4 seja 3, de modo que o resto da divisao de n+1 por 4 seja 0. Isso garante que pares de Langford existirão para n e n+1 (o que nem sempre é o caso). A estratégia utilizada será a de gerar as sequências de Langford para n+1, filtrar aquelas em que os primeiros m-1 pares (específicos) estão à esquerda, e filtrar aquelas em que temos 2m-1 e 4m à direita (duas últimas posições). Por fim, para resolver o problema, devemos voltar aos arranjos em n; ou seja, trocamos o primeiro 4m que aparece com 2m-1 (isto é, o 4m que não está na última posição) e deletamos os últimos dois números da sequência (que serão 4m 4m). Isso deve nos levar aos arranjos em n com a propriedade desejada.

Vamos começar com o código que gera as sequências de Langford, a partir do código presente na pergunta linkada no enunciado:

def langford(n, seq):

   next_n = n - 1

for i in range(0, len(seq) - n - 1):
    j = i + n + 1
    if not (seq[i] or seq[j]):

        seq[i] = seq[j] = n
        if not(next_n==0):

            yield from langford(n1, seq)
        else:

            yield seq[:]

        seq[i] = seq[j] = 0

Agora vem a parte que realmente importa neste caso:

n=11           
m = int((n+1)/4)         

lista_lang = list(langford(n+1,[0]*2*(n+1)))

Primeiro,damos um input n válido (resto da divisão por 4 é 3); no exemplo, n=11. Criamos uma lista com as sequências de Langford para n+1. Continuando:

#Primeira condição
condicao1 = []
condicao1 = list(condicao1)
for lang in lista_lang:
            x = True
            for i in range(0,m-1):
                if lang[i] == 4*m-4-2*i:
                    pass
                else:
                    x = False
            if x== True:
                print(lang)
                condicao1.append(lang)
for i in condicao1:
    print(i)

Para as sequências de Langford, testamos os m-1 primeiros números, segundo a dica de Knuth. Colocamos as sequências que passam por esse filtro numa nova lista. Passemos agora à segunda condição, dada pelo enunciado.

# Segunda condição
condicao2 = []
condicao2 = list(condicao2)
for lang in condicao1:
    if lang[-1] == 4*m and lang[-2] == 2*m-1:
        print(lang)
        condicao2.append(lang)

Checamos simplesmente se o último elemento é 4m e se o penúltimo é 2m-1. Para os que passam nessa condição, adicionamos a uma nova lista. O output será:

[8, 6, 11, 1, 2, 1, 10, 2, 6, 8, 12, 9, 7, 4, 11, 3, 5, 10, 4, 3, 7, 9, 5, 12]
[8, 6, 2, 11, 9, 2, 10, 3, 6, 8, 12, 3, 7, 4, 9, 11, 5, 10, 4, 1, 7, 1, 5, 12]
[8, 6, 2, 11, 9, 2, 4, 10, 6, 8, 12, 4, 7, 3, 9, 11, 5, 3, 10, 1, 7, 1, 5, 12]
[8, 6, 2, 11, 1, 2, 1, 10, 6, 8, 12, 9, 7, 3, 4, 11, 5, 3, 10, 4, 7, 9, 5, 12]
[8, 6, 10, 3, 9, 11, 4, 3, 6, 8, 12, 4, 7, 10, 9, 2, 5, 11, 2, 1, 7, 1, 5, 12]
[8, 6, 10, 3, 1, 11, 1, 3, 6, 8, 12, 9, 7, 10, 4, 2, 5, 11, 2, 4, 7, 9, 5, 12]
[8, 6, 9, 10, 2, 11, 4, 2, 6, 8, 12, 4, 9, 7, 10, 3, 5, 11, 1, 3, 1, 7, 5, 12]
[8, 6, 9, 2, 10, 11, 2, 3, 6, 8, 12, 3, 9, 7, 4, 10, 5, 11, 1, 4, 1, 7, 5, 12]
[8, 6, 3, 9, 7, 11, 3, 10, 6, 8, 12, 2, 7, 9, 2, 4, 5, 11, 10, 1, 4, 1, 5, 12]
[8, 6, 1, 10, 1, 7, 11, 4, 6, 8, 12, 9, 4, 7, 10, 3, 5, 2, 11, 3, 2, 9, 5, 12]
[8, 6, 9, 1, 10, 1, 11, 3, 6, 8, 12, 3, 9, 7, 4, 10, 5, 2, 11, 4, 2, 7, 5, 12]
[8, 6, 10, 1, 9, 1, 4, 11, 6, 8, 12, 4, 7, 10, 9, 2, 5, 3, 2, 11, 7, 3, 5, 12]
[8, 6, 1, 10, 1, 9, 4, 11, 6, 8, 12, 4, 7, 3, 10, 9, 5, 3, 2, 11, 7, 2, 5, 12]
[8, 6, 9, 1, 10, 1, 4, 11, 6, 8, 12, 4, 9, 7, 3, 10, 5, 2, 3, 11, 2, 7, 5, 12]
[8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 12, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9, 5, 12]

Note: O primeiro elemento 4m (neste caso, o número 12) aparece sempre na mesma posição em todas as sequências de Langford que passaram pelas 2 condições! Verificando isso:

 count = 0
for lang in condicao2:
    count = count + 1
    print("Sequência " + str(count) + ":")
    for i in range(len(lang)):
        if lang[i]==4*m:
            print(i)
            break

E o output é:

    Sequência 1:
10
Sequência 2:
10
Sequência 3:
10
Sequência 4:
10
Sequência 5:
10
Sequência 6:
10
Sequência 7:
10
Sequência 8:
10
Sequência 9:
10
Sequência 10:
10
Sequência 11:
10
Sequência 12:
10
Sequência 13:
10
Sequência 14:
10
Sequência 15:
10

Isso necessariamente tem que acontecer para a sequência de Langford funcionar em n e n+1, de modo geral, podemos extrair então a posição do primeiro 4m que aparece procurando em apenas uma sequência e aplicando a todas! Para o caso geral, um código que resolveria isso seria, por exemplo (onde pegamos a primeira sequência de Langford da lista):

for i in range(len(condicao2[0])):
        if condicao2[0][i]==4*m:
            pos = i
            break

Para finalizar, vamos então para o último passo, i.e., fazer a "engenharia reversa" e voltar de n+1 para n:

for lang in condicao2:
    lang[pos] = 2*m - 1
    lang[-2] = 4*m
for i in condicao2:
    print(i)
solucao = condicao2
solucao = list(solucao)
for lang in solucao:
    del lang[-1]
    del lang[-1]
for i in solucao:
    print(i)

Usando o exemplo simples para n=4, o que fazemos aqui é:
Langford n+1: \(2-3-4-2-1-3-1-4 \)
Primeira substituição: \(2-3-1-2-1-3-1-4 \)
Segunda substituição: \(2-3-1-2-1-3-4-4 \) [Este passo na verdade pode ser pulado, mas estamos mantendo para deixar mais claro o processo]
Deletando os dois últimos = solução: \(2-3-1-2-1-3\)

Encontramos, assim, a solução do problema, cujo output para o exemplo do código (n=11) é:

[8, 6, 11, 1, 2, 1, 10, 2, 6, 8, 5, 9, 7, 4, 11, 3, 5, 10, 4, 3, 7, 9]
[8, 6, 2, 11, 9, 2, 10, 3, 6, 8, 5, 3, 7, 4, 9, 11, 5, 10, 4, 1, 7, 1]
[8, 6, 2, 11, 9, 2, 4, 10, 6, 8, 5, 4, 7, 3, 9, 11, 5, 3, 10, 1, 7, 1]
[8, 6, 2, 11, 1, 2, 1, 10, 6, 8, 5, 9, 7, 3, 4, 11, 5, 3, 10, 4, 7, 9]
[8, 6, 10, 3, 9, 11, 4, 3, 6, 8, 5, 4, 7, 10, 9, 2, 5, 11, 2, 1, 7, 1]
[8, 6, 10, 3, 1, 11, 1, 3, 6, 8, 5, 9, 7, 10, 4, 2, 5, 11, 2, 4, 7, 9]
[8, 6, 9, 10, 2, 11, 4, 2, 6, 8, 5, 4, 9, 7, 10, 3, 5, 11, 1, 3, 1, 7]
[8, 6, 9, 2, 10, 11, 2, 3, 6, 8, 5, 3, 9, 7, 4, 10, 5, 11, 1, 4, 1, 7]
[8, 6, 3, 9, 7, 11, 3, 10, 6, 8, 5, 2, 7, 9, 2, 4, 5, 11, 10, 1, 4, 1]
[8, 6, 1, 10, 1, 7, 11, 4, 6, 8, 5, 9, 4, 7, 10, 3, 5, 2, 11, 3, 2, 9]
[8, 6, 9, 1, 10, 1, 11, 3, 6, 8, 5, 3, 9, 7, 4, 10, 5, 2, 11, 4, 2, 7]
[8, 6, 10, 1, 9, 1, 4, 11, 6, 8, 5, 4, 7, 10, 9, 2, 5, 3, 2, 11, 7, 3]
[8, 6, 1, 10, 1, 9, 4, 11, 6, 8, 5, 4, 7, 3, 10, 9, 5, 3, 2, 11, 7, 2]
[8, 6, 9, 1, 10, 1, 4, 11, 6, 8, 5, 4, 9, 7, 3, 10, 5, 2, 3, 11, 2, 7]
[8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 5, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9]

Note que neste caso, temos 8s, 6s e 5s aparecendo nas mesmas posições em todas as sequências.

comentou Jun 22 por Douglas Sad Silveira (121 pontos)  
A condição necessária em que o resto da divisão de n por 4 seja 3, de modo que o resto da divisao de n+1 por 4 seja 0, é crucial na estruturação do código,  pois garante que pares de Langford existirão para n e n+1. Assim, a programação apresentada consegue, de forma clara e didática, juntar essa condição com a dica dada no enunciado, de que a sequência se inicia com 4m-4 e os últimos dois valores são dados por 2m-1 e 4m, respectivamente. A ideia de ir reduzindo a dimensão do problema, através da filtragem das condições 1 e 2, explora bastante a estrutura de listas, se mostrando eficiente do ponto de vista computacional para a resolução do exercício.
...