What's the most efficient algorithm for genera

问题:

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).

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}).

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)?

回答1:

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) would yield all subsets in lexicographical order:

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

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

回答2:

This can be computed using the recusrsive rule:

kSubsets(S, k) :
  k=0 or k>len(S):  {}
  else:  { for each i-th item in S: {Si} + kSubsets({Si+1,...,Sn}, k-1 }

For example:

kSubsets({1,2,3}, 2) =  {
                         {1}+kSubsets({2,3}, 1)}, 
                         {2}+kSubsets({3}, 1)}, 
                         {3}+kSubsets({}, 1)
                        } =
     = {
        {1}+{{2}+{kSubsets({3},0), {3}+kSubsets({}, 0)}}},
        {2}+{{3}+kSubsets({},0)},
        {3}+{}
       } =
     = {
        {1}+{{2}+{{}, {3}}},
        {2}+{{3}},
        {}
       } =
     = {
        {1}+{{2}, {3}},
        {2, 3}
       } =
     = {
        {1, 2}, {1, 3},
        {2, 3}
       } =
     = { {1,2}, {1,3}, {2,3} }

Note that T+P means to add the items of T to each item in P (each item in P is a set).