首页 > 代码库 > 【LeetCode】Permutation全排列

【LeetCode】Permutation全排列

1. Next Permutation

    实现C++的std::next_permutation函数,重新排列范围内的元素,返回按照 字典序 排列的下一个值较大的组合。若其已经是最大排列,则返回最小排列,即按升序重新排列元素。不能分配额外的内存空间。

void nextPermutation(vector<int>& nums) {
    next_permutation(nums.begin(), nums.end());
}

    全排列 Permutation 问题已经被古人研究透了,参见 Wikipedia page,Next Permutation 有一个经典的简单有效算法,还能解决含有重复元素的全排列问题。

  1. 从尾端寻找第一个下标 i,使 nums[i] < nums[i + 1]。若这样的 i 不存在,则这个排列已经是降序排列(或者元素全部相同),那么直接逆序得到升序排列。
  2. 从尾端寻找第一个下标 j,使 nums[i] < nums[j]。若 i 存在,则 j 一定存在且 i < j,因为 j 起码可以 = i + 1。
  3. 交换 i 和 j 位置的元素。
  4. 逆序从 i + 1 到结尾的子数组,即求出下一个序列。

    e.g. 

nums = [6, 3, 4, 9, 8, 7, 1]
              i        j
  1. 找到 i = 2,nums[i] = 4。i 右边的一定是降序排列 [9, 8, 7, 1]
  2. 从尾端找第一个大于 nums[i] 的数 7,即 nums[j] = 7。
  3. 交换 4 和 7,[6, 3, 7, 9, 8, 4, 1]。保证交换后的 [6, 3, 7, ......] 一定大于原来的 [6, 3, 4, ......],且可以发现 i 右边的 [9, 8, 4, 1] 仍然是降序排列
  4. 对 i 右边进行逆序,得到结果 [6, 3, 7, 1, 4, 8, 9]。

C++实现:

 

 1 void nextPermutation(vector<int>& nums) {
 2     int j = nums.size() - 1, i = j;
 3     while (--i >= 0) {
 4         if (nums[i] < nums[i + 1])
 5             break;
 6     }
 7     if (i != -1) {
 8         while (j > i) {
 9             if (nums[j] > nums[i])
10                 break;
11             j--;
12         }
13         swap(nums[i], nums[j]);
14     }
15     reverse(nums.begin() + i + 1, nums.end());
16     return;
17 }

 

【LeetCode】Permutation全排列