tło

Sekwencja Davenport Schinzel ma dwie pozytywne parametrów całkowitych di n. Oznaczymy zestaw wszystkich sekwencji Davenporta-Schinzela dla danych parametrów przez DS(d,n).

Rozważ wszystkie sekwencje liczb naturalnych 1do nwłącznie, które spełniają:

• Żadne dwie kolejne liczby w sekwencji nie są identyczne.
• Nie ma podsekwencji (niekoniecznie kolejnych) o długości większej niż d, która zmienia się między dwiema różnymi liczbami.

Niech Loznacza maksymalną długość takiej sekwencji (podaną di n). Następnie DS(d,n)jest zbiorem wszystkich takich sekwencji o długości L.

Niektóre przykłady mogą pomóc. Pozwól d = 4, n = 3. Najdłuższe możliwe sekwencje z tymi ograniczeniami mają L = 8. Więc następujące jest członkiem DS(4,3):

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

Nie ma kolejnych identycznych liczb i występują naprzemienne podciągi długości 4, ale nie dłuższe:

 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

Następujących przykładów nie ma w 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.

Aby uzyskać więcej informacji, zobacz MathWorld i OEIS oraz wymienione w nich odniesienia.

Wyzwanie

Biorąc pod uwagę dwie dodatnie liczby całkowite ni dwygeneruj dowolną sekwencję Davenporta-Schinzela w DS(d,n). Zauważ, że generalnie nie są one unikalne, więc wypisz dowolny poprawny wynik.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i zwracając wynik z funkcji lub drukując go do STDOUT (lub najbliższej alternatywy).

Możesz użyć dowolnego wygodnego, jednoznacznego formatu ciągu lub listy do wydrukowania.

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).

Sekwencje długości

Ponieważ sekwencje nie są unikalne, poszczególne przykłady w tym wyzwaniu nie mają wiele zastosowania. Jednak dwa ogólne problemy z poprawnością są dość łatwe do sprawdzenia dla dowolnego wyniku, więc głównym pytaniem jest, czy sekwencja ma odpowiednią długość (czy istnieje dłuższa ważna sekwencja). Dlatego oto lista znanych ¹ L dla podanych di 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 ...

Nie możesz zakodować żadnych informacji z tej tabeli w swoim zgłoszeniu.

¹ Ta tabela pochodzi z 1994 r., Więc od tego czasu może być większy postęp, ale wątpię, aby każde zgłoszenie mogło obsłużyć nawet większe wpisy w tej tabeli w rozsądnym czasie.

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]

Dane wejściowe są po prostu w formacie 4, 3.

Ieracyjnie tworzę wszystkie sekwencje, które zaczynają się 1i spełniają dwie właściwości, i przechowuję je S. Ponieważ tworzę je w posortowanej kolejności (posortowanej według długości [i według wartości]), ostatni wpis musi być sekwencją Davenporta-Schinzela. Korzysta z miłego faktu, że możesz iterować listę podczas dołączania do niej.