使用 Gosper 的 Hack（银行家序列）生成所有子集

Question

我有一个生成数组所有子集的方法，我想尝试实现的是同一种方法，但使用二进制来实现。 Gosper 的 Hack 似乎是最好的主意，但我不知道如何实施它。下面的代码用于生成所有 subsets.The 子集可以是未知的 (http://imgur.com/KXflVjq) 这显示了运行几秒钟后的输出。感谢您的任何建议

int m = prop.length;
int list = (1 << m);
for(long i = 1; i<list; i++) {
   final List sub = new ArrayList<>();
   for(long j=0; j<m; j++) {
      if((i & (1<<j)) > 0) {      
         sub.add(j);
      }
   }
   Collections.sort(sub);
   System.out.println(sub);
}

编辑：由于我对问题的措辞不正确，我需要的输出是：

2  1  0
0  0  1 = 0 
0  1  0 = 1

等等

Answer 1

首先，我想指出，不清楚您要实现的目标到底是什么；请考虑澄清问题。我假设您想要生成 n 集的所有 k 子集。这个问题可以很容易地简化为生成 {1,2,...,n} 的所有 k-子集（即它足够计算所有 k-索引子集）。

一种算法，用于生成 n-set

的 k-子集

前段时间我写了 this implementation of a method (which I rediscovered few years ago) for generating all k-subsets of an n-set. Hope it helps. The algorithm essentially visists all binary sequences of length n containing exactly k ones in a clever way (without going through all 2^n sequences); see the accompanying note 描述算法，其中包含详细描述、伪代码和一个小的逐步示例。

我觉得时间复杂度是O(k {n choose k})量级。我还没有这方面的正式证据。（很明显，任何算法都必须花费 Omega({n choose k}) 时间。）

C:

中的代码

#include <stdlib.h>
#include <stdio.h>

void subs(int n, int k);

int main(int argc, char **argv)
{
    if(argc != 3) return 1;
    int n, k;

    n = atoi(argv[1]); k = atoi(argv[2]);
    subs(n, k);

    return 0;
}

void subs(int n, int k)
{
    int *p = (int *)malloc(sizeof(int)*k);
    int i, j, r;

    for(i = 0; i < k; ++i) p[i] = i; // initialize our ``set'' 
    // the algorithm
    while(1)
     {  // visit the current k-subset
        for(i = 0; i < k; ++i)
            printf("%d ", p[i]+1);
        printf("\n");

        if(p[0] == n-k) break; // if this is the last k-subset, we are done 

        for(i = k-1; i >= 0 && p[i]+k-i == n; --i); // find the right element 
        r = p[i]; ++p[i]; j = 2; // exchange them 
        for(++i; i < k; ++i, ++j) p[i] = r+j; // move them 
     }
    free(p);
}

参考资料

如果这不够有效，我强烈推荐 Knuth 的 Volume 4 of The Art of Comouter Programming，他在其中广泛地处理了这个问题。它可能是最好的参考资料（而且是最近的！）。

您甚至可以找到分册草稿，TAOCP 第 4 卷分册 3，生成所有组合和分区 (2005)，vi+150pp。 ISBN 0-201-85394-9，在 Knuth 的主页上（查看他 2011 年左右的新闻）。

使用 Gosper 的 Hack（银行家序列）生成所有子集

Generating all subsets using Gosper's Hack (Bankers sequence)

java

subset

一种算法，用于生成 n-set

参考资料