生成排列、组合（无重复集合）

Posted on 2024-11-10 Edited on 2024-11-16 In Algorithms , Discrete mathematics , Counting Word count in article: 269 Reading time ≈ 1 mins.

顺便复习一下离散数学，下周 Quiz...

按照字典序生成的排列

void nextPermutation(vector<int>& lastPermutation) {
  size_t j = lastPermutation.size() - 2;  // 假设其中至少有2个元素
  size_t k = lastPermutation.size() - 1;
  size_t r = lastPermutation.size() - 1;
  size_t s;
  while (lastPermutation[j] > lastPermutation[j + 1]) {
    --j;
  }
  while (lastPermutation[j] > lastPermutation[k]) {
    --k;
  }
  swap(lastPermutation[j], lastPermutation[k]);
  s = j + 1;
  while (r > s) {
    --r;
    ++s;
  }
  // 使j后面的元素升序排列
  sort(lastPermutation.begin() + j + 1, lastPermutation.end());
}

实现全排列可以简单的执行次生成下一个排列

size_t fact(size_t t) {
  if (t == 0 || t == 1) return 1;
  return t * fact(t - 1);
}

vector<vector<int>> fullPermutation(vector<int> initial) {
  vector<vector<int>> res;
  sort(initial.begin(), initial.end());
  res.push_back(initial);
  for (size_t t = 1; t < fact(initial.size()); ++t) {
    res.push_back(res[res.size() - 1]);
    nextPermutation(res[res.size() - 1]);
  }
  return res;
}

生成组合

对于一个大小为的集合，该问题可以转变为一个求所有长度为的Bit String的问题，即通过表示选择一个元素，而则不选择它
更加简洁的方法生成所有Bit String是直接通过余二倒取生成二进制串，遍历所有二进制的范围为

此为生成下一个最大Bit String的算法，此算法本质是计算一个二进制加一的结果。

void nextBitString(string &lastBitString) {
  auto c = lastBitString.rbegin();
  while (c != lastBitString.rend() && *c == '1') (*c = '0', ++c);
  *c = '1';
}

类似的，这里给出生成所有`Bit String`的算法

vector<string> allBitString(size_t length) {
  vector<string> res;
  res.push_back(string(length, '0'));
  for (size_t i = 1; i < (1 << length); ++i) {
    res.push_back(res[res.size() - 1]);
    nextBitString(res[res.size() - 1]);
  }
  return res;
}

按照字典序生成集合的组合

其中第一个组合是，最后一个组合是

此算法为按照字典序生成下一个组合

void nextCombination(vector<size_t> &lastCombination, size_t n) {
  auto i = lastCombination.size() - 1;
  while (lastCombination[i] == (n - lastCombination.size() + i + 1)) {
    if (i != 0)
      --i;
    else
      break;
  }
  ++lastCombination[i];
  for (auto j = i + 1; j < lastCombination.size(); j++) {
    lastCombination[j] = lastCombination[i] + j - i;
  }
}

类似的，给出求出所有组合的算法

long long fact(size_t t) {
  if (t == 0 || t == 1) return 1;
  return t * fact(t - 1);
}

long long C(size_t n, size_t r) { return fact(n) / fact(n - r) / fact(r); }

vector<vector<size_t>> fullCombination(vector<size_t> initial, size_t n) {
  vector<vector<size_t>> res;
  sort(initial.begin(), initial.end()); // 初始化升序序列
  res.push_back(initial);
  for (long long i = 1; i < C(n, initial.size()); i++) {
    res.push_back(res[res.size() - 1]);
    nextCombination(res[res.size() - 1], n);
  }
  return res;
}

0%