I am finding all of Combinations, _nC _r :

#include <stdio.h>

void make_combination( int n, int r ){
    for (int x=1; x<n-r 1 1; x  ){ 
        // because it is start from 1, add 1 to range, too
        for (int y=x 1; y<n-r y 1; y  ){
            for (int z=y 1; z<n-r z 1; z  ){
                printf("%d %d %d\n",x,y,z);            
            }
        }
    }
}

int main(void){
    int n, r;

    printf("Insert n : ");
    scanf("%d", &n);

    printf("Insert r : ");
    scanf("%d", &r);

    make_combination(n, r);
    return 0;
}

I want to make this to recursive function, to make it work on variable 'r' value, because I don't want fixed number of for loops.

I tried but couldn't make recursive function.

CodePudding user response：

Indeed we can use recursion to build the n-levels deep structure of the nested for loops, performing the action at the deepest level of recursion.

Or, equivalently, we can build n-1 levels and perform the last for loop explicitly, like this:

#include <stdio.h>

void rec(const char *pre, int n, int lo, int hi) {
    if (n == 0) return;
    if (n > 1) {
        for (int k = lo; k <= hi; k  ) {
            char tmp[100]; // 100 is enough for home use
            sprintf(tmp, "%s %d", pre, k);
            rec(tmp, n - 1, k   1, hi);
        }
    } else {
        for (int k = lo; k <= hi; k  ) printf("%s %d\n", pre, k);
    }
}

int main(void) {
    rec("", 3, 0, 5); // use 3 values from 0 to 5
    return 0;
}

This creates sorted triplets of numbers in the 0..5 range. Output

 0 1 2
 0 1 3
 0 1 4
 0 1 5
 0 2 3
 0 2 4
 0 2 5
 0 3 4
 0 3 5
 0 4 5
 1 2 3
 1 2 4
 1 2 5
 1 3 4
 1 3 5
 1 4 5
 2 3 4
 2 3 5
 2 4 5
 3 4 5

Replacing the call in main with rec("", 4, 0, 5); creates 4-tuples; the output is

 0 1 2 3
 0 1 2 4
 0 1 2 5
 0 1 3 4
 0 1 3 5
 0 1 4 5
 0 2 3 4
 0 2 3 5
 0 2 4 5
 0 3 4 5
 1 2 3 4
 1 2 3 5
 1 2 4 5
 1 3 4 5
 2 3 4 5

Added my thought process to write the recursive function

I know a recursivity solution is based on "reduce complexity and recurse". So I want to "solve" n loops when I know how to do n-1 loops.

How do I do 0 loops? Easy (but not helpful): do nothing

if (n == 0) return;

How do I do 1 loop? Just print the numbers

if (n == 1) for (int k = lo; k <= hi; k  ) printf("%d ", k);

How to do n loops? For each available number, save the number and recurse with 1 less loop and adjusted limits.

It was this that generated that code. After writing the code I could have studied it attentively and stream line some aspects, but decided to post as it was.