linux-hw/8/function.cpp

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

#include "function.h"

using std::vector; using std::swap; using std::ostream;

// 处理参数
void read_arg(const int argc, char ***pargv, std::vector<int> &arr) {
  char **argv = *pargv;
  if (argc < 3)
    throw std::invalid_argument("usage: ./run.exe [arr_size] [arr (split by space)]");
  const size_t arr_size = strtoul(argv[1], NULL, 0);
  if (arr_size + 2 != static_cast<size_t>(argc))
    throw std::invalid_argument("arr_size dosen't fit");
  int carr[arr_size];
  for (size_t i = 0; i < arr_size; ++i)
    carr[i] = strtol(argv[2 + i], NULL, 0);
  arr = vector<int>(&carr[0], &carr[arr_size]);
}

// 检查beg与end之间有无重复值
bool isdiff(vector<int> &arr, size_t beg, size_t end) {
  for (size_t i = beg; i < end; ++i) {
    if (arr[i] == arr[end])
      return false;
  }
  return true;
}

// 递归求全排列并存入vector<vector<int>>中
void perm_r(vector<int> &arr, size_t pos, size_t len, vector<vector<int>> &res){
  if (pos == len) {
    res.push_back(arr);
    return;
  }
  for (size_t i = pos; i <= len; ++i) {
    if (isdiff(arr, pos, i) == true) {
      swap(arr[pos], arr[i]);
      perm_r(arr, pos + 1, len, res);
      swap(arr[pos], arr[i]);
    }
  }
}

// 简化入口
void permutation(vector<int> &arr, vector<vector<int>> &res) {
  perm_r(arr, 0, arr.size() - 1, res);
}

// 打印vector<int>
ostream &print_arr(const vector<int> &vec, ostream &os) {
  os << "[";
  for (const int &n : vec)
    os << " " << n;
  os << " ]";
  return os;
};