Untitled

Dec 16th, 2021
851
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def find_pos(arr):
2.     pos = None
3.     for i in range(len(arr) - 1):
4.         if arr[i] > arr[i + 1]:
5.             pos = i
6.     return pos
7.
8.
9. def find_max_lower_idx(pos):
10.     max_lower = 0
11.     for idx in range(pos + 1, len(arr)):
12.         if max_lower < arr[idx] < arr[pos]:
13.             max_lower = idx
14.     return max_lower
15.
16.
17. def swap(pos_1, pos_2, arr):
18.     x = arr[pos_1]
19.     arr[pos_1] = arr[pos_2]
20.     arr[pos_2] = x
21.
22.
23. def get_previous_permutation(arr):
24.     pos = find_pos(arr)
25.     if pos is None:
26.         return sorted(arr, reverse=True)
27.     max_lower = find_max_lower_idx(pos)
28.     swap(pos, max_lower, arr)
29.     return arr[:pos + 1] + sorted(arr[pos + 1:], reverse=True)
30.
31.
32.
33. if __name__ == '__main__':
34.     arr = [1, 3, 2, 5, 4]
35.     print(f'Got - {arr}')
36.     print(f'Previous permutation - {get_previous_permutation(arr)}')
37.