5

我正在尝试n-th在 powerset 中找到该集合。我的意思是，powerset 是按n-th以下顺序生成的——首先是大小，然后是字典顺序——因此，powerset 中的集合的索引[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元素向量的整个幂集，但我需要一次只使用一组。

要求：

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

3 回答 3

5

我没有该函数的封闭形式，但我确实有一个有点破解的非循环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并将后面1的所有 s 一直向右移动。

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

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

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

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

这是一个快速而肮脏的驱动程序（命令行参数是集合的大小，默认为 5，最大无符号长的位数）：

#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为零。（在这种情况下，您不需要 bitand mask，实际上您可能想要选择一种不同的方式来指定集合大小。）如果last_zero结果为零（这实际上非常罕见），那么您需要做以其他方式进行转换，但原理是相同的：找到0a之前的第一个1（注意在0一个单词的结尾和1在下一个单词开头的情况）；更改01为，计算出需要移动10多少个s，然后将它们移动到最后。1

于 2013-02-05T21:39:02.613 回答
4

考虑元素列表L = [a, b, c]，的幂集由L下式给出：

P(L) = {
    [],
    [a], [b], [c],
    [a, b], [a, c], [b, c],
    [a, b, c]
}

考虑到每个位置，您将拥有以下映射：

id  | positions - integer | desired set
 0  |  [0 0 0]  -    0    |  []
 1  |  [1 0 0]  -    4    |  [a]
 2  |  [0 1 0]  -    2    |  [b]
 3  |  [0 0 1]  -    1    |  [c]
 4  |  [1 1 0]  -    6    |  [a, b]
 5  |  [1 0 1]  -    5    |  [a, c]
 6  |  [0 1 1]  -    3    |  [b, c]
 7  |  [1 1 1]  -    7    |  [a, b, c]

如您所见，id没有直接映射到整数。需要应用适当的映射，以便您拥有：

id  | positions - integer |  mapped  - integer
 0  |  [0 0 0]  -    0    |  [0 0 0] -    0
 1  |  [1 0 0]  -    4    |  [0 0 1] -    1
 2  |  [0 1 0]  -    2    |  [0 1 0] -    2
 3  |  [0 0 1]  -    1    |  [0 1 1] -    3
 4  |  [1 1 0]  -    6    |  [1 0 0] -    4
 5  |  [1 0 1]  -    5    |  [1 0 1] -    5
 6  |  [0 1 1]  -    3    |  [1 1 0] -    6
 7  |  [1 1 1]  -    7    |  [1 1 1] -    7

作为解决这个问题的尝试，我想出了使用二叉树来进行映射——我发布它，以便有人可以从中看到解决方案：

                                        #
                          ______________|_____________
        a               /                             \
                  _____|_____                   _______|______
        b        /           \                 /              \
              __|__         __|__           __|__            __|__
        c    /     \       /     \         /     \          /     \
           [ ]     [c]    [b]   [b, c]    [a]   [a, c]    [a, b]  [a, b, c]
index:      0       3      2       6       1      5         4         7
于 2013-02-05T17:42:13.953 回答
2

假设你的集合大小为 N。

因此，有 (N 选择 k) 个大小为 k 的集合。只需从 n 中减去（N 选择 k），直到 n 即将变为负数，您就可以非常快速地找到正确的 k（即第 n 个集合的大小）。这将您的问题减少到找到 N 集的第 n 个 k 子集。

您的 N 集的第一个（N-1 选择 k-1）k 个子集将包含其最少元素。因此，如果 n 小于（N-1 选择 k-1），则选择第一个元素并递归集合的其余部分。否则，您有（N-1 选择 k）个其他集合之一；丢弃第一个元素，从 n 中减去（N-1 选择 k-1），然后递归。

代码：

#include <stdio.h>

int ch[88][88];
int choose(int n, int k) {
 if (n<0||k<0||k>n) return 0;
 if (!k||n==k) return 1;
 if (ch[n][k]) return ch[n][k];
 return ch[n][k] = choose(n-1,k-1) + choose(n-1,k);
}

int nthkset(int N, int n, int k) {
 if (!n) return (1<<k)-1;
 if (choose(N-1,k-1) > n) return 1 | (nthkset(N-1,n,k-1) << 1);
 return nthkset(N-1,n-choose(N-1,k-1),k)<<1;
}

int nthset(int N, int n) {
 for (int k = 0; k <= N; k++)
  if (choose(N,k) > n) return nthkset(N,n,k);
  else n -= choose(N,k);
 return -1; // not enough subsets of [N].
}

int main() {
 int N,n;
 scanf("%i %i", &N, &n);
 int a = nthset(N,n);
 for (int i=0;i<N;i++) printf("%i", !!(a&1<<i));
 printf("\n");
}
于 2013-02-05T21:16:07.810 回答