c - How can i find all combinations of K elements of a given set of N elemets without a recursion?

Question

I tried to program something in C but it goes too deep for me…

I have studied a relevant paper "A CONTROL STRUCTURE FOR A VARIABLE NUMBER OF NESTED LOOPS, Skordalakis, Papakonstantinou", I have tried to transfer the flow chart proposed in C, but it is not possible with structured programming. The idea should be something like:

b1 = 1; 
    
for (m = 1 ; m <= K ; m++) {
   for (i[m] = b[m] ; i[m] <= n; i[m]++) {
        if ( m < K ) {
            a[m] = i[m];
            b[m+1] = i[m] + 1;
            break;
        }
        a[m] = i[m];
        if ( i[m] < n ){
            i[m] = i[m] + 1;
            m = m - 1;
            continue;
        }
    }
}

i is the control variable for every loop (an array), b is the starting parameter for every loop (an array again) and the a array holds every combination. I have seen some solutions to similar problems that they use a boolean flow control variable (also proposed in the paper).

Can somebody advise?

Answer 1

Here is one possible solution that just occured to me.

Given a set of n elements, we can represent a choice of k elements as a binary number.

For example, with n=6 and k=2, we could choose the second and last elements:

010001

We could just enumerate the binary numbers of n digits, and discard the ones that don't have exactly k ones.

For example, with n=4 and k=2.

0000
0001
0010
0011 ?
0100
0101 ?
0110 ?
0111
1000
1001 ?
1010 ?
1011
1100 ?
1101
1111

But that's too many wasted iterations.

So I thought about making a sequence that generates only the numbers with exacly k ones. For Example, with n=6 and k=3, I would enumaterate as follows:

1 1 1 0 0 0 
1 1 0 1 0 0 
1 0 1 1 0 0 
0 1 1 1 0 0 
1 1 0 0 1 0 
1 0 1 0 1 0 
0 1 1 0 1 0 
1 0 0 1 1 0 
0 1 0 1 1 0 
0 0 1 1 1 0 
1 1 0 0 0 1 
1 0 1 0 0 1 
0 1 1 0 0 1 
1 0 0 1 0 1 
0 1 0 1 0 1 
0 0 1 1 0 1 
1 0 0 0 1 1 
0 1 0 0 1 1 
0 0 1 0 1 1 
0 0 0 1 1 1 

If you take some time to think about it, you will start to understand how the algorithm would work.

We initialize the array with all the(k) ones at the beginning. We are shifting them to the end in some way, and we keep going until all the ones are at the end.

Try to implement that yourself without looking at the solution: https://ideone.com/aY9YBl