Sequências de Langford: padrões e analogias

Considere uma sequência de tamanho 2*n formada por duas cópias dos inteiros de 1 a n. Dito de outro modo, considere uma permutação dos números {1,1,2,2,3,3,..., n,n}. A sequência diz-se de Langford, de ordem n, designada por L(n), se as ocorrências de cada par do número k tiver a separá-los exactamente k inteiros. Por exemplo, (2,3,1,2,1,3) é uma sequência de Langford de ordem 3, (4,1,3,1,2,4,3,2) é uma sequência de Langford de ordem 4, (1, 2, 1, 6, 2, 8, 11, 9, 10, 3, 6, 4, 7, 3, 8, 5, 4, 9, 11, 10, 7, 5) é uma sequência de ordem 11. São várias as questões que se podem colocar sobre estas sequências :

existência: para todo o n existe pelo menos uma sequência de Langford?
construção: se existe L(n), como obtê-la?
enumeração: quantas sequências de ordem n existem?
geração: as sequências de ordem n podem ser geradas sistematicamente?
optimização: quais as soluções que maximizam (ou minimizam) f(L(n)) para uma dada função objectivo f?

O problema de Langford consiste em encontrar uma sequência de Langford para um dado n. Trata-se na realidade de um caso especial do problema combinatório mais geral conhecido por problema da cobertura exacta. Mas quem é que se pode interessar por isto? Bem, para além do prazer de brincar com a matemática, existem exemplos de aplicação concreta: resolver um problema do Sodoku é resolver um problema de cobertura exacta. O problema da cobertura exacta é um problema combinatório de elevada complexidade (*), sendo que para valores elevados de n não existe um computador suficientemente rápido, nem hoje nem amanhã, que o resolva em tempo útil. Mas nós não vamos discutir estas questões. Vamos começar por criar um programa simples que nos diz, para todo o n, se uma dada sequência é de Langford ou não. Vamos admitir que para um dado n a sequência tem comprimento de 2*n e cada inteiro entre 1 e n ocorre exactamente duas vezes. Vamos a isso.

Como resolver o problema? Vamos pensar num caso mais simples: como saber se um dado k tem k inteiros entre as suas duas ocorrências? Bem, basta encontrar as posições entre as duas ocorrências e contar as posições entre ambas. E para todos? Também não é difícil: repetir para todos inteiros no intervalo [1,n]. Asim vamos ter um ciclo repetido n vezes que faz a verificação da condição. Claro que se existir um número que não verifique a condição podemos logo abandonar o programa pois já sabemos a resposta.

view sourceprint?

01.def testa_langford(seq):

02.    """Verifica se seq é uma sequência de Langford."""

03.    ordem = len(seq)//2

04.    for k in range(1,ordem+1):

05.        indice_1 = seq.index(k)

06.        indice_2 = seq.index(k,indice_1+1,len(seq))

07.        if (indice_2 - indice_1 - 1) != k:

08.            return False

09.    return True

Nesta solução admitimos como foi dito que a sequência tem comprimento igual a 2*n e cada inteiro entre 1 e n ocorre exactamente duas vezes. Mas para ter a certeza disso não há como testar um sequência qualquer. Como fazer? Só temos que testar a existência de cada número k duas vezes, para o que recorremos ao método count para sequências:

view sourceprint?

1.def candidata(seq):

2.    “””Pode ser sequência de Langford?”””

3.    n = len(seq) // 2

4.    for k in range(1,n+1):

5.        if seq.count(k) != 2:

6.            return False

7.    return True

Olhando para este programa e para o anterior o que notamos? Seguem exactamente o mesmo padrão: um ciclo que gera os números de 1 a n de modo ordenado e um teste para verificar a condição que nos pode levar à rejeição da hipótese. Correndo o programa e ficamos todos satisfeitos... ou talvez não. Teste com o caso (1,2,1,2,3). Vai dizer-lhe que é uma candidata quando é óbvio que nunca pode ser: tem um comprimento ímpar! Nada que não se possa resolver de modo trivial:

view sourceprint?

01.def candidata(seq):

02.    “””Pode ser sequência de Langford?”””

03.    if len(seq) % 2 != 0:

04.        return False

05. 

06.    n = len(seq) // 2

07.    for k in range(1,n+1):

08.        if seq.count(k) != 2:

09.            return False

10.    return True

Para concluir vamos pensar num programa que nos indica qual a distância a que uma dada sequência se encontra de uma verdadeira sequência de Langford. O modo como pretendemos fazer isso consistirá em determinar quantos números, no intervalo de 1 a n, não satisfazem a sua condição. Informaticamente já sabemos que precisamos de um ciclo para percorrer todos os números e de um contador para contar os casos em que a condição não é satisfeita. Trata-se pois de mais um exemplo do padrão ciclo - acumulador, em que este último tem funções de contador. Pensando um pouco chegamos à conclusão que este problema é análogo ao primeiro. A diferença está em que não abandonamos o programa mal se saiba que não pode ser uma sequência de Langford, antes continuamos actualizado um contador.

view sourceprint?

01.def qualidade(seq):

02.    """Conta o número de números que satisfaz a condição e Langford."""

03.    ordem = len(seq)//2

04.    conta = 0

05.    for i in range(1,ordem+1):

06.        indice_1 = seq.index(i)

07.        indice_2 = seq.index(i,indice_1+1,len(seq))

08.        if (indice_2 - indice_1 - 1) != i:

09.            conta += 1

10.    return conta

Se ao correr o programa o resultado for 0, então sabemos que é uma sequência de Langford.

(*) Tecnicamente diz-se que é um problema NP-Completo.