Antecedentes

Una secuencia Davenport-Schinzel tiene dos parámetros enteros positivos dy n. Denotaremos el conjunto de todas las secuencias de Davenport-Schinzel para parámetros dados por DS(d,n).

Considere todas las secuencias de los números naturales 1para n, inclusive, que satisfagan:

• No hay dos números consecutivos en la secuencia que sean idénticos.
• No hay subsecuencia (no necesariamente consecutiva) de longitud mayor que d, que alterna entre dos números diferentes.

Deje Ldenotar la longitud máxima de tal secuencia (dado dy n). Entonces, DS(d,n)es el conjunto de todas esas secuencias con longitud L.

Algunos ejemplos pueden ayudar. Deje d = 4, n = 3. Las secuencias más largas posibles con estas restricciones tienen L = 8. Entonces lo siguiente es miembro de DS(4,3):

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

No hay números idénticos consecutivos y hay subsecuencias alternas de longitud 4, pero no más largas:

 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

Los siguientes ejemplos no están en 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 obtener más información, consulte MathWorld y OEIS y las referencias que enumeran.

El reto

Dados dos enteros positivos ny dgenerar cualquier secuencia Davenport-Schinzel en DS(d,n). Tenga en cuenta que estos no son generalmente únicos, por lo que genera cualquier resultado válido único.

Puede escribir un programa o función, tomando datos a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función, y devolviendo el resultado de la función o imprimiéndolo en STDOUT (o la alternativa más cercana).

Puede usar cualquier cadena conveniente o un formato de lista inequívoco para la salida.

Este es el código de golf, por lo que gana el envío más corto (en bytes).

Longitudes de secuencia

Como las secuencias no son únicas, no hay mucho uso para ejemplos individuales en este desafío. Sin embargo, los dos problemas generales de validez son bastante fáciles de verificar para cualquier salida, por lo que la pregunta principal es si la secuencia tiene la longitud correcta (o si hay una secuencia válida más larga). Por lo tanto, aquí hay una lista de los ¹ conocidos Lpara dado dy 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 ...

No debe codificar ninguna información de esta tabla en su envío.

¹ Esta tabla es de 1994, por lo que puede haber habido más progreso desde entonces, pero dudo que cualquier presentación pueda manejar incluso las entradas más grandes en esta tabla en un período de tiempo razonable.

Pitón 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]

La entrada está simplemente en el formato 4, 3.

I iterativamente creo todas las secuencias, que comienzan con 1y satisfacen las dos propiedades, y las almaceno S. Como los creo en orden (ordenados por longitud [y por valores]), la última entrada debe ser una secuencia Davenport-Schinzel. Utiliza el hecho interesante de que puedes iterar sobre una lista mientras la anexas.