# Construct a diverse array

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.

# 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


# 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


# 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


# 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?

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


# 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:yield from F(k-{i},c+[*i][c!=[]:])
R=range


Try it online!

• 158 bytes Oct 17, 2022 at 3:21
• Here is a gist of a call graph. Oct 19, 2022 at 0:01

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

• 33 bytes Oct 17, 2022 at 4:19

# 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 # R, 50 bytes

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


Try it online!

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


Try it online!

• saved 10 Bytes thanks to @xnor
• 41 bytes with do notation
– xnor
Oct 18, 2022 at 0:41
• 39 bytes
– xnor
Oct 18, 2022 at 0:44

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

# Rust, 84 74 bytes

-10 bytes thanks to alepalpha

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


Plauground

Takes a usize and returns an iterator of usizes.

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

# 05AB1E, 9 bytes

LLεZ.ý}˜Ć


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

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)


# Python 3, 51 bytes

f=lambda n,i=1:n*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] => ).

# 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)