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

我正在尝试在Powerset中找到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 ，第一个 vector 具有列表中的原始项，第二个 vector 具有n-th的幂集中的V设置-这就是为什么我愿意在这里拥有n-th set函数;

我需要在解决方案空间上以线性时间完成而不是，这意味着它无法列出所有集合，而他们只能选择一个n-th；

我的最初想法是使用位表示位置，并为我需要的内容获得有效的映射-作为我发布的“不完整”解决方案。

最佳答案

我没有该函数的封闭形式，但是我确实有一个有点骇人听闻的非循环next_combination函数，如果有帮助，欢迎您。它假定您可以将位掩码设置为某种整数类型，考虑到64个元素集有264种可能性，这可能不是一个不合理的假设。

就像评论所说，我发现“字典顺序”的定义有点奇怪，因为我会说字典顺序是:[], [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行正在做(扩展的)正则表达式替换的位hacking行为，该替换查找字符串中的最后一个01，将其翻转为10，然后将所有随后的1一直向右移动。

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

第6行执行此操作(仅在前一个操作失败的情况下)，再添加一个1并将1一直向右移动:

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

我不知道该解释是有用的还是不利的:)

这是一个快速而肮脏的驱动程序(命令行参数是集合的大小，默认为5，最大为无符号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个元素有用，但枚举某些有限的部分(例如三个元素的所有子集)可能很有用。在这种情况下，仅当修饰词适合单个单词时，比特黑客才真正有用。幸运的是，这很容易测试。您只需要对位集中的最后一个字进行上述计算，直到last_zero为零的测试为止。 (在这种情况下，您不需要bit和mask，实际上您可能想要选择另一种指定设置大小的方法。)如果last_zero最终为零(实际上很少见)，那么您需要以其他方式进行转换，但原理相同:找到第一个0之前的1(请注意0在单词的末尾，而1在下一个词的开头的情况);将01更改为10，找出需要移动多少1，然后将其移动到末尾。

关于c++ - 查找幂集的第n组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14713584/