22
\$\begingroup\$

Given an integer \$ n \ge 1 \$, your task is to output an array \$ a \$ consisting of \$ n^2 + 1 \$ integers, such that all possible pairs of integers \$ (x, y) \$ satisfying \$ 1 \le x, y \le n \$ exist as a contiguous subarray in \$ a \$, exactly once.

For example, if \$ n = 2 \$, a valid output would be \$ (1, 1, 2, 2, 1) \$. We can check all possible pairs to verify that this is indeed correct:

$$ \begin{align} (1, 1) \to (\color{red}{1, 1}, 2, 2, 1) \\ (1, 2) \to (1, \color{red}{1, 2}, 2, 1) \\ (2, 1) \to (1, 1, 2, \color{red}{2, 1}) \\ (2, 2) \to (1, 1, \color{red}{2, 2}, 1) \\ \end{align} $$

Notes

  • It can be shown that a construction exists for all \$ n \$.
  • \$ a \$ may be outputted in any reasonable form (e.g. a delimiter-separated string).
  • It is recommended, but not required, to prove that your construction works for all \$ n \$.
  • This problem is closely related to asking for the de Bruijn sequence of order \$ n \$.
  • This is , so the shortest code in bytes wins.
\$\endgroup\$
0

15 Answers 15

13
\$\begingroup\$

Husk, 7 bytes

:1ṁSJṫṫ

Try it online!

This is OEIS A349526 reversed.

:1ṁSJṫṫ
      ṫ      Let i range from the input down to 1
             For each i
     ṫ         Range from i down to 1
   SJ          Insert an i between every two elements
  ṁ          Concatenate
:1           Prepend 1 to the result
\$\endgroup\$
7
\$\begingroup\$

Husk, 14 bytes

§+oṘ2ḣoṁSJoḣ←ṫ

Try it online!

How?

First, observe that this challenge is equivalent to the following:

  • Create a complete digraph consisting of \$n\$ nodes, labeled \$1\$ through \$n\$
  • Add a loop edge from each node to itself
  • Construct a traversal of the graph which follows each (directed) edge exactly once

This solution generates a sequence like this (example for input 5):

1,1,2,2,3,3,4,4,5,5,1,5,2,5,3,5,4,1,4,2,4,3,1,3,2,1

which can be divided into sections:

1,1,2,2,3,3,4,4,5,5  1,5,2,5,3,5,4  1,4,2,4,3  1,3,2  1
  • In the first section, we go from node \$1\$ to node \$n\$ in order, taking the loop edge at each node as we reach it.
  • In the second section, we take the edge from node \$n\$ to each node other than \$n-1\$ and immediately return to node \$n\$. Finally, we go to node \$n-1\$.
  • In the next section, we do the same for node \$n-1\$, visiting each node except for \$n-2\$.
  • We continue this pattern all the way back to node \$1\$.

This approach visits every directed edge exactly once: the edges \$i \to i\$ and \$i \to i+1\$ in the first section, and in \$i\$'s return section the edges \$i \to j\$ and \$j \to i\$ for all \$j < i-1\$, as well as \$i \to i-1\$.

Explanation

We construct the first section and the remaining sections separately and then concatenate them.

First section:

oṘ2ḣ
   ḣ  Range from 1 to argument, inclusive
o     Compose with
 Ṙ2   Repeat each element of a list twice

(Credit to Razetime for the Ṙ2 code.)

Remaining sections:

oṁSJoḣ←ṫ
       ṫ  Range from argument down to 1, inclusive
o         Compose with
 ṁ        Map this function and concatenate the resulting lists:
      ←     Decrement
    o       Compose with
     ḣ      Range from 1 to argument, inclusive
   J        Insert a value between all elements
  S         using the argument as that value

Putting it all together:

§+oṘ2ḣoṁSJoḣ←ṫ
§               Apply each of these functions to the argument:
  oṘ2ḣ            First section function
      oṁSJoḣ←ṫ    Remaining sections function
                and combine the results using this function:
 +                Concatenate lists
\$\endgroup\$
7
\$\begingroup\$

Vyxal, 16 15 bytes

₌ɾ²›↔'2l?:Ẋ⊍¬;h

Try it Online!

So remember the last time I solved an array challenge with a brute force algorithm and it timed out for anything larger that a 2x2 matrix? Well I've made an improvement! This algorithm times out for anything larger than n=3.

Explained

₌ɾ²›↔'2l?:Ẋ⊍¬;h
₌ɾ²›↔            # From the range [1, input], choose all combinations with repetition of length (input**2) + 1
     '       ;h  # And get the first combination where:
      2l         #   A list of all windows of length 2
        ?:Ẋ⊍¬    #   set xor'd with the cartesian product of the range [1, input] with itself is empty
\$\endgroup\$
7
\$\begingroup\$

Jelly, 6 bytes

Rj)F;1

A monadic Link that accepts a positive integer and yields a list of positive integers.

Try it online!

How?

Much like alephalpha's Husk answer...

Rj)F;1 - Link: integer, N
  )    - for each (n in [1..N]):
R      -   range (n)
 j     -   join with (n)
   F   - flatten
    ;1 - concatenate a one
\$\endgroup\$
4
\$\begingroup\$

Python3, 173 bytes:

lambda n:next(F({(x,y)for x in R(1,n+1)for y in R(1,n+1)}))
def F(k,c=[]):
 if not k:yield c
 for i in k:
  if[]==c or c[-1]==i[0]:yield from F(k-{i},c+[*i][c!=[]:])
R=range

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 158 bytes \$\endgroup\$ Commented Oct 17, 2022 at 3:21
  • \$\begingroup\$ Here is a gist of a call graph. \$\endgroup\$
    – Galen
    Commented Oct 19, 2022 at 0:01
4
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

-3 bytes thanks to @hakr14.

#~DeBruijnSequence~2~Append~0+1&

Try it online!

Using the built-in DeBruijnSequence.


Wolfram Language (Mathematica), 43 bytes

##~Join~{1}&@@Range@i~Riffle~i~Table~{i,#}&

Try it online!

This is OEIS A349526.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 33 bytes \$\endgroup\$
    – hakr14
    Commented Oct 17, 2022 at 4:19
4
\$\begingroup\$

Nibbles, 7.5 bytes (15 nibbles)

+.:,$1>>+.,$:@

A Nibbles port of the generator for A349526, thanks to alephalpha's Husk answer (upvote that!).

   ,$           # range 1..input
  :  1          # append 1
 .              # map each i over this:
         .,$    #   map over 1..i
            :@  #     prepend i
        +       #   flatten
      >>        #   and remove first element
+               # and flatten the list-of-lists

enter image description here

\$\endgroup\$
4
\$\begingroup\$

R, 50 bytes

f=function(x)if(x)c(1,rbind(x,x:1)[-x],f(x-1)[-1])

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 49 39 bytes

f n=n:do x<-[1..n];init$(:[x])=<<[x..n]

Try it online!

  • saved 10 Bytes thanks to @xnor
\$\endgroup\$
2
  • \$\begingroup\$ 41 bytes with do notation \$\endgroup\$
    – xnor
    Commented Oct 18, 2022 at 0:41
  • 2
    \$\begingroup\$ 39 bytes \$\endgroup\$
    – xnor
    Commented Oct 18, 2022 at 0:44
3
\$\begingroup\$

JavaScript (ES6), 47 bytes

Returns a comma-separated string.

This generates the same results as alephalpha's answer, with a recursive algorithm.

f=n=>n?1+[,(g=k=>k>1?[k,n,g(k-1)]:f(n-1))(n)]:1

Try it online!

How?

By using [1, instead of 1+[, (like that), we can see that it actually builds the following structure (here for \$n=3\$):

+------ first call to f
|   +-- first call to g
|   |
v   v
[1, [3, 3, [2, 3, [1, [2, 2, [1, 1]]]]]]
                  ^
                  |
                  +-- second call to f

The purpose of 1+[, is to force the result to be coerced to a string and implicitly flattened.

\$\endgroup\$
3
\$\begingroup\$

Rust, 84 74 bytes

-10 bytes thanks to alepalpha

use itertools::*;|n|chain((1..=n).flat_map(|m|(1..=m).intersperse(m)),[1])

Plauground

Takes a usize and returns an iterator of usizes.

\$\endgroup\$
1
2
\$\begingroup\$

Charcoal, 17 bytes

FNF⊕ι«I⊕✂⟦ικ⟧¬κ»1

Try it online! Link is to verbose version of code. Explanation: Port of @DominicvanEssen's Nibbles answer.

FN

Input n and loop i from 0 until n.

F⊕ι«

Loop k from 0 until i inclusive.

I⊕✂⟦ικ⟧¬κ

If k is 0 then just output k+1 otherwise output both i+1 and k+1.

»1

Output a trailing 1.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

LLεZ.ý}˜Ć

Port of @alephalpha's Husk answer, but reversed.

Try it online or verify the first 5 test cases.

Explanation:

L       # Push a list in the range [1, (implicit) input]
 L      # Convert each value in this list to a list in the range [1,value]
  ε     # Map over each inner list:
   Z    #  Push the list's maximum (without popping the list itself)
    .ý  #  Intersperse the list with this maximum as delimiter
  }˜    # After the map: flatten it to a single list
    Ć   # Enclose; appending its own head (which is always 1)
        # (after which the result is output implicitly)
\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 51 bytes

f=lambda n,i=1:n*[1]and f(n-i//n,i%n+1)+[n,i][i-n:]

Try it online!

This uses a similar method as alephalpha's answer, except it orders segments in reverse.

Using n=4 as an example, the list is built recursively, as a sum of segments [1,1] + [2,2,1] + [3,3,2,3,1] + [4,4,3,4,2,4,1], where the last segment is concatenated to f(n-1).

The segments are also built recursively, as [4,4]+[4,3]+[4,2]+[4,1] with the [i-n:] to slice off the beginning of the second term ([4,3] => [3]).

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 13 bytes

<~l.&⟦₁gjẋ~sᵛ

Try it online!

Explanation

<~l.            length(output) > input
    &⟦₁         Take the range [1, …, input]
       gj       Juxtapose to itself [[1, …, input], [1, …, input]]
         ẋ      Cartesian product
          ~sᵛ   Each sublist of the cartesian product is a connex sublist of the output
                (the output gets filled in with the right values to match this constraint)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.