k-element subsets

[Rajesh V]

Hi,
The aim of this C++ code is to print all the k-element subsets of a set of size n. But somewhere it goes wrong - it doesn't print the answer properly. I tried a lot to find the mistake, but in vain. Please help me in debugging it and thanks in advance.

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
    printf( "Enter the number of elements of the set:\n" );
    int n;
    scanf( "%d", &n );
    printf( "Enter the elements of the set:\n" );
    vector<int> v( n );
    for( int i = 0; i < n; i++ )
    scanf( "%d", &v[i] );
    printf( "Enter the length K which is the length of the subsets to be printed: \n" );
    int k;
    scanf( "%d", &k );
    int s = ( 1 << k ) - 1;
    while( !( s & ( 1 << n ) ) )
    {
    printf( "\n" );
    for( int i = v.size() - 1; i >= 0; i-- ) 
    {
        if( (s & (  1 << i )) != 0 )
        {
        printf( "%d ", v[i] );
        }
        int lo = s & ~( s - 1 ); // last one bit
        int lz = ( s + lo ) & ~s; //last zero bit above lo
        s |= lz; // setting the bit
        s &= ~( lz - 1 ); // clearing bits below lz
        s |= ( lz >> ffs(lo) ) - 1; // adding proper number of bits at the end
    }
    }
    printf( "\n" );
    return 0;
}
 
 

[JosAH]

You can do much better than that; basically you want C(n, k) n >= k; the numbers make up the index values of the elements of your set. The following function computes the next combination (lexicographically) given a current sequence of k numbers out of a set of n. If no such combination can be found anymore it'll return false otherwise true is returned. Have a look:

int combine(int* c, int k, int n) {
 
    for (int i= k; --i >= 0;) {
        if (++c[i] <= n-(k-i)) {
            while (++i < k)
                c[i]= c[i-1]+1;
            return 1;
        }
    }
    return 0;
}
 

kind regards,

Jos