Permutations

描述

Given a collection of numbers, return all possible permutations.

For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

next_permutation()

函数 next_permutation()的具体实现见这节 Next Permutation。

  1. // Permutations
  2. // 重新实现 next_permutation()
  3. // 时间复杂度O(n!)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     vector<vector<int> > permute(vector<int> &num) {
  7.         vector<vector<int> > result;
  8.         sort(num.begin(), num.end());
  10.         do {
  11.             result.push_back(num);
  12.         // 调用的是 2.1.12 节的 next_permutation()
  13.         // 而不是 std::next_permutation()
  14.         } while(next_permutation(num.begin(), num.end()));
  15.         return result;
  16.     }
  17. private:
  18.     // 代码来自 2.1.12 节的 next_permutation()
  19.     void nextPermutation(vector<int> &nums) {
  20.         next_permutation(nums.begin(), nums.end());
  21.     }
  23.     template<typename BidiIt>
  24.     bool next_permutation(BidiIt first, BidiIt last) {
  25.         // Get a reversed range to simplify reversed traversal.
  26.         const auto rfirst = reverse_iterator<BidiIt>(last);
  27.         const auto rlast = reverse_iterator<BidiIt>(first);
  29.         // Begin from the second last element to the first element.
  30.         auto pivot = next(rfirst);
  32.         // Find `pivot`, which is the first element that is no less than its
  33.         // successor.  `Prev` is used since `pivort` is a `reversed_iterator`.
  34.         while (pivot != rlast && *pivot >= *prev(pivot))
  35.             ++pivot;
  37.         // No such elemenet found, current sequence is already the largest
  38.         // permutation, then rearrange to the first permutation and return false.
  39.         if (pivot == rlast) {
  40.             reverse(rfirst, rlast);
  41.             return false;
  42.         }
  44.         // Scan from right to left, find the first element that is greater than
  45.         // `pivot`.
  46.         auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
  48.         swap(*change, *pivot);
  49.         reverse(rfirst, pivot);
  51.         return true;
  52.     }
  53. };

递归

本题是求路径本身，求所有解，函数参数需要标记当前走到了哪步，还需要中间结果的引用，最终结果的引用。

扩展节点，每次从左到右，选一个没有出现过的元素。

本题不需要判重，因为状态装换图是一颗有层次的树。收敛条件是当前走到了最后一个元素。

代码

  1. // Permutations
  2. // 深搜，增量构造法
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     vector<vector<int> > permute(vector<int>& num) {
  7.         sort(num.begin(), num.end());
  9.         vector<vector<int>> result;
  10.         vector<int> path;  // 中间结果
  12.         dfs(num, path, result);
  13.         return result;
  14.     }
  15. private:
  16.     void dfs(const vector<int>& num, vector<int> &path,
  17.             vector<vector<int> > &result) {
  18.         if (path.size() == num.size()) {  // 收敛条件
  19.             result.push_back(path);
  20.             return;
  21.         }
  23.         // 扩展状态
  24.         for (auto i : num) {
  25.             // 查找 i 是否在path 中出现过
  26.             auto pos = find(path.begin(), path.end(), i);
  28.             if (pos == path.end()) {
  29.                 path.push_back(i);
  30.                 dfs(num, path, result);
  31.                 path.pop_back();
  32.             }
  33.         }
  34.     }
  35. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/brute-force/permutations.html