[Permutation] Next Permutation

1. Example

Rearrange number into the lexicographically next greater permutation of numbers
e.g., 1,2,3 -> 1,3,2
e.g., 1,1,5 -> 1,5,1
e.g., 1,2->2,1
If such arrangement is not possible, it must rearrange it as the lowest possible order(i.e., sorted in ascending order)
e.g., 3,2,1-> 1,2,3
e.g., 2,7, 6,3    ,5,4,1 -> 2,7,6,   4   1,3,5

2. Implementation
Not possible case: number is in ascending order from backward, the solution is reverse it
e.g., 3,2,1
Possible case: number is not in ascending order from backward, the solution is record the one where first non ascending occur.
e.g., 1,2,3 -> first non ascending occur is in length-2
e.g., 1,1,5 -> first non ascending occur is in length-2
Q1: what to do after find out non-ascending index?
A1: find the least greater number to replace it
Q1: After replacing, your number become greater but is that the next smallest?
A1: Not yet. there is one part you can still optimize -  Reverse the backward ascending part into forward ascending one.

Input:[1,3,2]
Output:[3,2,1]
Expected:[2,1,3]

Input:[1,2,3]
Output:[3,2,1]



Expected:[1,3,2]
Runtime Error Message:Line 124: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:[1]
int nonAscendingIndex = nums.length -2;

while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] ) { 

          nonAscendingIndex--; 

}

int leastGreaterIndex = nonAscendingIndex+1;

int leastGreaterIndex = nonAscendingIndex+1;

while( leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] ) 

{ 

          leastGreaterIndex++; 

} 

leastGreaterIndex--;

// Time:O(n), Space:O(1)
//Runtime Error Message:
//Line 139: java.lang.ArrayIndexOutOfBoundsException: -1
//Last executed input:
//[1,2]
// Input:
//[1,2]
//Output:
//[1,2]
//Expected:
//[2,1]
public void nextPermutation(int[] nums)
{


      // validate the input
      if ( nums == null || nums.length == 0 )
      {
           return;
      }

     



      // NOTE :start from back
      int nonAscendingIndex = nums.length -2;
      while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] )
      {
          nonAscendingIndex--;
      }





      // NOTE: case all backward ascending will both end up i = -1
      if ( nonAscendingIndex >= 0 )
      {
          // [1,2,3] -> [1,3,2] not [3,1,2]
          int leastGreaterIndex = nonAscendingIndex+1;
          while(  leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] )
          {
               leastGreaterIndex++;
          }
          leastGreaterIndex--;
          swap(nums, nonAscendingIndex,leastGreaterIndex);
      }
 
      
      // case1: backward in descending case
      // case2: only one element
      // case3: regular case, after swap
      reverse(nums,i+1, num.length-1);
}

public void swap(int[] nums, int l, int r)
{
      //validate the input
      if ( nums == null || nums.length ==0 )
      {
         return;
      }


      int temp = nums[l];
      nums[l] = nums[r];
      nums[r] = temp;
}

public void reverse (int[] nums, int start , int end)
{

       // validate the input
       if (nums == null || nums.length ==0 )
       { 
           return;
       }


       int l = start;
       int r = end;
       while (l < r)
       {
             int temp = nums[l];
             nums[l] = nums[r];
             nums[r] = temp;
             l++;
             r--;
       }
}

3. Similar Ones (M) Permutations (H) Permutations II (M) Permutation Sequence (M) Palindrome Permutation II