Problem Link: https://cses.fi/problemset/task/3175

Problem Statement: Generate a permutation of numbers from 1 to n such that absolute difference between any two adjacent numbers is not equal to 1. We need to generate the lexicographically smallest such permutation.

Solution:

Idea#1 : Greedily generate the permutation by choosing the smallest available number whose difference with previous number is not 1.

Why this won't work?: Consider the example n = 8

we choose 1 in first iteration, so perm = [1]

we can't choose 2 in second iteration, so we choose 3, so perm = [1, 3]

we can't choose either 2 or 4 in third iteration so we choose 5, so perm = [1, 3, 5]

we can't choose either 3 or 4 in fourth iteration so we choose 2, so perm = [1, 3, 5, 2]

we can't choose either 1 or 3 in the fifth iteration so we choose 4, so perm = [1,3, 5, 2, 4]

Now we have exhausted all the numbers from 1-5, we are only left with 6, 7, 8. However any arrangement of 3 consecutive numbers produces an adjacent difference 1.

Improvising the idea:

Consider the following idea: Generate the first n-i elements greedily using the method described above and for the last i elements brute force over all possible i! permutations and choose the lexicographic smallest permutation that satisfies the following two conditions: 1. the i-length permutation in the end must be valid. 2. the first element in the i-length permutation and the last element in the n-i length permutation must not differ by 1.

How small can i be? Does i = 2. work? No, because we might generate n-2 elements greedily and end up with two elements of the form x, x+1 which cannot be arranged in the two left over slots.

Does i = 3, No. Because we might end up with x, x+1, x+2 type elements which cannot be arranged in 3 slots.

Does i = 4 work? Let us suppose we ended up with a1, a2, a3, a4 such that a1 < a2 < a3 < a4 then since a3-a1 >= 2 and a4-a2 >= 2, we have that [a2, a4, a1, a3] and [a3, a1, a4, a2] are valid permutations. However, since the last element in the n-i greedily generated elements can still have a difference of 1 with both a3 and a2. Thus i = 4 might not be sufficient.

Does i = 5 work? Yes, because if we have five elements a1, a2, a3, a4, a5 (with a1 < a2 < a3 < a4 < a5) we can make a valid permutation starting with a2, or staring with a3 or starting with a4 and since the last element in n-i length permutation can be adjacent with utmost 2 numbers, it follows that i = 5 always works.

Algorithm Summary:

1. For i = 1 to n-5 choose the entry greedily, we can do this by maintaining a stack = [1, 2, 3, ... n] and choosing the least number that is not adjacent to the last number choosen.

2. After we finish the above procedure we are left with 5 elements in the stack. We generate all the 5! permutations of those elements, and pick the smallest permutation (lexically) that satisfies the following two conditions

a. The permutation must not have an adjacent difference 1 b. The first element of the permutation must not have a difference 1 with the last element of the n-5 size list.

Final Note: I realized that i = 4 also works. But the proof for the same is a bit difficult (more cases) but proving i = 5 is easy.