Hintergrund

Eine Davenport-Schinzel-Sequenz hat zwei positive ganzzahlige Parameter dund n. Wir bezeichnen die Menge aller Davenport-Schinzel-Sequenzen für gegebene Parameter mit DS(d,n).

Betrachten Sie alle Sequenzen der natürlichen Zahlen 1zu n, einschließlich, die erfüllen:

• Keine zwei aufeinander folgenden Nummern in der Sequenz sind identisch.
• Es gibt keine (nicht unbedingt aufeinanderfolgende) Teilsequenz mit einer Länge größer als d, die zwischen zwei verschiedenen Zahlen wechselt.

Lassen Sie Lbezeichnen die maximale Länge einer solchen Sequenz (angegeben dund n). Dann DS(d,n)ist die Menge aller solcher Sequenzen mit Länge L.

Einige Beispiele könnten helfen. Lassen Sie d = 4, n = 3. Die längsten möglichen Sequenzen mit diesen Einschränkungen haben L = 8. Folgendes ist also Mitglied von DS(4,3):

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

Es gibt keine aufeinanderfolgenden identischen Zahlen und es gibt abwechselnde Teilfolgen der Länge 4, aber keine längeren:

 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

Die folgenden Beispiele sind nicht in 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.

Weitere Informationen finden Sie in MathWorld und OEIS sowie in den darin aufgeführten Referenzen.

Die Herausforderung

Bei zwei positiven ganzen Zahlen nund derzeugen Sie eine beliebige Davenport-Schinzel-Sequenz in DS(d,n). Beachten Sie, dass diese im Allgemeinen nicht eindeutig sind. Geben Sie daher ein einzelnes gültiges Ergebnis aus.

Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis von der Funktion zurückgeben oder an STDOUT (oder die nächstgelegene Alternative) drucken.

Sie können für die Ausgabe ein beliebiges bequemes, eindeutiges Zeichenfolgen- oder Listenformat verwenden.

Dies ist Code Golf, daher gewinnt die kürzeste Übermittlung (in Bytes).

Sequenzlängen

Da die Sequenzen nicht eindeutig sind, werden einzelne Beispiele in dieser Herausforderung nicht viel verwendet. Die beiden allgemeinen Gültigkeitsprobleme lassen sich jedoch relativ einfach auf Ausgaben überprüfen. Die Hauptfrage ist daher, ob die Sequenz die richtige Länge hat (oder ob es eine längere gültige Sequenz gibt). Daher ist hier eine Liste der bekannten ¹ L für gegeben dund 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 ...

Sie dürfen keine Informationen aus dieser Tabelle in Ihre Einreichung fest codieren.

¹ Diese Tabelle stammt aus dem Jahr 1994, daher gab es seitdem möglicherweise weitere Fortschritte, aber ich bezweifle, dass jede Einreichung in der Lage sein wird, auch die größeren Einträge in dieser Tabelle in angemessener Zeit zu verarbeiten.

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]

Die Eingabe erfolgt einfach im Format 4, 3.

Ich erstelle iterativ alle Sequenzen, die mit 1den beiden Eigenschaften beginnen und diese erfüllen, und speichere sie in S. Da ich sie in sortierter Reihenfolge (sortiert nach Länge [und nach Werten]) erstelle, muss der letzte Eintrag eine Davenport-Schinzel-Sequenz sein. Verwendet die nette Tatsache, dass Sie eine Liste durchlaufen können, während Sie sie anhängen.