Weblogs

CSES Permutations

Introduction

Hello There, In this post let’s see how I tackled the Permutations problem from CSES.

Permutations is the 5th problem from CSES. I stored my solutions here. Let’s explore the solutions.

NOTE: To reduce character count shown in CSES I have used short variable names in the code.

CSES Profile

Problem Statement

Link

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.

Approach #1

We have n. So for the first approach I went on with the brute force method. That is to create all possible permutations and find whether it is a solution or not.

We use the built-in permutations function from the itertools.

For each of the permutations for [1...n], we check whether all of the numbers from the permutation didn’t contain the difference as 1 when compared to the adjacent elements.

Observations

Obviously as expected for big permutations the code didn’t stand.

For short permutations it worked. From this I learned that there should be some other way to solve this problem. I thought for a little bit and searched the internet for possible ideas.

Code

Link

 1n = int(input())
 2
 3from itertools import permutations
 4
 5perm = permutations(list(range(1, n+1)))
 6
 7for i in list(perm):
 8flag = False
 9for j in range(0, n):
10next_index = j + 1 if j != n -1 else None
11previous_index = j - 1 if j != 0 else None
12
13        diff1 = None
14        if next_index:
15            diff1 = abs(i[next_index] - i[j])
16
17        diff2 = None
18        if previous_index:
19            diff2 = abs(i[previous_index] - i[j])
20
21        if diff1 == 1 or diff2 == 1:
22            flag = True
23
24        if flag:
25            break
26
27    if not flag:
28        print(' '.join([str(k) for k in i]))
29        break
30
31    flag = False
32
33print('NO SOLUTION')

Approach #2

In the internet I found this.

From that blog I can formulate a solution for this problem. They are going with approach of the difference between 2 even or odd numbers will always be 2.

So they take all of the even numbers in the first half of the permutation solution and rest will be the odd numbers. This way we will always have difference between any 2 adjacent numbers as more than 1.

For permutations of length 2 & 3 there are no solutions to make the difference more than 1.

Observations

The code this time succeeded. The CSES max execution time was ~0.59 s. But I was not satisfied with the execution time and I wanted to reduce it. As observed here, local variables perform better than global variables in python. So I updated the code accordingly that we will see in the next approach after this approach’s code.

Code

Link

 1n = int(input())
 2
 3if n in [2, 3]:
 4print('NO SOLUTION')
 5exit()
 6
 7v = 2
 8
 9while v <= n:
10print(v, end=' ')
11v += 2
12
13v = 1
14
15while v <= n:
16print(v, end=' ')
17v += 2

Approach #3..5

As we have the working solution from Approach #2. Now it’s time to optimize.

In these approaches we converted the global variable approach to local variable approach.

Then I experimented with possible solutions for permutations for 2 & 3 lengths. Experimented with using Set, == & List for the in operation.

Also I tried to make a function for the inner while loop duplication and try to see how it affects the performance. Couldn’t see any noticeable differences.

These approaches gave ~0.52 s. But why stop. Let’s optimize further.

Observations

These approaches gave a little performance enhancement. I checked other python solution from CSES and found that my usage of print causes my program to slow down. Let’s fix this in the next approach.

Code

Link #3 Link #4 Link #5

 1
 2# 3
 3
 4def a():
 5n = int(input())
 6
 7    if n in {2, 3}:
 8        print('NO SOLUTION')
 9        exit()
10
11    def b(v):
12        while v <= n:
13            print(v, end=' ')
14            v += 2
15    b(2)
16    b(1)
17
18a()
19
20# 4
21
22def a():
23n = int(input())
24
25    if n == 2 or n == 3:
26        print('NO SOLUTION')
27        exit()
28
29    v = 2
30    while v <= n:
31        print(v, end=' ')
32        v += 2
33
34    v = 1
35    while v <= n:
36        print(v, end=' ')
37        v += 2
38
39a()
40
41# 5
42
43def a():
44n = int(input())
45
46    if n in {2, 3}:
47        print('NO SOLUTION')
48        exit()
49
50    v = 2
51    while v <= n:
52        print(v, end=' ')
53        v += 2
54
55    v = 1
56    while v <= n:
57        print(v, end=' ')
58        v += 2
59
60a()

Approach #6 and their friends

In this approach instead of printing out the value each time we are storing it in an array and print it after all the loop ends.

This gave a very significant performance boost.

Observations

This approach ran at ~0.34 s. This is a major performance enhancement. Converting the duplicated while into a function made the runtime as ~0.36 s, a little slow.

Code

Link #6 Link #6-1 Link #6-2

 1
 2# 6
 3
 4def a():
 5n = int(input())
 6
 7    if n == 1:
 8        print('1')
 9    if n in {2, 3}:
10        print('NO SOLUTION')
11    else:
12        r = []
13        v = 2
14        while v <= n:
15            r.append(v)
16            v += 2
17
18        v = 1
19        while v <= n:
20            r.append(v)
21            v += 2
22
23        print(' '.join(map(str, r)))
24
25a()
26
27# 6-with-str-called-at-append
28
29def a():
30n = int(input())
31
32    if n == 1:
33        print('1')
34    if n in {2, 3}:
35        print('NO SOLUTION')
36    else:
37        r = []
38        v = 2
39        while v <= n:
40            r.append(str(v))
41            v += 2
42
43        v = 1
44        while v <= n:
45            r.append(str(v))
46            v += 2
47
48        print(' '.join(r))
49
50a()
51
52# 6-with-function-little-slow
53
54def a():
55n = int(input())
56
57    if n == 1:
58        print('1')
59    if n in {2, 3}:
60        print('NO SOLUTION')
61    else:
62        r = []
63
64        def b(v):
65            while v <= n:
66                r.append(v)
67                v += 2
68
69            while v <= n:
70                r.append(v)
71                v += 2
72
73        b(2)
74        b(1)
75        print(' '.join(map(str, r)))
76
77a()

Conclusion

In conclusion from this problem,

#problem-solving #python #cses