c++ - 找到幂集的第 n 组

Question

我正试图找到幂集中的 n-th 集。 n-th 我的意思是幂集是按以下顺序生成的——首先是大小，然后是字典序——如此，的幂集中集合的索引>[a, b, c] 是:

0 - []
1 - [a]
2 - [b]
3 - [c]
4 - [a, b]
5 - [a, c]
6 - [b, c]
7 - [a, b, c]

在寻找解决方案时，我只能找到一种算法来返回元素列表的第 n 个排列——例如，here .

上下文:

我正在尝试检索元素 vector V 的整个幂集，但我需要一次处理一个集合。

要求:

• 我只能同时维护两个 vector ，第一个包含列表中的原始项，第二个包含 V 的幂集中的 n-th 集合 -- 这就是为什么我愿意在这里使用 n-th set 函数；
• 我需要在解决方案空间的线性时间内而不是完成这项工作——这意味着它无法列出所有集合，他们会选择第 n 个 一个;
• 我最初的想法是使用位来表示位置，并获得我需要的有效映射——作为我发布的“不完整”解决方案。

Answer 1

我没有函数的封闭形式，但我确实有一个位黑客非循环 next_combination功能，如果有帮助，欢迎您使用。它假设您可以将位掩码放入某种整数类型，这可能不是一个不合理的假设，因为 64 元素集有 2⁶⁴ 种可能性。

正如评论所说，我发现这个“字典顺序”的定义有点奇怪，因为我会说字典顺序是:[], [a], [ab], [abc], [ac], [b], [bc], [c] .但我之前不得不做“先按大小，然后按字典顺序”的枚举。

// Generate bitmaps representing all subsets of a set of k elements,
// in order first by (ascending) subset size, and then lexicographically.
// The elements correspond to the bits in increasing magnitude (so the
// first element in lexicographic order corresponds to the 2^0 bit.)
//
// This function generates and returns the next bit-pattern, in circular order
// (so that if the iteration is finished, it returns 0).
//
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
  UnsignedInteger last_one = comb & -comb;
  UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
  if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
  else if (last_one > 1) return mask / (last_one / 2);
  else return ~comb & 1;
}

第 5 行正在执行与(扩展的)正则表达式替换等效的位破解，它找到最后一个 01在字符串中，将其翻转为 10并转移以下所有1一直向右。

s/01(1*)(0*)$/10\2\1/

第 6 行执行此操作(仅当前一个失败时)再添加一个 1并转移 1一直向右:

s/(1*)0(0*)/\21\1/

我不知道这个解释是有帮助还是有阻碍:)

---

这是一个快速而肮脏的驱动程序(命令行参数是集合的大小，默认为 5，unsigned long 中的最大位数):

#include <iostream>

template<typename UnsignedInteger>
std::ostream& show(std::ostream& out, UnsignedInteger comb) {
  out << '[';
  char a = 'a';
  for (UnsignedInteger i = 1; comb; i *= 2, ++a) {
    if (i & comb) {
      out << a;
      comb -= i;
    }
  }
  return out << ']';
}

int main(int argc, char** argv) {
  unsigned int n = 5;
  if (argc > 1) n = atoi(argv[1]);
  unsigned long mask = (1UL << n) - 1;
  unsigned long comb = 0;
  do {
    show(std::cout, comb) << std::endl;
    comb = next_combination(comb, mask);
  } while (comb);
  return 0;
}

---

鉴于枚举的大小，很难相信此函数可能对超过 64 个元素的集合有用，但它可能对枚举某些有限的部分有用，例如三个元素的所有子集。在这种情况下，bit-hackery 只有在修改适合单个单词时才真正有用。幸运的是，这很容易测试；您只需要对位集中的最后一个单词进行上述计算，直至测试 last_zero为零。 (在这种情况下，您不需要位和 mask ，实际上您可能想选择一种不同的方式来指定集合大小。)如果 last_zero结果为零(这实际上是非常罕见的)，那么你需要以其他方式进行转换，但原理是一样的:找到第一个 0在 1 之前(注意 0 在一个词的结尾而 1 在下一个词的开头的情况)；更改 01至 10 , 算出有多少 1 s 你需要移动，并将它们移动到最后。