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. 遞歸全排列就是從第一個數(shù)字起每個數(shù)分別與它后面的數(shù)字交換。
2. 去重的全排列就是從第一個數(shù)字起每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。(交換的時候判斷下是否已出現(xiàn)即可)
3. 非遞歸全排列就是由后向前找替換數(shù)和替換點，然后由后向前找第一個比替換數(shù)大的數(shù)與替換數(shù)交換，最后顛倒替換點后的所有數(shù)據(jù)。(證明)
   (參考)

// 遞歸版本
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;
      }
    }
  }
};