排列算法――字典序法 - JAVA

前言

LeetCode上确实有不少全排列的题目，之前介绍了一种递归的解法，链接见：字符串全排列算法
这里介绍一种字典序方法

字典序法

对给定的字符集中的字符规定一个先后关系，在此基础上按照顺序依次产生每个排列。例如字符集{1,2,3}，按照字典序生成的全排列是：123，132，213，231，312，321
参考示例：

算法流程如下：从右向左，找到第一个破坏从右向左递增顺序的数字，在上图的参考示例中，3是第一个破坏递增序列的，因为1，2，4，5已经是一个递增序列了从右向左，找到第一个大于step1的数字，这里是4交换这两个数字逆序4之后的数字序列
该方法支持数据重复，且在C++STL中被采用

题目

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 Z http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcmRlciAoaWUsIHNvcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIpLjxicj4KPGJyPgpUaGUgcmVwbGFjZW1lbnQgbXVzdCBiZSBpbi1wbGFjZSwgZG8gbm90IGFsbG9jYXRlIGV4dHJhIG1lbW9yeS48YnI+Cjxicj4KSGVyZSBhcmUgc29tZSBleGFtcGxlcy4gSW5wdXRzIGFyZSBpbiB0aGUgbGVmdC1oYW5kIGNvbHVtbiBhbmQgaXRzIGNvcnJlc3BvbmRpbmcgb3V0cHV0cyBhcmUgaW4gdGhlIHJpZ2h0LWhhbmQgY29sdW1uLjxicj4KMSwyLDMgofogMSwzLDI8YnI+CjMsMiwxIKH6IDEsMiwzPGJyPgoxLDEsNSCh+iAxLDUsMTxicj4KCjxicj4KCjxicj4KCjxoMj5BQ7T6wus8L2gyPgo8cHJlIGNsYXNzPQ=="brush:java;">public class Solution { public void nextPermutation(int[] num) { // special case if (num == null || num.length <= 1) { return; } // find the partition number which violate the increase trend int partition, swapLoc; for (partition = num.length - 1; partition - 1 >= 0; partition--) { if (num[partition - 1] < num[partition]) { break; } } partition -= 1; // find the first digit which large than Partition number if (partition >= 0) { for (swapLoc = num.length - 1; swapLoc > partition; swapLoc--) { if (num[swapLoc] > num[partition]) { break; } } // swap partition number and change number int tmp = num[partition]; num[partition] = num[swapLoc]; num[swapLoc] = tmp; } // reverse all the digit on the right of partition index for (int i = partition + 1, j = num.length - 1; i < j; i++, j--) { int tmp = num[i]; num[i] = num[j]; num[j] = tmp; } } }