Learning Algorithms Recipes: Next permutation sequence
Input: sequence of numbers as an array e.g. 140213
Output: next minimun number greater than input that can be generated using the numbers in array 140231
Algorithm
- Find LARGEST i starting from len(arr)-1 where arr[i-1] >= arr[i]
i = 5 arr = [1, 4, 0, 2 ,1, 3] 1 does not satisfies condition => break loop
result: i = 5
if i <= 0 then "there is no way to generate another permutation"
- Find LARGEST j starting from len(arr)-1 where j>=i && arr[j] <= arr[i-1]
j = 5 arr = [1, 4, 0, 2 ,1, 3] satisfies condition
j = 4 arr = [1, 4, 0, 2 ,1, 3] satisfies condition j break loop
...
result: j = 5
- Swap arr[i-1] and arr[j]
result: arr = [1, 0, 4, 2 ,3, 1]
- Reverse array starting from i
j = 5 => we need to reverse [1]
result: arr = [1, 4, 0, 2, 3, 1]
def biggerIsGreater(w):
if len(w) == 0:
return 'no answer'
s_w = list(w)
i = len(s_w) - 1
while i > 0 and s_w[i-1] >= s_w[i]:
i -= 1
if i <= 0:
return 'no answer'
j = len(s_w) - 1
while s_w[j] <= s_w[i-1]:
j -= 1
s_w[j], s_w[i-1] = s_w[i-1], s_w[j]
s_w[i : ] = s_w[len(s_w) - 1 : i - 1 : -1]
return ''.join(s_w)