Betrachten Sie eine binäre Sequenz mit 1und 2, zB:

1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1 ...

Schreiben wir die Lauflängen auf:

1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1 ...
_  _  ____  ____  _  _  _  ____
1, 1, 2,    2,    1, 1, 1, 2,   ...

In diesem Fall erhalten wir zufällig eine andere binäre Sequenz. Dies ist natürlich nicht garantiert (z. B. wenn wir den Vorgang wiederholen würden, wäre dies der dritte Durchgang 3), aber nehmen wir an, dass dies der Fall ist .

Nun stellt sich die Frage, ob wir eine Sequenz finden können, bei der diese Art der Lauflängencodierung mehrmals angewendet wird, um die ursprüngliche Sequenz wiederherzustellen. Für eine Zykluslänge von 1 (dh einen Fixpunkt dieser Transformation) ergibt sich die Oldenburger-Kolakoski-Sequenz (OEIS-Eintrag A0000002 ):

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, ...

(Es gibt tatsächlich eine andere Lösung: Wir können auch das führende weglassen 1.)

Was ist mit einem Zyklus der Länge 2? Das ist auch möglich! Die folgenden beiden Sequenzen sind die Liste der Lauflängen der jeweils anderen:

1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, ...
2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, ...

(Dies sind die OEIS-Einträge A025142 und A025143 . Dies ist die einzige Lösung.)

Können wir einen Zyklus der Länge 3 finden? Klar, hier ist jede Sequenz die Lauflängencodierung der nächsten (und die dritte ist die Lauflängencodierung der ersten):

1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, ...
1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, ...
2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, ...

In diesem Fall gibt es eine andere Lösung. Es stellt sich heraus, dass wir für jede Zykluslänge einen solchen Zyklus finden können. Tatsächlich wird die Anzahl der unterschiedlichen Zyklen der Länge n durch den OEIS-Eintrag A001037 angegeben (dies zählt nicht die willkürliche Wahl, welche Sequenz in einem Zyklus als erste angesehen wird).

Unterhaltsame Tatsache: So unwahrscheinlich es auch scheint, diese Herausforderung wurde durch das Studium der komplexen Karte angeregt f(z) = z - 1/z. Wer herausfindet, was diese Karte mit dieser Herausforderung zu tun hat, bekommt einen Cookie.

Die Herausforderung

Bei gegebener Zykluslänge k > 0und Sequenzlänge n > 0werden die ersten nTerme kverschiedener (unendlicher) Binärsequenzen ausgegeben, die unter der obigen Lauflängentransformation einen Zyklus bilden. Wenn mehrere Zyklen vorhanden sind, können Sie einen davon ausgeben. Es liegt an Ihnen, mit welcher Sequenz im Zyklus begonnen wird und in welche Richtung der Zyklus verläuft (Sie können sie entweder so ausgeben, dass jede Sequenz die nächste beschreibt, oder so, dass jede Sequenz die vorherige zyklisch beschreibt).

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Ausgabe kann in jedem geeigneten, eindeutigen, verschachtelten Listenformat erfolgen, so dass die äußere Dimension kund die innere Dimension vorliegen n.

Es gelten die Standardregeln für Code-Golf .

Zusätzliche Beispiele

Hier sind einige Beispiele. Aber wie gesagt, die Lösungen sind nicht eindeutig, daher können Ihre eigenen Lösungen abweichen und trotzdem korrekt sein. Vielleicht helfen Ihnen diese, eine Lösung zu finden. Auf jedes Beispiel k nfolgen die Sequenzen, sodass jede Zeile die nächste (zyklisch) beschreibt:

4 20
1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1
2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1

5 6
2, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2
2, 1, 2, 2, 1, 1
1, 1, 2, 1, 1, 2
2, 1, 2, 2, 1, 2

8 20
2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2
2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2
1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1
2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1

13 50
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1
1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1
1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1
1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1

Beachten Sie, dass sich nicht alle Zeilen in den letzten beiden Ausgaben unterscheiden, obwohl sie letztendlich ngroß genug wären .

Verwandte Fragen

• Erzeugen Sie eine Kolakoski-Sequenz

CJam (41 Bytes)

{Ma*{1:Bm<{1+ee{(1&B^)+}%e~A<0:B;}%}@:A*}

Dies ist eine anonyme Funktion, die Eingaben auf dem Stapel in der Reihenfolge entgegennimmt n kund Ausgaben auf dem Stapel belässt. Online-Demo

Die Grundidee besteht darin, mit einer Lyndon-Wortspalte zu beginnen [2 1 1 1 ...]und iterativ direkt auf der Grundlage zu erweitern, dass wir, wenn wir das Anfangselement jeder Zeile und die Abwechslung kennen, die Lauflängendekodierung durchführen und mehr Elemente erhalten können.

Haskell, 72 Bytes

~(a:b)?c=c:[c|a>1]++b?(3-c)
k!n=take k$take n<$>last(k!n)?2:map(?1)(k!n)

Demo:

*Main> 4!20
[[2,1,1,2,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,1],[1,1,2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1],[1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2],[1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2]]