排列组合问题算法分析与C++实现Leetcode46

排列组合问题算法分析与C++实现

排列组合经常出现在编程问题中，如从集合选取组合或排列。Leetcode 46、77分别是排列、组合问题。

排列问题

• 采用递归思路实现：对于全排列，每次从集合取出一个元素放在首位，然后对余下的集合实现全排列。
  C++实现

vector<vector<int>> PermutationAll(const list<int> &nums) {
  vector<vector<int>> ans;
  size_t size = nums.size();
  if (size == 1) {
    return {{nums.front()}};
  }
  if (size > 1) {
    for (auto it = nums.begin(); it != nums.end(); it++) {
      vector<int> tmp;
      tmp.push_back(*it);
      list<int> cp(nums);
      cp.erase(std::find(cp.begin(), cp.end(), *it));
      auto p = PermutationAll(cp);
      for (auto x : p) {
        vector<int> cpp(tmp);
        cpp.insert(cpp.end(), x.begin(), x.end());
        ans.push_back(cpp);
      }
    }
  }
  return ans;
}

• 上面实现了全排列，那么部分元素的排列如何做，同样采用递归实现，代码略有不同：

vector<vector<int>> Permutation(const list<int> &nums, int size) {
  vector<vector<int>> ans;
  size_t n = nums.size();
  if (n < size) {
    throw std::runtime_error("2nd Para in Permutation() is error.");
  }
  if (size == 1) {
    for (auto x : nums) {
      vector<int> tmp{x};
      ans.push_back(tmp);
    }
    return ans;
  }
  if (size > 1) {
    for (auto it = nums.begin(); it != nums.end(); it++) {
      vector<int> tmp;
      tmp.push_back(*it);
      list<int> cp(nums);
      cp.erase(std::find(cp.begin(), cp.end(), *it));
      auto p = Permutation(cp, size - 1);
      for (auto x : p) {
        vector<int> cpp(tmp);
        cpp.insert(cpp.end(), x.begin(), x.end());
        //O(1) operation
        // cpp.splice(cpp.end(),x);
        ans.push_back(cpp);
      }
    }
  }
  return ans;
}

• 完整测试代码

#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::list;
using std::vector;

vector<vector<int>> PermutationAll(const list<int> &nums) {
  vector<vector<int>> ans;
  size_t size = nums.size();
  if (size == 1) {
    return {{nums.front()}};
  }
  if (size > 1) {
    for (auto it = nums.begin(); it != nums.end(); it++) {
      vector<int> tmp;
      tmp.push_back(*it);
      list<int> cp(nums);
      cp.erase(std::find(cp.begin(), cp.end(), *it));
      auto p = PermutationAll(cp);
      for (auto x : p) {
        vector<int> cpp(tmp); 
        cpp.insert(cpp.end(), x.begin(), x.end());
        // O(1) operation
        // cpp.splice(cpp.end(),x);
        ans.push_back(cpp);
      }
    }
  }
  return ans;
}

vector<vector<int>> Permutation(const list<int> &nums, int size) {
  vector<vector<int>> ans;
  size_t n = nums.size();
  if (n < size) {
    throw std::runtime_error("2nd Para in Permutation() is error.");
  }
  if (size == 1) {
    for (auto x : nums) {
      vector<int> tmp{x};
      ans.push_back(tmp);
    }
    return ans;
  }
  if (size > 1) {
    for (auto it = nums.begin(); it != nums.end(); it++) {
      vector<int> tmp;
      tmp.push_back(*it);
      list<int> cp(nums);
      cp.erase(std::find(cp.begin(), cp.end(), *it));
      auto p = Permutation(cp, size - 1);
      for (auto x : p) {
        vector<int> cpp(tmp);
        cpp.insert(cpp.end(), x.begin(), x.end());
        ans.push_back(cpp);
      }
    }
  }
  return ans;
}
bool IsEqual(const vector<int> &a, const vector<int> &b) {
  size_t na = a.size();
  size_t nb = b.size();
  if (na != nb) {
    return false;
  }
  size_t i = 0;
  while (i < na) {
    if (a[i] != b[i]) {
      return false;
    }
    i++;
  }
  return true;
}
int main() {
  list<int> nums{1, 2, 3, 4, 5};
  cout << "Enter your permutation size: ";
  int size = 0;
  cin >> size;
  cout << endl;
  auto x = Permutation(nums, size);
  auto y = PermutationAll(nums);
  cout << "Permutations number: " << x.size() << endl;
  cout << "PermutationAll number: " << y.size() << endl;
  int np = 1;
  size_t n = nums.size();
  int cnt = 0;
  while (cnt < size) {
    np *= n--;
    cnt++;
  }
  cout << "Check number Permutation: " << np << endl;
  cnt = 0;
  np = 1;
  while (cnt < n) {
    np *= n--;
    cnt++;
  }
  cout << "Permutation all: " << endl;
  std::for_each(y.begin(), y.end(), [](const vector<int> &k) {
    std::for_each(k.begin(), k.end(),
                  [](const int &d) { std::cout << d << " "; });
    cout << endl;
  });
  for (auto &b : x) {
    std::sort(b.begin(), b.end());
  }
  std::sort(x.begin(), x.end());
  //   auto unique_end = std::unique(x.begin(), x.end(), IsEqual);
  auto unique_end = std::unique(x.begin(), x.end());
  cout << "Combinations: " << endl;
  std::for_each(x.begin(), unique_end, [](const vector<int> &k) {
    std::for_each(k.begin(), k.end(),
                  [](const int &d) { std::cout << d << " "; });
    cout << endl;
  });
  return 0;
}

组合问题

• 组合过程，思路分析：从n个元素选出m个元素，每次选出一个元素（如从前到后次序），然后从选出的元素位置后的部分求出选m-1个元素的组合，如此利用递归求解。
  完整测试代码：

#include <algorithm>
#include <iostream>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
// TODO: use template
vector<vector<int>> Combination(const vector<int> &nums, int m,
                                vector<int>::const_iterator &begin,
                                vector<int>::const_iterator &end) {
  if (nums.empty()) {
    // TODO: which is better exception or error
    throw std::runtime_error("size of nums is zero.");
  }
  if (m > end - begin) {
    // throw std::runtime_error("combination's size is bigger than size of
    // nums.");
    cerr << "combination's size is bigger than size of nums." << endl;
  }
  vector<vector<int>> ans;
  if (m == 0) {
    ans = {nums};
  }
  if (m == 1) {
    for (auto x = begin; x != end; x++) {
      vector<int> tmp{*x};
      ans.push_back(tmp);
    }
  }
  if (m > 1) {
    for (auto it = begin; it != end - m + 1; it++) {
      vector<int> tmp;
      tmp.push_back(*it);
      auto nbegin = it + 1;
      auto p = Combination(nums, m - 1, nbegin, end);
      for (auto x : p) {
        vector<int> cpp(tmp);
        cpp.insert(cpp.end(), x.begin(), x.end());
        ans.push_back(cpp);
      }
    }
  }
  return ans;
}

int main() {
  vector<int> vn{1, 2, 3, 4, 5};
  cout << "Enter your combination size: ";
  int size = 0;
  cin >> size;
  auto begin = vn.cbegin();
  auto end = vn.cend();
  auto C = Combination(vn, size, begin, end);
  std::for_each(C.begin(), C.end(), [](const vector<int> &k) {
    std::for_each(k.begin(), k.end(),
                  [](const int &d) { std::cout << d << " "; });
    cout << endl;
  });
  return 0;
}

Leetcode 77题参考：

vector<vector<int>> combine(int n, int k) {
  vector<int> nums;
  for (int i = 1; i < n + 1; i++) {
    nums.push_back(i);
  }
  auto begin = nums.cbegin();
  auto end = nums.cend();
  return Combination(nums, k, begin, end);
}

另一种耗时更短的解法：

class Solution {
 private:
  vector<vector<int>> res;
  void dfs(int n, int k, int start, vector<int> &tmp) {
    if (tmp.size() == k) {
      res.push_back(tmp);
      return;
    }
    for (int i = start; i <= n; i++) {
      tmp.push_back(i);
      dfs(n, k, i + 1, tmp);
      tmp.pop_back();
    }
    return;
  }

 public:
  vector<vector<int>> combine(int n, int k) {
    if (n <= 0 && k <= 0 && k > n) return res;
    vector<int> tmp;
    dfs(n, k, 1, tmp);
    return res;
  }
};