排列

发表于 | 分类于 | 浏览 次

排列系列

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法1：回溯

全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{3, 4, 5}为例说明如何编写全排列的递归算法。

1、首先看两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。由于一个数的全排列就是其本身，从而得到以上结果。

2、再看三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合。

从而可以推断，设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p)，pn = p - {rn}。因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        dfs(nums, 0, res);
        return res;
    }
    void swap(int&a, int &b){
        int tmp = a;
        a = b;
        b = tmp;
    }
    void dfs(vector<int>&nums, int i, vector<vector<int>>& res){
        if(i == nums.size()){
            vector<int> tmp(nums);
            res.push_back(tmp);
            return;
        }
        for(int j=i;j<nums.size();++j){
            swap(nums[i], nums[j]);
            dfs(nums, i + 1, res);
            swap(nums[i], nums[j]);
        }
    }
};

此题解法和subsets有相似之处。

解法2：回溯

这种思路和思路的区别是：思路采用位置两两交换，交换后出现一种新的组合，将这种新的组合添加到中间集中，再添加到结果集中。而这种思路是采用逐一向中间集中添加元素，当中间集中元素个数等于nums.size()时，将中间集添加到结果集中，并终止该层递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        vector<bool> vis(nums.size(), false);
        dfs(nums, tmp, vis, res);
        return res;
    }
    void dfs(vector<int>& nums, vector<int>& tmp, vector<bool>& vis, vector<vector<int>>& res){
        if(tmp.size() == nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();++i){
            if(!vis[i]){
                tmp.push_back(nums[i]);
                vis[i] = true;
                dfs(nums, tmp, vis, res);
                tmp.pop_back();
                vis[i] = false;
            }
        }
    }
};

Permutation Sequence

Next permutation

Next Permutation

当整个是逆序时，无法找到下一个更大的排列了。如[3,2,1]，此时按照题目要求，直接将序列逆序，变成[1,2,3]。

  • 第一步：首先找到数组连续的一对数a[i]与a[i-1]，a[i] > a[i-1]。

  • 第二步：之后从a[i,…,n-1]中找出一个比a[i-1]大的最小的数arr[j]与a[i-1]交换。

    在交换之前，序列arr[i,…,n-1]满足逆序，即，a[i] >= a[i+1]>=a[i+2]>=…>=a[n-1]。若不，假设，a[r]<a[s]，i<=r<s<=n-1。a[i]就不会是第一个满足a[i] > a[i-1]的元素。

    如[6,5,4,3,2,1]满足逆序，若交换4和3，则得到[6,5,3,4,2,1]，此时可以满足a[2] < a[3]。那么3和4就是第一对被找到的满足a[i] > a[i-1]的元素了。

    由于arr[i-1] < arr[j]小，交换之后的序列arr[i,…,n-1]仍然满足逆序。reverse(arr[i,..n-1])
    注意：数组中存在重复元素时的情形。
    当arr[i,..n-1]满足逆序时，若数组arr[i,..n-1]中存在重复元素，则这两个重复元素必然相邻．交换两个相等元素，显然无用，因此，在前面寻找可交换元素的过程中，没有将两个相等元素作为寻找目标．但是此时，若这两个相等元素正是arr[i,..n-1]中比arr[i-1]大的最小的元素，那么此时该选择哪一个元素呢？答案是选择索引较大的那一个。因为索引较大的那一个目前处在较低位上，reverse之后处在较高位上．

解法1

1
2


参考文献

[1]next permutation视频：https://www.bilibili.com/video/av52421617?from=search&seid=9609389838434247675
[2]Permutations：https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51534048