An algorithm for generating a permutation of N numbers ranging from 1 to N with the maximum of smallest neighbouring differences

Question

I encountered this question in a programming contest (New Zealand Informatics Competition 2024, unfortunately no link to the question is available). I was asked to write a program which generates a permutation of $N$ numbers ranging from 1 to $N$. For any permutation we can calculate the differences (absolute value of any two neighbouring numbers in the permutation) of every two neighbouring numbers and we want to output a permutation whose smallest difference among all neighbouring numbers is maximised. For example, for $N$ = 4 and a permutation "1324", the values of differences between all 3 pairs of neighbouring numbers (13, 32, 24) are 2, 1, 2 respectively. So the smallest value among all the differences (2,1,2) is 1. For $N$ = 4, the output is 2413 which has a smallest neighbouring difference of 2. The permutation 2413 is better than 1342 or 1324 since each has a smallest neighbouring difference of 1 (Note "34" in 1342 and "32" in 1324). The program should output a permutation which is lexicographically better (smaller numbers first) than another permutation if both have the same maximum smallest neighbouring differences. Some special cases are as follows.

$N = 1$, output 1;

$N = 2$, output 12; (not 21 since 12 is lexicographically better.)

$N = 3$, output 123; (not 132 or 321 or any other permutations.)

$N =4 $, output 2413;

It seems to be that it is easier if $N$ is even. I had a vague idea that I'll generate the first number as half of $N$. Then I'll do addition and subtraction one by one to generate the following numbers.

I'm curious whether the maximum of smallest neighbouring differences for all permutations regardless of $N$ is no greater than 3. Or is there any maths behind this question?

Answer 1

No its $\left\lfloor \frac{n}{2} \right\rfloor$ for any $n$.

Here is the link of the problem you are talking about (without the lexicographical smallest condition), with here its solution. Taking the words directly from it:

Let's prove that the minimum difference of consecutive elements is not greater than $\left\lfloor \frac{n}{2} \right\rfloor$. To do it, let's prove that larger value is not achievable. Consider element of a permutation with value $\left\lfloor \frac{n}{2} \right\rfloor + 1$. It will have at least one adjacent element in the constructed permutation. And the maximum absolute difference of this element with the adjacent elements is at most $\left\lfloor \frac{n}{2} \right\rfloor$.

Now we will construct the permutation with the minimum absolute difference of consecutive elements equals to $\left\lfloor \frac{n}{2} \right\rfloor$. Assign $x = \left\lfloor \frac{n}{2}\right\rfloor + 1$. Now we can construct such permutation: $x, 1, x+1, 2, x+2, \dots$. It's easy to see that the minimum absolute difference of consecutive elements equals to $x−1$.

Here is a submission I made for the problem which is working.

---

The only part remaining is to consider the lexicographical smallest condition of your problem. To do that, I try different cases of setting up this permutation, starting from the most optimal ones, and moving to more un-optimal ones as I face a dead-end (providing arguments why we can't move further).

The two things I keep in mind while building these: (1) We can't repeat any number in the permutation, and (2) difference between any two adjacent numbers $\ge x-1$. I'll color the number places as $\color{green}{\text{green}}$ when I'm making a choice between multiple possibilities, $\color{blue}{\text{blue}}$ when I'm forced to place this exact number, and $\color{red}{\text{red}}$ when I know this possibility will face a dead-end.

For odd $n \implies [1, 2, \dots x, x+1, \dots 2x-1]$

• $\color{green} 1$
  • $1, \color{green} x$
  • $1, x, \color{blue} {2x-1}$
    • $1, x, 2x-1, \color{green} {2}$
      • $1, x, 2x-1, 2, \color{red} {x+1}$
        • Now we can't place any $y$ after this, which is not already used, where $|x+1-y| \ge x-1$. So we move to the other scenarios.
      • $1, x, 2x-1, 2, \color{red} {x+2 \text{ or } x+3 \text{ or } \dots 2x-2}$
        • As $x+1$ can only be adjacent to $1$ or $2$, both of which are already used up in this case, we won't be able to place $x+1$ any time in the future of this case.
    • $1, x, 2x-1, \color{red} {3 \text{ or } 4 \text { or } \dots x-2}$
      • As $x+1$ can only be adjacent to $1$ or $2$, and $1$ is already used, $x+1$ can only be at the right end of the permutation in this case (besides $2$). A similar argument can be made for $x-1$, which can be only adjacent to $2x-1$ or $2x-2$. As both $x-1$ and $x+1$ cannot be simlutaneously at the right end of the permutation, this case will also fail.
  • $1, x, 2x-1, \color{blue}{x-1}$
  • $1, x, 2x-1, x-1, \color{blue}{2x-2}$
    • $1, x, 2x-1, x-1, 2x-2, \color{red}{2}$
      • Same argument as above
    • $1, x, 2x-1, x-1, 2x-2, \color{red}{3 \text{ or } 4 \text { or } \dots x-3}$
      • Same argument as above, but with $x+1$ and $x-2$ (instead of $x+1$ and $x-1$)
  • $1, x, 2x-1, x-1, 2x-2, \color{blue}{x-2}$
  • $\dots$
  • $1, x, 2x-1, x-1, 2x-2, x-2, \dots x+3, \color{blue}{3}$
  • $1, x, 2x-1, x-1, 2x-2, x-2, \dots x+3, 3, \color{blue}{x+2}$
  • $1, x, 2x-1, x-1, 2x-2, x-2, \dots x+3, 3, x+2, \color{blue}{2}$
  • $1, x, 2x-1, x-1, 2x-2, x-2, \dots x+3, 3, x+2, 2, \color{blue}{x+1}$

For even $n \implies [1, 2, \dots x, x+1, \dots 2x-2]$

Here $x-1$ can only be adjacent to $2x-2$ and $x$ can only be adjacent to $1$, so both of these have to be at either of the ends.

• $\color{green}{x-1}$
• $x-1, \color{blue}{2x-2}$
  • $x-1, 2x-2, \color{red}{1 \text{ or } 2 \text{ or } \dots x-3}$
    • We shift the argument from $x-1$ to $x-2$, i.e., $x-2$ can only be adjcent to $2x-2$ or $2x-3$. But as $2x-2$ is used up in this case, $x-2$ has to be at the right end, but we already have $x$ there.
• $x-1, 2x-2, \color{blue}{x-2}$
• $x-1, 2x-2, x-2, \color{blue}{2x-3}$
• $\dots$
• $x-1, 2x-2, x-2, 2x-3, \dots \color{blue}{3}$
• $x-1, 2x-2, x-2, 2x-3, \dots 3, \color{blue}{x+2}$
  • $x-1, 2x-2, x-2, 2x-3, \dots 3, x+2, \color{red}{1}$
    • Shifting the argument from $3$ to $2$, i.e., $2$ can only be adjacent to $x+1, x+2 \dots 2x-2$. But as $x+2, x+3 \dots 2x-2$ are already used in the permutation, $2$ has to be at the right end, which conflicts with $x$ being at the right end.
• $x-1, 2x-2, x-2, 2x-3, \dots 3, x+2, \color{blue}{2}$
• $x-1, 2x-2, x-2, 2x-3, \dots 3, x+2, 2, \color{blue}{x+1}$
• $x-1, 2x-2, x-2, 2x-3, \dots 3, x+2, 2, x+1, \color{blue}{1}$
• $x-1, 2x-2, x-2, 2x-3, \dots 3, x+2, 2, x+1, 1, \color{blue}{x}$