Construct a diverse array

Question

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 code-golf, so the shortest code in bytes wins.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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!

Answer 6

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.

Answer 7

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

Answer 8

R, 50 bytes

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

Try it online!

Answer 9

Haskell, 49 39 bytes

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

Try it online!

• saved 10 Bytes thanks to @xnor

Answer 10

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.

Answer 11

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.

Answer 12

Charcoal, 17 bytes

ＦＮＦ⊕ι«Ｉ⊕✂⟦ικ⟧¬κ»1

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

ＦＮ

Input n and loop i from 0 until n.

Ｆ⊕ι«

Loop k from 0 until i inclusive.

Ｉ⊕✂⟦ικ⟧¬κ

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

»1

Output a trailing 1.

Answer 13

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)

Answer 14

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

Answer 15

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)