Link to the problem : Permutations

Intuition

The idea is to generate a permutation of the numbers from 1 to n such that the difference between any two consecutive elements is at least greater than 1.

One way to do this is to first write all the even numbers between 1 and n in increasing order and then write all the odd numbers between 1 and n in increasing order.

This is only one such solution. There are other solutions as well.

Edge case:

• If n is 1, print 1. this is because there are no consecutive elements in the permutation, hence is a valid permutation.
• If n is less than 4, print “NO SOLUTION”. because for n < 4, any permutation will have a difference between any two consecutive elements less than 1. example 1 2 3 4, 1 3 2 4, 1 3 4 2, etc are not valid permutations.

Solution

 1def main():
 2    n = int(input())
 3    if n == 1:
 4        print(1)
 5        return
 6    if n < 4:
 7        print("NO SOLUTION")
 8        return
 9    for i in range(2,n+1,2):
10        print(i, end=" ")
11    for i in range(1,n+1,2):
12        print(i, end=" ")
13
14if __name__ == "__main__":
15    main()

Other possible solutions

• Write all the odd numbers between 1 and n in increasing order and then write all the even numbers between 1 and n in increasing order.
• Write all the odd numbers between 1 and n in decreasing order and then write all the even numbers between 1 and n in decreasing order.
• Write all the even numbers between 1 and n in increasing order and then write all the odd numbers between 1 and n in decreasing order.