CA 12 - Next Permutation

Problem Statement: here PS Understanding: We have to find the arrangement of numbers that is immediately bigger than the current one. Solution: def nextPermutation ( nums ): n = len ( nums ) i = n - 2 while i >= 0 and nums [ i ] >= nums [ i + 1 ]: i -= 1 if i >= 0 : j = n - 1 while nums [ j ] <= nums [ i ]: j -= 1 nums [ i ], nums [ j ] = nums [ j ], nums [ i ] left , right = i + 1 , n - 1 while left < right : nums [ left ], nums [ right ] = nums [ right ], nums [ left ] left += 1 right -= 1 We have numbers like: [1, 2, 3] and we want to make the next bigger arrangement using the same numbers. Example: 123 → next is 132 132 → next is 213 213 → next is 231 1. Start from the right end and check if the number before is less than it. eg. in [1,2,3] find where left < right 2 < 3 → this is the spot So mark index of 2 2. Find a slightly bigger number on the right Now look to the right of 2: [3] Find a number just bigger than 2 → that is 3. 3. Swap them Swap 2 and 3 [1, 3, 2] 4. Fix the right