生成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屋!