Next Permutation之字典序法
字典序法是求出当前数组在字典序下的下一个数组，也就是正好比当前数组稍大的下一数组。笔者是从《组合数学》中看到的算法，但当时并没有深入思考，而当在leetcode上看到了next permutation才知道该算法的经典。
算法的思路如下：
（1）求满足下列不等式的最大的j，记为i， 即
i=max{j | nj-1<nj}
（2）求满足下列不等式的最大的k，记为h，即
h=max{k | ni-1<nk}
（3）将ni-1和nh交换，这时数组从i位开始都是递减的，所以将数组从第i位开始到最后这一部分进行180度旋转，得到最终的数组了。
下面分析一下算法，为什么通过这个算法得到的就是比原来数组大的最小的数组呢？首先，nh是比ni-1大的最小整数，为什么呢，nh不是只是比ni-1大的最靠后的数字而已吗，其实从nh开始，他后面的不可能有比ni-1大的数，然后在i到h这一段，nh又恰好是最小的那个数，因为如果这一段出现了比nh小的数，那么第（1）个条件就不满足了。所以将ni-1和nh交换是肯定对的。然后，交换完以后，从第i位到第h位都是比原来的ni-1大的数，因为他们比nh都要大，然后根据第（2）个条件，从第h+1位开始到最后都是比原来ni-1小的数，所以从第i位开始到最后形成了一个递减的序列，因此此时再将这一序列颠倒一下便可得到题目所求的数组了。
算法的代码如下：
void nextPermutation(vector<int>& nums) {
if(nums.size()<2)
return;
//find a max index i, from i to the end is descending
int ase_max=-1;
for(int i=1;i<nums.size();i++){
if(nums[i]>nums[i-1]){
ase_max=i;
}
}
if(ase_max==-1){
//the nums is descending
for(int i=0;i<nums.size()/2;i++){
swap(nums[i],nums[nums.size()-i-1]);
}
return;
}
//find a max index k, where nums[k] is the smallest num that is bigger than nums[i-1]
int bigger_max=ase_max;
for(int i=ase_max-1;i<nums.size();i++){
if(nums[i]>nums[ase_max-1])
bigger_max=i;
}
//swap the nums[i-1] and nums[k]
swap(nums[ase_max-1],nums[bigger_max]);
//reverse the numbers from nums[i] to nums[size-1], because these numbers are deasending
for(int i=0;i<(nums.size()-ase_max)/2;i++){
swap(nums[ase_max+i],nums[nums.size()-i-1]);
}
}希望能对大家有所帮助
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年11月29日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读