Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Find next larger number which consists of all the digits of current number.
You had better to remember this algorithm:

• From right to left, find the first index1 that num[index1] > num[index1-1]; if it does not exist, it means the current number is the largest one, just reverse it
• From right to left, find the first index2 that num[index2] > num[index1-1];
• Swap num[index1-1] and num[index2];
• Reverse the array from index1 to the end of this array.

 public class Solution {  
   public void nextPermutation(int[] num) {  
     if (num == null || num.length == 0)  
       return ;  
     int index1 = 0, index2 = 0;  
     for (int i=num.length-1; i>=1; i--) {  
          if (num[i]>num[i-1]) {  
               index1=i;  
               for (int j=num.length-1; j>=index1; j--){  
                    if (num[j]>num[leftPos]) {  
                         index2 = j;  
                         int t = num[index2];  
                         num[index2] = num[index1-1];  
                         num[index1-1] = t;  
                         break;  
                    }  
               }  
               reverseArray(num, index1, num.length-1);  
               return;  
          }  
     }  
     reverseArray(num, 0, num.length-1);  
   }  
   public int[] reverseArray(int[] array, int begin, int end) {  
     if (begin >= end)  
       return array;  
     for (int i=begin, j=end; i<j; i++, j--) {  
       int t = array[i];  
       array[i] = array[j];  
       array[j] = t;  
     }  
     return array;  
   }  
 }