字典排序permutation

理论

C++ 中的next_permutation 一般作为正序全排列的使用规则，其实这个就是正序字典排序的实现。

比如我们要对列表 [1,2,3] 做full permutation 一般使用递归实现如下，

 1 static boolean generateP(int index, int high, int[] list) {
 2 
 3     if (index == high) {
 4 
 5         System.arraycopy(P,0,list,0,list.length);
 6 
 7         return true;
 8 
 9     }else {
10 
11         for (int x = index; x <high; x++) {
12 
13             swap(list,list[x],list[index]);
14 
15             generateP(index+1,high,list);
16 
17             swap(list,list[x],list[index]);
18 
19         }
20 
21     }
22 
23     return false;
24 
25 }

下面对字典排序规则说一下

(1)从后往前遍历，找到第一个逆序，比如1,2,4,3 的2，记录位置pos与值value

(2) 如果遍历完也没有找到这个元素说明已经是排序的最后一个了那么从头到尾做reverse 使其他为升序如4 3 2 1 变为 1->2->3->4;

(3)如果步骤一找到了这个数，那么从后面往前面找到第一大于它的数，并且交换(很多人说从步骤一发现的数开始往后面找是不对的）

步骤3交换后从步骤一发现的的位置后面开始进行头尾的逆序操作。

拆分出来需要三个方法 reverse ，swap，permutation，

板子

 1 static void next_permutation(int[] nums) {
 2 
 3     int value = 0, pos = 0;
 4 
 5     int i = 0, temp = 0;
 6 
 7     for (i = nums.length - 1; i > 0; i--) {
 8 
 9         if (nums[i] > nums[i - 1]) {//记录非逆序的第一个数
10 
11             value = nums[i - 1];
12 
13             pos = i - 1;
14 
15             break;
16 
17         }
18 
19     }
20 
21     if (i == 0) {//未发现数那么直接进行逆置
22 
23         for (i = 0; i < nums.length / 2; i++) {
24 
25             temp = nums[i];
26 
27             nums[i] = nums[nums.length - i - 1];
28 
29             nums[nums.length - i - 1] = temp;
30 
31         }
32 
33         return;
34 
35     }
36 
37     for (int j = nums.length - 1; j > pos; j--) {
38 
39         if (value < nums[j]) {//从后往前面找到第一大于非逆序数
40 
41             temp = value;
42 
43             nums[pos] = nums[j];
44 
45             nums[j] = temp;
46 
47             break;
48 
49         }
50 
51     }
52 
53     for (i = pos + 1; i < pos + 1 + (nums.length - 1 - pos) / 2; i++) {
54 
55         temp = nums[i];//从非逆序数开始进行倒置
56 
57         nums[i] = nums[nums.length - 1 - i + pos + 1];
58 
59         nums[nums.length - 1 - i + pos + 1] = temp;
60 
61     }
62 
63 }
64 
65

题目例子：

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