## Problem:

Generate the next permutation of the current array.

## Solution:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

## Source Code:

```/**
*
*/

/**
* @author antonio081014
* @time: Oct 27, 2012, 10:13:11 AM
*/
public class Solution {

/**
* @param args
*/
public static void main(String[] args) {
Solution main = new Solution();
int[] array = { 1, 2, 3, 4, 5 };
main.print(array);
main.next_permutation(array);
main.print(array);
main.next_permutation(array);
main.print(array);
main.next_permutation(array);
main.print(array);
System.exit(0);
}

public void print(int[] array) {
for (int tmp : array) {
System.out.print(" " + tmp);
}
System.out.println();
}

public void next_permutation(int[] array) {
int i, j;
// Find the largest index k such that a[k] < a[k + 1]. If no such index
// exists, the permutation is the last permutation.
for (i = array.length - 2; i >= 0; i--) {
if (array[i] < array[i + 1])
break;
}
if (i < 0) {
System.out.println("End");
return;
}

// Find the largest index l such that a[k] < a[l]. Since k + 1 is such
// an index, l is well defined and satisfies k < l.
for (j = array.length - 1; j > i; j--) {
if (array[j] > array[i])
break;
}

// Swap a[k] with a[l].
swap(array, i++, j);

// Reverse the sequence from a[k + 1] up to and including the final
// element a[n].
for (j = array.length - 1; j > i; i++, j--) {
swap(array, i, j);
}
}

public void swap(int[] array, int x, int y) {
array[x] ^= array[y];
array[y] ^= array[x];
array[x] ^= array[y];
}
}
```