Contexte

Une séquence de Davenport-Schinzel a deux paramètres entiers positifs det n. Nous noterons l'ensemble de toutes les séquences de Davenport-Schinzel pour des paramètres donnés par DS(d,n).

Considérez toutes les séquences des nombres naturels 1à n, inclus, qui satisfont:

• Il n'y a pas deux nombres consécutifs dans la séquence identiques.
• Il n'y a pas de sous-séquence (pas nécessairement consécutive) de longueur supérieure à d, qui alterne entre deux nombres différents.

Soit Lla longueur maximale d'une telle séquence (donnée det n). Ensuite, DS(d,n)est l'ensemble de toutes ces séquences de longueur L.

Quelques exemples pourraient aider. Laissez d = 4, n = 3. Les séquences les plus longues possibles avec ces contraintes ont L = 8. Donc, ce qui suit est membre de DS(4,3):

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

Il n'y a pas de nombres identiques consécutifs et il y a des sous-séquences alternées de longueur 4, mais pas plus longues:

 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

Les exemples suivants ne figurent pas dans 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.

Pour plus d'informations, voir MathWorld et OEIS et les références qu'ils énumèrent.

Le défi

Étant donné deux entiers positifs, net d, générez n'importe quelle séquence de Davenport-Schinzel dans DS(d,n). Notez que ceux-ci ne sont généralement pas uniques, donc sortez tout résultat valide unique.

Vous pouvez écrire un programme ou une fonction, en prenant des entrées via STDIN (ou l'alternative la plus proche), l'argument de ligne de commande ou l'argument de la fonction, et en retournant le résultat de la fonction ou en l'imprimant dans STDOUT (ou l'alternative la plus proche).

Vous pouvez utiliser n'importe quel format de chaîne ou de liste pratique et sans ambiguïté pour la sortie.

Il s'agit du code golf, donc la soumission la plus courte (en octets) l'emporte.

Longueurs de séquence

Étant donné que les séquences ne sont pas uniques, il n'y a pas beaucoup d'utilisation pour des exemples individuels dans ce défi. Cependant, les deux problèmes généraux de validité sont assez faciles à vérifier pour n'importe quelle sortie, donc la question principale est juste de savoir si la séquence a la bonne longueur (ou s'il y a une séquence valide plus longue). Par conséquent, voici une liste des ¹ connus Lpour donnés det 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 ...

Vous ne devez coder en dur aucune information de ce tableau dans votre soumission.

¹ Ce tableau date de 1994, il peut donc y avoir eu plus de progrès depuis lors, mais je doute que toute communication soit en mesure de traiter les entrées les plus importantes de ce tableau dans un délai raisonnable.

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]

L'entrée est simplement au format 4, 3.

Je crée de manière itérative toutes les séquences, qui commencent par 1les deux propriétés et les satisfont, puis je les stocke S. Puisque je les crée dans un ordre trié (trié par longueur [et par valeurs]), la dernière entrée doit être une séquence Davenport-Schinzel. Utilise le fait agréable, que vous pouvez parcourir une liste tout en y ajoutant.