46. 全排列 Permutations

描述

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

示例

  Input: [1,2,3]
  Output:
  [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
  ]

思路：

1. 递归全排列就是从第一个数字起每个数分别与它后面的数字交换。
2. 去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。(交换的时候判断下是否已出现即可)
3. 非递归全排列就是由后向前找替换数和替换点，然后由后向前找第一个比替换数大的数与替换数交换，最后颠倒替换点后的所有数据。(证明)
   (参考)

// 递归版本
class Solution_46_01 {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> ret;
    _permute(0, nums.size() - 1, nums, ret);
    return ret;
  }
  void _permute(int k, int size, vector<int>& nums, vector<vector<int>>& ret) {
    if (k == size) {
      ret.push_back(nums);
      return;
    }
    for (int i = k; i <= size; ++i) {
      swapNum(nums, k, i);
      _permute(k + 1, size, nums, ret);
      swapNum(nums, i, k);
    }
  }
  void swapNum(vector<int>& nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
  }
};

// 非递归版本，基于Stl的next_permutation
class Solution_46_02 {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> ret;
    std::sort(nums.begin(), nums.end());
    ret.push_back(nums);
    while (next_permutation<vector<int>::iterator>(nums.begin(), nums.end())) {
      ret.push_back(nums);
    }
    return ret;
  }
  template <class BidirIt>
  bool next_permutation(BidirIt first, BidirIt last) {
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
    while (true) {
      BidirIt i1, i2;
      i1 = i;
      if (*--i < *i1) {
        i2 = last;
        while (!(*i < *--i2))
          ;
        std::iter_swap(i, i2);
        std::reverse(i1, last);
        return true;
      }
      if (i == first) {
        std::reverse(first, last);
        return false;
      }
    }
  }
};