Generate combinations of k numbers in an array with ordering constraints

Question

This is one of the questions from my midterm exam.

Please trace the following program. Modify this program to write a recursive program int combinations(A, n, k) that you can print out all the combinations of k numbers out of n different numbers stored in an array A with additional rules of:

(1) the order of A[0], A[1], ..., A[n-1] must remain and

(2) the sequence of these k numbers must be in an increasing order.

For example, assume there are four numbers 4, 1, 2, 3 stored in array int A[4]. Calling this recursive function combinations(A, 4, 2) will return a count 3 and print out (1, 2), (1, 3) and (2, 3), or calling combinations(A, 4, 3) will return a count 1 and print out (1, 2, 3).

Your recursive program must consider to avoid the unnecessary recursive function calls.

Teacher gave the following code as the hint:

#include <stdio.h>
#define N 4
int boolfunc(int *var, int m);
int recursivebool(int *var, int n);
int main(){
    int varbool[20];
    recursivebool(varbool, N);
}
int boolfunc(int *var, int m){
    int result=var[0], i;
    for (i=1; i<m; i++) result = (result && var[i]);
    return result;
}

int recursivebool(int *var, int n){
    int localvar[20], i, j;
    if (n == 0){
        for(i=0; i<N; i++) printf("%d ", var[i]);
        printf("%d\n", boolfunc(var, N));
        return;
    }
    for (j=0; j<=1; j++) {
        var[n-1] = j;
        recursivebool(var, n - 1);
    }
}

If we run this program we can get output like this:

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

I can understand the hint program. And I need to use this concept to write int combination(int *A, int n, int k) like the question asked. As what I know, if k is 2, I can use this concept to find the scenario that have two 1 with two 0 like this:

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

Then, we can find the numbers from corresponding index of 1 and exam the numbers to see if they are in the increasing order.

I tried so hard to solve this question. But it's too difficult.

Answer 1

You can approach this as a simple constraint satisfaction problem and use recursive backtracking to solve the constraints.

As you mention, we can naively generate all the possible combinations, then retroactively pick the ones we want, but then we've done a lot of useless work which the assignment correctly prohibits.

A solution is to break off the recursive search as soon as a violation of a constraint is detected and try a different possibility. If we ever reach a point where we've satisfied all the constraints for the sequence, we print the result. Ideally, we'd return an array of results, but not having to do so makes it easier to focus on the algorithm.

In terms of satisfying the constraints, we can do so by using a start index to fulfill the i < j requirement. If we add a number to an in-progress result, the result array must be empty or the existing element at the tail of the array is less than the element we're trying to add. Beyond that, we have our base case of k.

#include <stdio.h>

void print_arr(int len, int *a);

int combinations_recurse(int *a, int n, int k, int *selected, 
                         int selected_len, int start) {
    if (selected_len == k) {
        print_arr(selected_len, selected);
        return 1;
    }

    int selected_count = 0;

    for (int i = start; i < n; i++) {
        if (!selected_len || selected[selected_len-1] < a[i]) {
            selected[selected_len] = a[i];
            selected_count += combinations_recurse(a, n, k, 
                selected, selected_len + 1, start + 1);
        }
    }

    return selected_count;
}

int combinations(int *a, int n, int k) {
    int selected[n];
    return combinations_recurse(a, n, k, selected, 0, 0);
}

int main() {
    int a[] = {4, 1, 2, 3};
    printf("count: %d\n\n", combinations(a, 4, 2));
    printf("count: %d\n", combinations(a, 4, 3));
    return 0;
}

void print_arr(int len, int *a) {
    printf("[");
    for (int i = 0; i < len - 1; printf("%d, ", a[i++]));
    if (len) printf("%d]\n", a[len-1]); 
    else puts("]");
}

Output:

[1, 2]
[1, 3]
[2, 3]
count: 3

[1, 2, 3]
count: 1