fundo

Uma sequência de Davenport-Schinzel possui dois parâmetros inteiros positivos de n. Vamos denotar o conjunto de todas as seqüências de Davenport-Schinzel para determinados parâmetros por DS(d,n).

Considere todas as seqüências dos números naturais 1para n, inclusive, que satisfazem:

• Não há dois números consecutivos na sequência são idênticos.
• Não há subsequência (não necessariamente consecutiva) de comprimento maior que d, que alterna entre dois números diferentes.

Vamos Ldenotar o comprimento máximo de uma sequência (dada de n). Então, DS(d,n)é o conjunto de todas essas seqüências com comprimento L.

Alguns exemplos podem ajudar. Vamos d = 4, n = 3. As seqüências mais longas possíveis com essas restrições têm L = 8. Portanto, o seguinte é um membro de DS(4,3):

[1, 2, 1, 3, 1, 3, 2, 3]

Não há números idênticos consecutivos e existem subsequências alternadas de comprimento 4, mas não números mais longos:

 1  2  1           2
 1  2        1     2
 1        3  1  3
 1        3  1        3
    2     3        2  3
    2           3  2  3
       1  3  1  3
       1  3  1        3

Os seguintes exemplos não estão em DS(4,3):

[1, 2, 2, 3, 1, 3, 2, 3]  # Two consecutive 2's.
[1, 2, 1, 3, 1, 3, 2, 1]  # Contains alternating subsequences of length 5.
[1, 2, 1, 3, 1, 3, 2]     # Longer valid sequences for d = 4, n = 3 exist.

Para mais informações, consulte MathWorld e OEIS e as referências que eles listam.

O desafio

Dados dois números inteiros positivos ne d, gere qualquer sequência de Davenport-Schinzel em DS(d,n). Observe que esses geralmente não são exclusivos, portanto, produza qualquer resultado válido único.

Você pode escrever um programa ou função, recebendo informações via STDIN (ou alternativa mais próxima), argumento de linha de comando ou argumento de função e retornando o resultado da função ou imprimindo-o em STDOUT (ou alternativa mais próxima).

Você pode usar qualquer seqüência conveniente ou inequívoca ou formato de lista para saída.

Isso é código de golfe, então a submissão mais curta (em bytes) vence.

Comprimentos de sequência

Como as seqüências não são únicas, não há muito uso para exemplos individuais nesse desafio. No entanto, os dois problemas gerais de validade são razoavelmente fáceis de verificar qualquer saída, portanto a questão principal é apenas se a sequência tem o tamanho certo (ou se existe uma sequência válida mais longa). Portanto, aqui está uma lista do ¹ conhecido Lpor dado de n:

 \ 
 d\n 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 
   \-----------------------------------------------------------
 1 | 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 2 | 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 3 | 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
 4 | 1  4  8 12 17 22 27 32 37 42 47 53 58 64 69 75 81 86 92 98
 5 | 1  5 10 16 22 29 ...
 6 | 1  6 14 23 34 ...
 7 | 1  7 16 28 41 ...
 8 | 1  8 20 35 53 ...
 9 | 1  9 22 40 61 ...
10 | 1 10 26 47 73 ...

Você não deve codificar nenhuma informação desta tabela no seu envio.

¹ Esta tabela é de 1994, portanto, pode ter havido mais progresso desde então, mas duvido que qualquer envio seja capaz de lidar com as entradas maiores dessa tabela em um período de tempo razoável.

Python 2: 172

from itertools import*
d,n=input();S=[[1]]
for s in S:
 for v in range(1,n+1):
  if(v!=s[-1])*all(w[2:]!=w[:-2]for w in combinations(s+[v],d+1)):S.append(s+[v])
print S[-1]

A entrada é simplesmente no formato 4, 3.

Crio iterativamente todas as seqüências que iniciam 1e satisfazem as duas propriedades e as armazeno S. Desde que eu os criei em ordem classificada (classificada por comprimento [e por valores]), a última entrada deve ser uma sequência de Davenport-Schinzel. Usa o fato interessante de que você pode iterar sobre uma lista enquanto anexa a ela.