找到第n组的powerset

Question

我正试图n-th在powerset中找到这个集合.通过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个排列 - 例如,这里.

背景:

我正在尝试检索V元素向量的整个powerset ,但我需要一次使用一组.

要求:

• 我只能同时维护两个向量,第一个带有列表中的原始项目,第二个带有n-th来自powerset 的集合V- 这就是为什么我愿意在n-th set这里有一个函数;
• 我需要这样做不是线性时间的解决方案的空间-这意味着它无法列出所有的设置,并将挑选n-th一个;
• 我最初的想法是使用位来表示位置,并获得我需要的有效映射 - 作为我发布的"不完整"解决方案.

Answer 1

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

正如评论所说,我发现"词典排序"的定义有点奇怪,因为我会说词典排序是: [], [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并将所有后续1s一直移到右侧.

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

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

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才真正有用.幸运的是,这很容易测试; 你只需要对bitset中的最后一个字进行上述计算,直到测试last_zero为零.(在这种情况下,你不需要bitand mask,实际上你可能想要选择一种不同的方式来指定设置大小.)如果last_zero结果为零(这实际上非常罕见),那么你需要做以某种其他方式进行转换,但原则是相同的:找到先0于a 的第一个1(注意0一个词的末尾和下一个词1的开头的情况); 更改01为10,找出1需要移动的数量,并将它们移动到最后.