查找第n个集幂的 [英] Find n-th set of a powerset

问题描述

我试图找到第n 的幂集。由第n 我的意思是，在以下的顺序产生幂 - 首先通过的大小，然后，字典顺序 - ，等等，集合的索引中的幂 [A，B，C] 是：

I'm trying to find the n-th set in a powerset. By n-th I mean that the powerset is generated in the following order -- first by the size, and then, lexicographically --, and so, the indices of the sets in the powerset of [a, b, c] is:

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

在寻找一个解决方案，所有我能找到的是一个算法返回元素列表的第n个排列 - 例如，的这里。

上下文

我想找回一个vector V 元素的整个幂，但我需要的时间与一组这样做。

I'm trying to retrieve the entire powerset of a vector V of elements, but I need to do this with one set at a time.

要求

• 余只能维持两个向量的同时，第一个与列表中原始项目，而第二个用第n 从设置的幂V - 这就是为什么我愿意在这里有一个 n个集功能;
• 在我需要这个做的不可以线性时间的解决方案的空间 - 这意味着它无法列出所有集，他们选择了第n 之一;
• 在我最初的想法是使用位重新present的位置，并得到一个有效映射我需要的东西 - 为不完整的解决方案，我贴

• I can only maintain two vectors at the same time, the first one with the original items in the list, and the second one with the n-th set from the powerset of V -- that's why I'm willing to have an n-th set function here;
• I need this to be done not in linear time on the space of solutions -- which means it cannot list all the sets and them pick the n-th one;
• my initial idea is to use bits to represent the positions, and get a valid mapping for what I need -- as the "incomplete" solution I posted.

推荐答案

我没有封闭形式的功能，但我有位黑客的非循环 next_combination 功能，欢迎您，如果有帮助。它假定你能适应位掩码为某个整数类型，这可能不是因为有一个不合理的假设2 ⁶⁴ 的可能性为64元一套。

I don't have a closed form for the function, but I do have a bit-hacking non-looping next_combination function, which you're welcome to, if it helps. It assumes that you can fit the bit mask into some integer type, which is probably not an unreasonable assumption given that there are 2⁶⁴ possibilities for the 64-element set.

正如评论说，我觉得有点古怪的词典式排序这个定义，因为我会说字典序为： []，[A]，[AB]，[ABC ]，[交流]，[B]，[BC]，[C] 。但我不得不前做了第一个按大小，然后辞书枚举。

As the comment says, I find this definition of "lexicographical ordering" a bit odd, since I'd say lexicographical ordering would be: [], [a], [ab], [abc], [ac], [b], [bc], [c]. But I've had to do the "first by size, then lexicographical" enumeration before.

// 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号线在做位黑客当量（扩展）常规EX pression更换，其中发现的最后一个 01 在字符串中，将其翻转到 10 并且将下面所有的 1 一切都是到最合适的。

Line 5 is doing the bit-hacking equivalent of the (extended) regular expression replacement, which finds the last 01 in the string, flips it to 10 and shifts all the following 1s all the way to the right.

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

第6行做这个（仅当previous一个失败的），增加一个 1 倒腾 1 一切都是到最合适的：

Line 6 does this one (only if the previous one failed) to add one more 1 and shift the 1s all the way to the right:

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

我不知道这是否有助于解释或阻碍：）

I don't know if that explanation helps or hinders :)

下面是一个快速和肮脏的驱动程序（命令行参数是集合的大小，默认为5，位在一个unsigned long的最大数量）：

Here's a quick and dirty driver (the command-line argument is the size of the set, default 5, maximum the number of bits in an 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个元素，赋予枚举的尺寸是有用的，但它可能是有益的列举了一些有限的一部分，如三要素所有子集。在这种情况下，如果变形例中一个字适合的比特两轮牛车只有真正有用。幸运的是，这很容易测试;你只需要做的计算如上面的最后一个字的位集合，到测试 last_zero 为零。 （在这种情况下，你不需要BITAND 面膜，实际上你可能想选择指定一组大小不同的方式。）如果 last_zero 原来是零（这实际上是pretty的罕见的），那么你需要做一些其他的方式的转变，但原理是一样的：找到第一个 0 其precedes一个 1 （注意的情况下 0 是一个单词的末尾和 1 的下一个的开始）;修改 01 到 10 ，计算出有多少 1 是你需要移动，并将其移动到年底。

---

It's hard to believe that this function might be useful for a set of more than 64 elements, given the size of the enumeration, but it might be useful to enumerate some limited part, such as all subsets of three elements. In this case, the bit-hackery is only really useful if the modification fits in a single word. Fortunately, that's easy to test; you simply need to do the computation as above on the last word in the bitset, up to the test for last_zero being zero. (In this case, you don't need to bitand mask, and indeed you might want to choose a different way of specifying the set size.) If last_zero turns out to be zero (which will actually be pretty rare), then you need to do the transformation in some other way, but the principle is the same: find the first 0 which precedes a 1 (watch out for the case where the 0 is at the end of a word and the 1 at the beginning of the next one); change the 01 to 10, figure out how many 1s you need to move, and move them to the end.

这篇关于查找第n个集幂的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！