package com.fishercoder.solutions;

public class _31 {
  public static class Solution1 {
    /**
     * Leetcode has a very good article to illustrate this problem and with animation:
     * https://leetcode.com/articles/next-permutation/
     * 1. if the array is already in decrementing order, then there's no next larger permutation possible.
     * 2. if not, start from the end of the array, find the first pair of numbers that break the decrementing order
     * 3. then from that index going to the right again, find the element that is closest bigger than this number, swap them
     * 4. reverse the right half of this array after this index
     */

    public void nextPermutation(int[] nums) {
      int i = nums.length - 2;
      while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
      }
      if (i >= 0) {
        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
          j--;
        }

        swap(nums, i, j);
      }

      reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
      int end = nums.length - 1;
      while (start <= end) {
        int tmp = nums[start];
        nums[start++] = nums[end];
        nums[end--] = tmp;
      }
    }

    private void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
    }
  }
}

@@ -48,16 +48,18 @@
 s _31 %7B%0A
+  
   public
@@ -92,12 +92,20 @@
     
-/**%0A
+    /**%0A    
     
@@ -192,16 +192,20 @@
 n:%0A     
+   
+ 
 * https:
@@ -246,16 +246,20 @@
 tation/%0A
+    
      * 1
@@ -362,16 +362,20 @@
 e.%0A     
+  
+  
 * 2. if 
@@ -477,16 +477,20 @@
 g order%0A
+    
      * 3
@@ -611,16 +611,20 @@
 em%0A     
+    
 * 4. rev
@@ -683,12 +683,20 @@
     
-*/%0A%0A
+    */%0A%0A    
     
@@ -739,24 +739,30 @@
 ms) %7B%0A      
+ 
+     
 int i = nums
@@ -774,16 +774,22 @@
 th - 2;%0A
+      
       wh
@@ -837,16 +837,24 @@
         
+  
+      
 i--;%0A   
@@ -860,16 +860,22 @@
     
+ 
+     
 %7D%0A      
 if (
@@ -870,16 +870,22 @@
 %7D%0A      
+ 
+     
 if (i %3E=
@@ -886,24 +886,32 @@
  (i %3E= 0) %7B%0A
+        
         int 
@@ -927,24 +927,32 @@
 length - 1;%0A
+        
         whil
@@ -1000,21 +1000,38 @@
     
-j--;%0A
+          j--;%0A       
         
 %7D%0A%0A 
@@ -1022,27 +1022,36 @@
             
+ 
 %7D%0A%0A
+        
         swap
@@ -1066,27 +1066,39 @@
 , j);%0A      
+    
+  
 %7D%0A%0A
+      
       revers
@@ -1113,16 +1113,20 @@
 i + 1);%0A
+    
     %7D%0A%0A 
@@ -1120,32 +1120,36 @@
 %0A        %7D%0A%0A    
+ 
+   
 private void rev
@@ -1174,24 +1174,30 @@
 nt start) %7B%0A
+      
       int en
@@ -1219,24 +1219,30 @@
  - 1;%0A      
+    
+  
 while (start
@@ -1256,24 +1256,32 @@
 ) %7B%0A        
+     
+   
 int tmp = nu
@@ -1295,24 +1295,32 @@
 t%5D;%0A        
+   
+     
 nums%5Bstart++
@@ -1334,16 +1334,24 @@
 s%5Bend%5D;%0A
+        
         
@@ -1365,24 +1365,30 @@
 d--%5D = tmp;%0A
+      
       %7D%0A    
@@ -1387,23 +1387,31 @@
   %7D%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A   
     
+ 
 private 
@@ -1444,24 +1444,30 @@
 i, int j) %7B%0A
+      
       int tm
@@ -1479,16 +1479,22 @@
 ums%5Bi%5D;%0A
+      
       nu
@@ -1510,16 +1510,22 @@
 ums%5Bj%5D;%0A
+      
       nu
@@ -1541,16 +1541,22 @@
 mp;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 31