生成n个集合的所有k个子集的最有效算法是什么? [英] What's the most efficient algorithm for generating all k-subsetsof an n-set?

问题描述

我们给了一组 n 个元素，我们想生成该集合的所有 k 个子集.例如，如果 S = {1,2,3} 和 k = 2 ，则答案将是 {1,2}，{1,3 }，{2,3} (顺序不重要).

We are given a set of n elements and we'd like to generate all k-subsets this set. For example, if S={1,2,3} and k=2, then the answer would be {1,2}, {1,3}, {2,3} (order not important).

存在 n 集(定义为:-)的 {n选择k} k 个子集，即 > O(n ^ k)(尽管这并不严格).显然，解决该问题的任何算法都必须及时运行 Omega({n select k}).

There are {n choose k} k-subsets of an n-set (by definition :-), which is O(n^k) (although this is not tight). Obviously any algorithm for the problem will have to run in time Omega({n choose k}).

目前已知最快的算法可以解决此问题?可以真正实现 {n选择k} 的下限吗(这样我们就有了一个本质上最优的算法)?

What is the currently fastest known algorithm for this problem? Can the lower bound of {n choose k} actually be achieved (so that we have an essentially optimal algorithm)?

推荐答案

可以使用一些众所周知的位魔术来生成所有子集(以long的二进制表示形式编码):

There is some well-known bit magic you could use for producing all subsets (encoded in the binary representation of a long):

long getNextSubset(long subset){
   long smallest = subset& -subset;       
   long ripple = subset + smallest;    
   long ones = subset ^ ripple;       
   ones = (ones >> 2)/smallest; 
   subset= ripple | ones;    
   return subset;
}

void printAllSubsets(int n, int k){
    long MAX=1L<<n;
    long subset=(1L<<k)-1L;
    while((MAX&subset)==0){
         System.out.println(Long.toString(subset, 2));
         subset=getNextSubset(subset);
    }
}

printAllSubsets(4,2)将按字典顺序生成所有子集:

printAllSubsets(4,2) would yield all subsets in lexicographical order:

[00]11
[0]101
[0]110
1001
1010
1100

优点是该代码的缺点是速度很快-不适用于64个以上的对象.

The advantage is, that this code is pretty fast, the downside - it does not work for more than 64 objects.

这篇关于生成n个集合的所有k个子集的最有效算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！