Combinations of given number that add up to X

This is a discussion on Combinations of given number that add up to X within the C Programming forums, part of the General Programming Boards category; Hi, Though it shouldn't be really difficult, I've been kind of stuck with this. I need to make a function, ...

  1. #1
    Zze
    Zze is offline
    Registered User
    Join Date
    Dec 2012
    Posts
    4

    Combinations of given number that add up to X

    Hi,

    Though it shouldn't be really difficult, I've been kind of stuck with this. I need to make a function, that computes and shows all the possible combinations (without repetition) of given number, where the digits (that only range from 1 to 9) of every combination give a specified sum when added.


    I guess it's not the clearest explanation, so here is an example: Calculate all sets of 5 numbers (from 1 to 9) that add up to 28.


    I would be really grateful, if someone could explain this.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,307
    Read this.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    Use recursion ...

    The sets of 5 numbers (1 to 9) that add up to 28 include:
    : the number 1 plus the sets of 4 numbers (2 to 9) that add up to 27
    : the number 2 plus the sets of 4 numbers (3 to 9) that add up to 26
    ...
    : the number 5 plus the sets of 4 numbers (6 to 9) that add up to 22

    ...

    Note that I've made the numbers "go" into sets in ascending order; this way there is no repetition in the recursive calls.
    Last edited by qny; 12-02-2012 at 05:22 AM.

  4. #4
    Zze
    Zze is offline
    Registered User
    Join Date
    Dec 2012
    Posts
    4
    I read it, but I really can't see a way of doing this.
    At least, I would like to know if I need to calculate ALL the combinations, and then filter the ones that don't match the sum, or is there a faster way?

  5. #5
    Registered User
    Join Date
    Nov 2012
    Posts
    1,100
    Quote Originally Posted by Zze View Post
    Calculate all sets of 5 numbers (from 1 to 9) that add up to 28.
    How many possibilities are there? If the number of possibilities is small, then an exhaustive search is feasible:

    1 + 1 + 1 + 1 + 1 = ?
    1 + 1 + 1 + 1 + 2 = ?
    1 + 1 + 1 + 1 + 3 = ?
    ...
    9 + 9 + 9 + 9 + 9 = ?

    For which combinations does the sum equal 28? If a combination gives 28, then print it out. All combinations which are printed out should give you the answer you are looking for.

  6. #6
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Assume you use digits 0 to 9. You then have 105 five-digit combinations, from 00000 to 99999.
    In general, if you have N digits, where each digit can have B different values, you have BN unique combinations.

    If you omit the repetitions, the first digit can have B different values, the second B-1 different values, and so on. For five decimal digits, this would be 10*9*8*7*6 = 30240.
    In general, if you have N digits, where each digit can have B different values, you have B!/(B-N)! unique combinations where the digits do not repeat.

    (Edited: I noticed the sum of the digits was another constraint.)

    As you realized, there are two basic approaches: one where you check every possible combination and discard those that are not acceptable results, and another where you only generate the correct results. Both are equally valid, but I'd recommend first searching for the nonrepeating digit combinations, and discarding those that do not result in the correct sum.

    The key is to find a way to represent each tentative solution using a single integer. (I've mentioned in another thread that this is basically ordering your result set. The order itself is not important, but the fact that you do order them is.)

    To convert a number solution between 0 and (B! / (B - N)! - 1), you can use pseudocode:
    Code:
        # solution is the integer specifying the current solution.
        # 0 yields the first, 1 the second, and so on.
        solution = 0
    
        # digitlist contains the unused digits
        digitlist := [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
    
        # digits is the number of digits to use in the combination
        digits := 5
    
        # result is a string describing the formula
        result := ""
    
        # sum is the sum of the digits.
        sum := 0
    
        # Loop to generate each digit in the solution:
        for digit := 1 to digits
    
            # We have len(digitlist) digits. Current digit index is (% = modulo operator)
            i := solution % len(digitlist)
    
            # Remove the used part from the integer specifying the solution
            solution := solution / len(digitlist)
    
            # Add digit to sum
            sum := sum + digitlist[i]
    
            # and to result string.
            result := result " + " digitlist[i]
    
            # Remove digit from digitlist
            delete digitlist[i]
    
        end for
    
        # Note: three first characters in result are " + ",
        # which you could remove here.
    
        # Note: solution > 0 here, if it was initially larger than
        # the total number of actual solutions.
    
        # return the sum of the digits, and the result string.
        return sum, result
    Note that you should use a temporary array for digitlist, as you will be modifying it. I wrote the example in pseudocode, because I hoped it would be easier for you to understand than the C version. It would be too tempting to simply use it without understanding; at least this way, you need to understand the technique before you can use it.

    The above will return the combination corresponding to integer solution. You could have an outer loop over all possible values (or until solution becomes too large, as noted at the end of the pseudocode above). Discard those that yield the wrong sum, and print those that yield the correct results.
    Last edited by Nominal Animal; 12-02-2012 at 10:24 AM.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is Sunday, traditionally a non-work day, so we pull the answers right out of our asses.

    j/k

    This can be brute force searched in about 1 second.

    let's say you have an int array a[5], and you set it to the lowest possible combination of digits equal to 28: 11899, but you wanted the number to be reversed, so it looked just like this, instead of like:
    Code:
    int a[5]={1,1,8,9,9};
    which when incremented the normal way, would be:
    21899
    31899
    41899
    etc.
    Not what I wanted, so I used
    Code:
    a[5]={9,9,8,1,1},
    which when viewed the normal way, displays as:

    11899
    11911
    11912
    11913
    etc.
    Code:
     
    length = 5;
    
    while(k<length) {
       while(a[0] < 10)
          if(a[4]+a[3]+a[2]+a[1]+a[0]==28) 
             for(m=4;m>-1;m--)   //print it reversed, and work from it reversed
                printf("%d",a[m])   //"normal" number format
             printf("\n")
             //getchar()
             count++      
          }
          increment a[0]
       }
       decrement a[0]   //one too far, back up
    
       //adjust the higher columns (index number) of digits
       k=0;
       while(a[k]==9)  //find the next digit < 9
          ++k     
    
       ++a[k]             //and increment it
    
       //reset all the lower index numbers, to their lowest possible value 1.
       j=k-1;
       while(j>-1)
          a[j]=1; 
          --j;
    
       i=0;     //and move back to the right most digit
    }
    
    print out your total permutations whose digits equaled 28
    This isn't the easiest or the fastest way of finding the answer, but it's very easy to check if your logic is going right, since it's in this "digital odometer" format.

    This is a program that, when you have completed it, You should keep it around.

    Even on a Sunday. <smile>

  8. #8
    Zze
    Zze is offline
    Registered User
    Join Date
    Dec 2012
    Posts
    4
    @qny
    Thank you for the idea. I've written this, but aside from the little problems, my main issue is how can "send" the correct vector and linked list from one recursive call to another, in order to fill them with correct data.

    Code:
    typedef struct _comb{                                    /*linked list struct that includes all the combinations*/
        int combi[8];
        struct _comb *next;    
    }comb;
    
    comb  *recursive(int p, int n, int l, comb *lp){         /*p - given sum, n - size of set, l - smallest of the numbers that can be used to form a set (the biggest is always 9), lp - linked list*/
        int i, j;
        int cmb[8];                                          /*vector for the set of numbers*/
        
        for(j = 0; j < 8; j++)                               /*initialization of the vector for the digits*/
            cmb[j] = 0;
        j = 0;
        
        n--;
        for(i = l; i<=8; i++){
            l++;
            if(n == 1){
                if((l - 1) == p){
                    cmb[j] = p;
                    return lp;
                }
                else
                    return lp;
            }
            
            recursive(p - l, n, l + 1, lp);
            
            j++;
            cmb[j] = l - 1;
        }
        /* INSERT THE VECTOR WITH A COMBINATION IN THE LIST */
        
        return lp;
    }

    Should I make the function void? In which case how do I manage the linked list? Also is it possible to make an "external" for cycle where I put my recursive function, instead of implementing it in the function?
    Last edited by Zze; 12-02-2012 at 06:43 PM.

  9. #9
    Zze
    Zze is offline
    Registered User
    Join Date
    Dec 2012
    Posts
    4
    Thanks for the suggestions everybody! However I can't repeat numbers in a combination, i.e. this 155 is an invalid set of 3 for the sum 11

  10. #10
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,388
    OK, so...

    Your minimum input is 15 and your maximum input is 35

    I think that bruit force is the best way for a task this small.

    i.e. Have an array of 5 numbers

    Have a function which finds the next combination -> Must not have repeated numbers

    if it doesn't have repeated numbers, find the sum

    if the sum == input, print it out on the screen.
    Fact - Beethoven wrote his first symphony in C

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Here is a different approach, one that assumes 1 + 3 + 7 + 8 + 9 = 28 and 3 + 1 + 7 + 8 + 9 = 28 are considered the same solution (as only the order of the terms changes).

    You have N digits that may appear at most once in the sum. (They either do not appear, or appear exactly once). Therefore, you have 2N possible sums. You can order these sums, these proposed solutions, using a single unsigned integer, where the first bit is set if the first digit is a term in the sum, the second bit is set if the second digit is a term in the sum, and so on. Of the 2N values, only those values that have a binary representation with exactly five bits set, and sum to 28, are solutions. This turns out to consider a rather small superset of solutions -- for nine digits, it tests only 29 = 512 possible solutions.

    This approach only beats my previous suggestion when 2numbers <= numbers! / (numbers - terms)!, as otherwise the other proposed superset (based on combinations), is smaller. For example, for sums with 5 terms, this approach is more efficient if you have between 5 and 21 numbers or digits to choose from.

    The following program supports up to one less digit (number) than the number of bits in an unsigned long. You supply the number of terms, the desired sum, and each number or digit (possible term in the sum) as command line parameters. The program will complain if the inputs overflow or do not otherwise make sense:
    Code:
    #include <stdio.h>
    #include <limits.h>
    #include <string.h>
    
    #ifndef   ULONG_BITS
    #define   ULONG_BITS (CHAR_BIT * sizeof (unsigned long))
    #endif /* ULONG_BITS */
    
    int main(int argc, char *argv[])
    {
        long            number[ULONG_BITS];
        long            term[ULONG_BITS];
        long            total, sum;
        unsigned long   proposal, solutions, left;
        int             numbers, terms, i, n;
        char            dummy;
    
        if (argc < 5 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
            fprintf(stderr, "\n");
            fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
            fprintf(stderr, "       %s TERMS SUM N1 [ N2 .. ] NN\n", argv[0]);
            fprintf(stderr, "\n");
            fprintf(stderr, "This will output the number of unique sums\n");
            fprintf(stderr, "totaling SUM when TERMS nonrepeating terms\n");
            fprintf(stderr, "from the specified set, N1 to NN, are summed.\n");
            fprintf(stderr, "\n");
            return 0;
        }
    
        numbers = argc - 3;
        if (numbers < 2) {
            fprintf(stderr, "Too few numbers specified.\n");
            return 1;
        }
        if (numbers >= (int)ULONG_BITS) {
            fprintf(stderr, "Too many numbers specified (max %d).\n", (int)ULONG_BITS - 1);
            return 1;
        }
    
        if (sscanf(argv[1], " %d %c", &terms, &dummy) != 1) {
            fprintf(stderr, "%s: Invalid number of terms in the sums.\n", argv[1]);
            return 1;
        }
        if (terms < 2) {
            fprintf(stderr, "%s: Too few terms in the sums.\n", argv[1]);
            return 1;
        }
        if (terms >= numbers) {
            fprintf(stderr, "%s: Too many terms in the sums.\n", argv[1]);
            return 1;
        }
    
        if (sscanf(argv[2], " %ld %c", &total, &dummy) != 1) {
            fprintf(stderr, "%s: Invalid total; not an integer.\n", argv[2]);
            return 1;
        }
    
        for (i = 0; i < numbers; i++)
            if (sscanf(argv[i+3], " %ld %c", &number[i], &dummy) != 1) {
                fprintf(stderr, "%s: Invalid number; not an integer.\n", argv[i+3]);
                return 1;
            }
    
        /* There are 2**numbers possible solutions in the superset containing
         * the desired solution. */
        proposal = 1UL << numbers;
    
        /* No solutions found yet. */
        solutions = 0UL;
    
        while (proposal-- > 0UL) {
    
            /* Each bit in 'left' refers to each 'number'. */
            left = proposal;
    
            /* Sum matching this proposal. */
            sum = 0L;
    
            /* 'n' is the number of terms in the sum. */
            n = 0;
    
            /* 'i' corresponds to the bit number at the least significant position. */
            i = 0;
    
            while (left && i < numbers && n < terms) {
    
                /* Was bit 'i' set in 'proposal'? */
                if (left & 1UL) {
    
                    /* Yes, add number 'i' to the sum. */
                    term[n] = number[i];
                    sum += number[i];
    
                    /* A number was added to the sum. */
                    n++;
                }
    
                left >>= 1UL;
                i++;
            }
    
            /* For 'proposal' to be a true solution:
             *    'sum' must equal 'total'
             *    'n' must equal 'terms'    (i.e. 'terms' numbers used)
             *    'left' must be zero       (exactly 'terms' bits in 'proposal' set)
            */
            if (sum != total || n != terms || left)
                continue;
    
            /* 'proposal' matches a true solution. */
            solutions++;
    
            printf("Solution %lu. %ld", solutions, term[0]);
            for (i = 1; i < terms; i++)
                printf(" + %ld", term[i]);
            printf(" = %ld\n", sum);
        }
    
        printf("Found %lu solutions.\n", solutions);
    
        return 0;
    }
    This has the nice side effect of being able to work on any numbers as terms in the sum, not just decimal digits. For example, if you compile the above to ./combinations, then running
    Code:
    ./combinations 3 0  -9 -8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8 9
    outputs all the 32 possible combinations of three nonrepeating nonzero positive or negative decimal digits that sum to zero.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Fill this with the non-repeating numbers you want, and add the checks for sum equal to whatever you want.

    The output isn't in order, but getting all combinations never was easier.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void printIt(int *n, int max);
    
    int main(void) {
       unsigned long long count=0;
       int n[4]={1,2,3,4};
       int i,j,temp,max=4;
    
       int *p=malloc((max+1)*sizeof(int));
       for(i=0;i<max+1;i++)
          p[i]=i;
    
       temp=0;
       i=1;
       printIt(n,max);
       count=1;
       while(i<max) {
          p[i]--;
          if(i%2==1) {
             j=p[i];
          }else {
             j=0;
          }
          temp = n[i];
          n[i] = n[j];
          n[j] = temp;
          i=1;
          printIt(n,max);
          count++;
          while(p[i]==0) {
             p[i]=i;
             i++;
          }
       }   
    
       printf("Enumerated Combinations: %llu \n",count);
       return 0;
    }
    void printIt(int *n, int max) {
       int i;
       
       for(i=0;i<max;i++) {
          printf("%d ",n[i]);
       }
       putchar('\n');
    }

  13. #13
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    Quote Originally Posted by Zze View Post
    ... my main issue is how can "send" the correct vector and linked list from one recursive call to another
    Basically change the vector/linked list before you call the recursive function and change it back afterwards.
    When the recursive function reaches the base case, just print the result (or save it in some other variable that doesn't get changed back)

    Code:
            /* change vector/list */
            recursive();
            /* change back */

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 03-18-2012, 03:05 PM
  2. All combinations
    By JonathanS in forum C Programming
    Replies: 38
    Last Post: 10-15-2011, 04:48 PM
  3. Generating number combinations
    By litzkrieg in forum C Programming
    Replies: 23
    Last Post: 03-01-2011, 10:25 AM
  4. computing the number of combinations
    By clover in forum C Programming
    Replies: 34
    Last Post: 06-06-2004, 01:12 PM
  5. Replies: 10
    Last Post: 01-07-2002, 03:03 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21