What is the most efficient algorithm for generating all k-subsets of an n-set?

Question

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

There are {n choose k} k-subsets of an n-set (by definition :-) such that O (n ^ k) (although this is not hard). Obviously, any algorithm for the task must be executed in Omega time ({n choose k}).

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

Answer 1

, ( ):

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

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

, , - 64 .

Answer 2

, recusrsive:

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

:

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

, T + P T P ( P ).