At its basic, I want to generate all the numbers from 0 .. N; that have M bits set. Ie. N=5, M=3, generate:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100
[download]

But not necessarily in that particular order. Ie. order is immaterial so long as they are all generated.

What I don't want to do is iterate 0 .. N and then count the bits and then eliminate.

More to the point, what I really need is the positions of the set bits, not the numbers containing them.

Update: What I actually want is the indices of the set bits; Ie. the second group of numbers in each line below:

11100 [0 1 2]
11010 [0 1 3]
11001 [0 1 4]
10110 [0 2 3]
10101 [0 2 4]
10011 [0 3 4]
01110 [1 2 3]
01101 [1 2 4]
01011 [1 3 4]
00111 [2 3 4]
[download]

Final complication is that this will be called from Inline::C, for speed, which means calling back into Perl for each iteration would be expensive. In other words, it'll need to be coded in C.

As C doesn't like returning multiple values; and cannot construct functions-on-the-fly the way we often do with Perl; the interface I'm thinking of is:

typedef struct {
    int N, M;
    char *posns.
} POSNS;

POSNS *initGenerator( int N, int M ) {
     POSNS *p = malloc( sizeof( POSNS ) );

     p->N = N; p->M = M; p->posns = malloc( M );

     for( i = 0; i < M; ++i ) p->posns[ i ] = N - M + i;
     return posns;
}

char *iterGenerator( POSNS *p ) {
    if( done) {
        free( p->posns );
        free( p );
        return NULL;
    }
    // modify p->posns;
    ...
    return p->posns;
}

POSNS p = initGenerator( n, m );

while( c = iterGenerator( p ) ) {
    // use c[].
}
[download]

I think this is going to be an odometer pattern iterator; possibly recursive; but beyond that my mind is blank.

I can convert a Perl solution to C, but it would need to avoid things that can't be done in C, (like generating subs on the fly).

Thoughts? Suggestions? Condemnations :)