CODEWITHSUNDEEP
carrays
Martin
Martin

Reputation: 19

Print all decreasing combinations of int array in C

I have an int array and i need to print all possible decreasing combinations which are starting with the highest number. Here's the example:

int array[MAX_LEN]={ 5 , 4 , 3 , 2 , 1 }

and the expected output: 

5 , 4 , 3 , 2 , 1  
5 , 4 , 3 , 2   
5 , 4 , 3 , 1  
5 , 4 , 2 , 1  
5 , 3 , 2 , 1  
5 , 2 , 1  
.  
.  
5 , 1  
.  
.  
5

Can someone give me an advice how to do it? Thanks

Upvotes: 0

Views: 152

Answers (2)

rcgldr
rcgldr

Reputation: 28921

To display n things 3 at a time, you can cycle using 3 indexes:

    for(i = 0; i < n-3; i++)
        for(j = i+1; j < n-2; j++)
            for(k=j+1; k < n-1; k++)
                // display array[i], array[j], array[k]

To generalize this to display n things for k = 1 to n things at a time (this is the outer loop), with an iterative (looping non recursive) method you can use an array of indexes such as ai[n]. Then for k things at a time, you need to replace the nested loops with code that accomplishes the same thing using k indexes starting with ai[0] = 0, ai[1] = 1, ... ai[k-1] = k-1. The ranges of the indexes will be ai[0] goes from 0 to n-k, ai[1] goes from ai[0]+1 to n-k+1, ..., ai[k-1] goes from ai[k-2]+1 to n-1. The indexes are advanced like an odometer, with ai[k-1] being the least significant digit, and ai[0] being the most significant digit.

This will give you all the combinations. If they need to be in descending order, you could sort the original array or sort a copy of the original array.

The generic name for this type of function is "next combination". Example code:

#include <stdio.h>
#include <malloc.h>

int next_combination(size_t *I, size_t k, size_t n)
{
size_t i, j;
    i = k-1;                            /* find next element to increment */
    while(I[i] == (n-k+i)){
        --i;
        if(i == (size_t)-1){            /* if done, */
            for(i = 0; i < k;  i++)     /*  return initial combination */
                I[i] = i;
            return(0);
        }
    }
    I[i] += 1;                          /* increment element */
    for(j = i+1; j < k; j++)            /* create increasing string */
            I[j] = I[i]+j-i;
    return(1);                          /* return with new combination */
}

int main(int argc, char **argv)
{
int    A[5] = {5, 4, 3, 2, 1};
size_t I[5];
size_t i, k, n;
    n = sizeof(A)/sizeof(A[0]);         /* n things */
    for(k = n; k; k--){                 /* n things k at a time */
        for(i = 0; i < k;  i++)         /* create initial combination */
            I[i] = i;
        do{                             /* display combinations */
            for(i = 0; i < k; i++)
                printf("%2d", A[I[i]]);
            printf("\n");
        }
        while(next_combination(I, k, n));
    }
    return(0);
}

Upvotes: 0

aioobe
aioobe

Reputation: 421160

This problem can be expressed as "for each subsequence of [4,3,2,1] print 5 followed by the subsequence"

To find all subsequences, you can do something along the following lines

findAllSubsequences(array) {
    if (array is empty)
        return an empty list

    result = new list

    head = array[0]      // 4
    tail = array[1...]   // [3, 2, 1]

    tailSubsequences = findAllSubsequences(tail)  // recurse on tail

    // Add all subsequences that don't include head
    // [3,2,1] [3,1] [2,1] ...
    result.addAll(tailSubsequences)

    // Add all subsequences that do include head
    // [4,3,2,1] [4,3,1] [4,2,1] ...
    for each subsequence s in tailSubsequences
        result.add(head concatenated with s)

    return result
}

Upvotes: 1

Related Questions