Advertisement
kevlinsky

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.  
Advertisement
RAW Paste Data Copied
Advertisement