Cycles in run-length encoding

Question

Consider some binary sequence, using 1 and 2, e.g.:

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

Let's write down the run lengths of that:

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

In this case we happen to get another binary sequence. Of course, that's not guaranteed (e.g. if we repeated the process, the third run would be 3), but let's assume we do.

Now the question is, can we find a sequence such that applying this type of run-length encoding multiple times gives us back the original sequence? For a cycle-length of 1 (i.e. a fixed point of this transformation), we find the Oldenburger-Kolakoski sequence (OEIS entry 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, ...

(There is actually another solution: we can also omit the leading 1.)

What about a cycle of length-2? That's also possible! The following two sequences are each others' list of run lengths:

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, ...

(These are OEIS entries A025142 and A025143. This is the only solution.)

Can we find a cycle of length 3? Sure, here each sequence is the run-length encoding of the next (and the third one is the run-length encoding of the first):

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 this case there is one other solution. It turns out that we can find such a cycle for every cycle length. In fact, the number of distinct cycles of length n is given by OEIS entry A001037 (this is not counting the arbitrary choice of which sequence in a cycle is considered the first).

Fun fact: As unlikely as it seems, this challenge was inspired by studying the complex map f(z) = z - 1/z. Whoever figures out what that map has to do with this challenge gets a cookie.

The Challenge

Given a cycle length k > 0 and a sequence length n > 0, output the first n terms of k distinct (infinite) binary sequences that form a cycle under the above run-length transformation. If multiple cycles exist, you may output any one of them. It's up to you which sequence in the cycle to start with, and which direction the cycle goes (so you can either output them such that each sequence describes the next, or such that each sequence describes the previous one, cyclically).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be in any convenient, unambiguous, nested list format, such that the the outer dimension is k and the inner dimension is n.

Standard code-golf rules apply.

Additional examples

Here are some examples. But as I said, the solutions are not unique, so your own solutions might differ and still be correct. Maybe these will help you come up with a solution though. Each example is k n followed by the sequences, such that each line describes the next (cyclically):

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

Note that not all of the lines in the last two outputs differ, although they would eventually if n was large enough.

Related Questions

• Generate a Kolakoski sequence

Answer 1

CJam (41 bytes)

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

This is an anonymous function which takes input on the stack in the order n k and leaves output on the stack. Online demo

The basic idea is to start with a Lyndon word column [2 1 1 1 ...] and iteratively extend right on the basis that knowing the initial element of each row and the alternation we can run-length decode and get more elements.

Answer 2

APL (Dyalog Unicode), 35 bytes

{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}

Try it online!

An anonymous dfn whose left argument is n and right is k.

Almost direct translation of Anders Kaseorg's Haskell answer (adapted to the finite and strict nature of APL arrays), with a bit of hint from Peter Taylor's idea:

The basic idea is to start with a Lyndon word column [2 1 1 1 ...] and iteratively extend right on the basis that knowing the initial element of each row and the alternation we can run-length decode and get more elements.

How it works

{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}  ⍝ left argument(⍺)←n, right(⍵)←k
                             1+⍵↑1   ⍝ u←[2, 1, ..., 1] of length k
                            ⍨        ⍝ Run the following with both sides being u:
 (                       )⍣≡         ⍝  Repeat until fixpoint:
                                     ⍝  (left: u, right: intermediate result v)
                     ¯1⌽⊢            ⍝   Rotate v down once
     ⊣{            }¨                ⍝   Zip with left side u: (left elem u_i, right elem v_i)
              ⍺,3-⍺                  ⍝    Make a 2-elem array [u_i, 3-u_i] which is [1 2] or [2 1]
         (≢⍵)⍴                       ⍝    Cycle the above to the length of v_i
       ⍵/                            ⍝    Duplicate each element of above v_i times e.g. 1 1 2/2 1 2 → 2 1 2 2
       ⍵/(≢⍵)⍴⍺,3-⍺                  ⍝    Run-length decode v_i with alternating 1 and 2's, starting with u_i
  ⍺↑¨                                ⍝   Extend or truncate each row to length n

Comparison with Anders' Haskell version

Anders' Haskell code (parenthesized for clarity) works like this:

~(a:b)?c=(c:[c|a>1])++(b?(3-c))
  (c:[c|a>1])  -- Two copies of c if head of x > 1, one copy otherwise
  ++(b?(3-c))  -- Run-length decode the rest with alternating 1 and 2

k!n=take k$take n<$>((last(k!n))?2):(map(?1)(k!n))
  take k$         -- take first k rows
  take n<$>       -- take first n elements from each row
  ((last(k!n))?2) -- run-length decode the last row with starting value 2
  :(map(?1)(k!n)) -- run-length decode the other rows with starting value 1

In one iteration, this is equivalent to "prepend the k-th row, run-length decode each row, and then discard the last row". We can simplify it to "rotate once and run-length decode", which I implemented as ¯1⌽.

For the run-length decoding function, I simply used the APL primitive /, while the Haskell version uses infinite lists to implement it.

Answer 3

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]]

Answer 4

05AB1E, 22 bytes

YΔ´12¹иćRšvyÞsÅΓI∍Dˆ]¯

Try it online!