Beginner python solution to CSES "Permutations"

Question

I'm working through the CSES problem set as I learn to program, and this solution was accepted, but I'm not quite happy with it. I just know there's a faster way to check whether or not a solution's valid instead of looping through every element, and I'm sure there're plenty more improvements that could be made. Any feedback is appreciated!

Problem: A permutation of integers 1,2,...,n is called beautiful if there are no adjacent elements whose difference is 1. Given n, construct a beautiful permutation if such a permutation exists. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

def check_solution(sol):
 last = sol[0]
 for num in sol:
 if num - last == 1 or num - last == -1:
 return False
 last = num
 return True
a = [int(x) for x in range(1, int(input())+1)]
b = []
even = a[1::2]
odd = a[::2]
b.extend(even)
b.extend(odd)
if check_solution(b):
 print(*b)
else:
 print("NO SOLUTION")

• vnp: Please add a problem statement.

Answer 1

Your list slicing idea is a good one. You could simplify further by doing something analogous with ranges, eliminating most of the need for intermediate variables

def beautiful_permutation(n):
 odd = list(range(1, n + 1, 2))
 even = list(range(2, n + 1, 2))
 return even + odd

Your validator probably should check more things and can also be simplified by taking advantage of abs(). Optionally, you could express the adjacent-number check using all() and zip(). We're still looping over the numbers, but just more concisely.

def check_solution(n, sol):
 return (
 # Must not be empty.
 sol and
 # Must cover all intergers 1 through N.
 set(range(1, n + 1)) == set(sol) and
 # No adjacent numbers with difference of 1.
 all(abs(a - b) != 1 for a, b in zip(sol, sol[1:]))
 )

One additional point. The method used to create the sequence nearly ensures validity. By definition, the individual sub-lists (odd and even) will follow the adjacent-number rule. The only way there can be a problem is at the junction point where we glue them together. But our function could directly validate the issue. If you were to add this and include a preliminary check for bad or special inputs (0, 1, etc.), you would have a function that, at least for practical purposes, is provably correct -- no need for a validator!?!

if odd and even and abs(even[-1] - odd[0]) != 1:
 return even + odd
else:
 return None

• Kelly Bundy: I think your "provably correct" solution is wrong for n=1.
• FMc: @KellyBundy Seems like a definitional case. Either way, OP can sort it out.
• t.y.ler: Super helpful ideas! I've been trying to get these problems done without referencing too much online, and given my lack of experience, that unfortunately will usually lead to an unnecessary function or two.