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.

Expand|Select|Wrap|Line Numbers

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

Expand|Select|Wrap|Line Numbers

 
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

k-element subsets

re: k-element subsets

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about