[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](https://en.wikipedia.org/wiki/De_Bruijn_sequence) of order \$ n \$.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins.
  
[Answer]
# [Husk](https://github.com/barbuz/Husk), 7 bytes
```
:1ṁSJṫṫ
```
[Try it online!](https://tio.run/##yygtzv7/38rw4c7GYK@HO1cD0f///00B "Husk – Try It Online")
This is OEIS [A349526](https://oeis.org/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]
# [Husk](https://github.com/barbuz/Husk), 14 bytes
```
§+oṘ2ḣoṁSJoḣ←ṫ
```
[Try it online!](https://tio.run/##yygtzv7//9By7fyHO2cYPdyxGEg3BnvlA1mP2iY83Ln6////pgA "Husk – Try It Online")
### How?
First, observe that this challenge is equivalent to the following:
* Create a [complete digraph](https://en.wikipedia.org/wiki/Complete_graph) 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](https://codegolf.stackexchange.com/questions/188988/ddoouubbllee-ssppeeaakk/189056#comment522032_189056) 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]
# [Vyxal](https://github.com/Vyxal/Vyxal), ~~16~~ 15 bytes
```
₌ɾ²›↔'2l?:Ẋ⊍¬;h
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJUIiwiIiwi4oKMyb7CsuKAuuKGlCcybD864bqK4oqNwqw7aCIsIiIsIjIiXQ==)
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]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Rj)F;1
```
A monadic Link that accepts a positive integer and yields a list of positive integers.
**[Try it online!](https://tio.run/##y0rNyan8/z8oS9PN2vD////GAA "Jelly – Try It Online")**
### How?
Much like alephalpha's [Husk answer](https://codegolf.stackexchange.com/a/253324/53748)...
```
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]
# 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!](https://tio.run/##TY2xDoIwEIZneYpza6Ukogtp0pUHYK0dsFC9AIU0DDSEZ6@FGON29/33fzf5@T3aezG5YMQj9PXwbGqw3LbLTEqykoV5akYHC6CFiuTMpvkB/D/YKE2a1kBJOqaFVJQngAbsOEPHPbZ9AzqBvYZ7rYtxzKUSQkOEWmZ5nFFe1ffauHHYbdmKG9OpvKCS@hzNXNGkEq62rzb8fMdKbqyIf0@TQzsTQ5DS8AE)
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 32 bytes
-3 bytes thanks to [@hakr14](https://codegolf.stackexchange.com/users/78186/hakr14).
```
#~DeBruijnSequence~2~Append~0+1&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@1@5ziXVqag0MysvOLWwNDUvObXOqM6xoCA1L6XOQNtQ7b9LfnRAUWZeSXSegq6dQlp0XmysjkJ1no6CIRAZ1Mb@BwA "Wolfram Language (Mathematica) – Try It Online")
Using the built-in [`DeBruijnSequence`](http://reference.wolfram.com/language/ref/DeBruijnSequence.html).
---
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 43 bytes
```
##~Join~{1}&@@Range@i~Riffle~i~Table~{i,#}&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@19Zuc4rPzOvrtqwVs3BISgxLz3VIbMuKDMtLSe1LrMuJDEJSFdn6ijXqv13yY8OKMrMK4nOU9C1U0iLzouN1VGoztNRMAQig9rY/wA "Wolfram Language (Mathematica) – Try It Online")
This is OEIS [A349526](https://oeis.org/A349526).
[Answer]
# [Nibbles](http://golfscript.com/nibbles/index.html), 7.5 bytes (15 nibbles)
```
+.:,$1>>+.,$:@
```
A [Nibbles](http://golfscript.com/nibbles/index.html) port of the generator for [A349526](https://oeis.org/A349526), thanks to [alephalpha's Husk answer](https://codegolf.stackexchange.com/a/253324/95126) (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](https://i.stack.imgur.com/Dx6xs.png)](https://i.stack.imgur.com/Dx6xs.png)
[Answer]
# [R](https://www.r-project.org/), 50 bytes
```
f=function(x)if(x)c(1,rbind(x,x:1)[-x],f(x-1)[-1])
```
[Try it online!](https://tio.run/##K/qfklmWWlScmlhUlFhp@z/NNq00L7kkMz9Po0IzMw1IJGsY6hQlZealaFToVFgZakbrVsTqACV0QUzDWE0UAzSMNf8DAA "R – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), ~~49~~ 39 bytes
```
f n=n:do x<-[1..n];init$(:[x])=<<[x..n]
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P00hzzbPKiVfocJGN9pQTy8v1jozL7NERcMquiJW09bGJroCJPg/NzEzT8FWITexwDdeQaOgKDOvRC9NUwGkxSz2PwA "Haskell – Try It Online")
* saved 10 Bytes thanks to @xnor
[Answer]
# JavaScript (ES6), 47 bytes
Returns a comma-separated string.
This generates the same results as [alephalpha's answer](https://codegolf.stackexchange.com/a/253324/58563), 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!](https://tio.run/##ZchNCoAgEEDhfSeZIQ3sbxFoB5EWYSpljFHR9a1tuHqPb5uf@TLnetyc4mJTcpKkolGUmoGXQaqgxKgDI@YhcIHT4IC@ItD3IplIV9xttUcPDmrE4i9NJm0mXSY9YnoB "JavaScript (Node.js) – Try It Online")
### How?
By using `[1,` instead of `1+[,` ([like that](https://tio.run/##DcyxDsIgFEDRvV/xxkdKm@DgYIXuDjo4Ng5NBYKQRwPExBi/HZnOne5rfa95S24vA8WnrtVIkormRXC00kvllZgXz4lb9INgj5NBajKk1qKamDDoAgQSDlPjLOHY7HsG3w5gi5Rj0GOIFi/323XMJTmyznywjRhjU/erfw)), 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]
# Rust, ~~84~~ 74 bytes
-10 bytes thanks to [alepalpha](https://codegolf.stackexchange.com/users/9288/alephalpha)
```
use itertools::*;|n|chain((1..=n).flat_map(|m|(1..=m).intersperse(m)),[1])
```
[Plauground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f25108422ba6282e2fd9611ad2dca433)
Takes a `usize` and returns an iterator of usizes.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 17 bytes
```
ＦＮＦ⊕ι«Ｉ⊕✂⟦ικ⟧¬κ»1
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z8tv0hBwzOvoLTErzQ3KbVIQ1NTASqWXJSam5pXkpqikQkUrFYIKMrMK9FwTiwuQZEMzslMTtWIztRRyI7VUfDLL9HI1gQBa4VaLogWJUMlTev//03/65blAAA "Charcoal – 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]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 9 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
LLεZ.ý}˜Ć
```
Port of [*@alephalpha*'s Husk answer](https://codegolf.stackexchange.com/a/253324/52210), but reversed.
[Try it online](https://tio.run/##yy9OTMpM/f/fx@fc1ii9w3trT8850vb/vzEA) or [verify the first 5 test cases](https://tio.run/##yy9OTMpM/W/q6mevpPCobZKCkr3ffx@fc1uj9A7vrT0950jbf53/AA).
**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]
# [Python 3](https://docs.python.org/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!](https://tio.run/##DcixCoAgFEbhvae4S6BlhDQEgk8iDkZZF@pPxKWnN8/0cdJXrhdLrdHe4dn2QFBstcHgtA/YKQpMPM/t9hi1HF2TdzzB@BrfTEwMygHnIbSiVZqOWikzioiCpaw/ "Python 3 – Try It Online")
This uses a similar method as [alephalpha's answer](https://codegolf.stackexchange.com/a/253324/95116), 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]
# [Brachylog](https://github.com/JCumin/Brachylog), 13 bytes
```
<~l.&⟦₁gjẋ~sᵛ
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r/36YuR0/t0fxlj5oa07Me7uquK364dfb//8b/owA "Brachylog – 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)
```
]