Next Permutation
Generation in lexicographic order
I can not work out this without Google's help.
steps below are copied from Wikipedia:
- 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 greater than k such that a[k] < a[l].
- Swap the value of a[k] with that of a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
Fisherlei's Image is a good illustration. You can see an image that how this solution goes.
Source code Read on Github
1 public class Solution {
2 // http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
3 void swap(int x[], int a, int b) {
4 int t = x[a];
5 x[a] = x[b];
6 x[b] = t;
7 }
8
9 public void nextPermutation(int[] num) {
10
11 if(num.length < 2) return;
12
13 int p = -1;
14
15 for(int i = num.length - 1; i >0; i--){
16 if(num[i] > num[i - 1]){
17 p = i - 1;
18 break;
19 }
20 }
21
22 if(p == -1){
23 Arrays.sort(num);
24 return;
25 }
26
27 int c = -1;
28 for(int i = num.length - 1; i >=0; i--){
29 if(num[i] > num[p]) {
30 c = i;
31 break;
32 }
33 }
34
35 swap(num, p, c);
36 Arrays.sort(num, p + 1, num.length);
37
38 }
39 }