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.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- 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.
- Swap a[k] with a[l].
- 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.
Ref. wiki link.
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]; } }