recursive solution for counting summations 
Author Message
 recursive solution for counting summations

Having been programming for some years, I am ashamed not being able to
solve this simple recursion problem:

        Given a positive integer N, print and count all possible
        combinations of summations of positive integers that add
        up to the given positive integer N, include N by itself.
        For example:
            given N = 1, Output
                Count           1
                combinations    1
            given N = 2, Output
                Count           2
                combinations    2
                                1 + 1
            given N = 2, Output
                Count           2
                combinations    2
                                1 + 1
            given N = 3, Output
                # 1+2 is considered a duplicate of 2+1 ...
                Count           3
                combinations    3
                                2 + 1    
                                1 + 1 + 1
            given N = 4, Output
                Count           5
                combinations    4
                                3 + 1    
                                2 + 2
                                2 + 1 + 1
                                1 + 1 + 1 + 1
        The output order of combinations doesn't matter but no duplicates
        i.e.: 1+2+1 == 2+1+1 == 1+1+2, so count and print only once.

In fact, this is from one of the data structure textbooks i believe.
No it's not my homework. Both recursion and iterative solutions
are welcome. I tried several time to solve this problem with recursion
but I could not find a good way to avoid duplications, though it seems
the problem lends itself well to a recursive solution. I suppose for
getting the Count, a static variable inside the function or a global
will do. Please help.  A working piece of function is most appreciated
but detailed pseudo code is cool too. TIA.

   -- Sam Adams
--



Tue, 08 Jul 2003 10:49:24 GMT  
 recursive solution for counting summations

Quote:

> Having been programming for some years, I am ashamed not being able to
> solve this simple recursion problem:

>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.
>         For example:
>             given N = 1, Output
>                 Count           1
>                 combinations    1
>             given N = 2, Output
>                 Count           2
>                 combinations    2
>                                 1 + 1
>             given N = 2, Output
>                 Count           2
>                 combinations    2
>                                 1 + 1
>             given N = 3, Output
>                 # 1+2 is considered a duplicate of 2+1 ...
>                 Count           3
>                 combinations    3
>                                 2 + 1
>                                 1 + 1 + 1
>             given N = 4, Output
>                 Count           5
>                 combinations    4
>                                 3 + 1
>                                 2 + 2
>                                 2 + 1 + 1
>                                 1 + 1 + 1 + 1
>         The output order of combinations doesn't matter but no duplicates
>         i.e.: 1+2+1 == 2+1+1 == 1+1+2, so count and print only once.

> In fact, this is from one of the data structure textbooks i believe.
> No it's not my homework. Both recursion and iterative solutions
> are welcome. I tried several time to solve this problem with recursion
> but I could not find a good way to avoid duplications, though it seems
> the problem lends itself well to a recursive solution. I suppose for
> getting the Count, a static variable inside the function or a global
> will do. Please help.  A working piece of function is most appreciated
> but detailed pseudo code is cool too. TIA.

>    -- Sam Adams
> --


<OT>

The count looks like the Fibonacci number series, though I could be wrong.
Let's check.

So far I have 1 2 3 5.  For 5, the next number should be 8.

Here are the combinations:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Hmmm... only 7.  Did I miss one?  So much for that theory.

</OT>

Later, Gregory Pietsch
--



Wed, 09 Jul 2003 02:01:07 GMT  
 recursive solution for counting summations

Quote:
Sam Adams writes:
>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.

The usual term for this is "partitions" of the number.  Courtesy of
<http://www.research.att.com/~njas/sequences/eisonline.html>, the
On-Line Encyclopedia of Integer Sequences, the number of partitions
for each N from 0 to 45 are:

   1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176,
   231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436,
   3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977,
   21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134

Quote:
> A working piece of function is most appreciated but detailed
> pseudo code is cool too. TIA.

Here's a working solution using sh, awk, and perl -- understand how it
works (the comments should suffice) and you can treat it as pseudocode.
The file "work" contains the list of partitions and is successively
rewritten on each pass through the outer loop, based on the previous
version "prev".  This was not written for efficiency and gets slow
pretty fast as N increases.

Working in C, you would probably prefer to do the canonicalization of
each partition immediately after generating it, rather than in a separate
pass as is done here.  I wrote it this way because it was easier.

#!/bin/sh

echo 1 >work # 1 has only the trivial partition

n=2
while [ $n -le $1 ]
do
        mv work prev
        awk <prev '
        {       # implicitly: for each line in file

                # print the line with each individual number incremented
                # (note that == is used for its numeric result, 0 or 1)
                for (i = 1; i <= NF; ++i) {
                        for (j = 1; j <= NF; ++j) {
                                printf "%d ", $j + (i == j);
                        }
                        printf "\n"
                }
                # print the line again with a 1 before it
                print 1, $0
        }' |

        # Now we have a list of partitions that is much too large,
        # containing many duplicates.  To get rid of them, first
        # canonicalize each one by sorting each list of numbers in
        # descending order:

        perl -e '
                while (<>) { # for each line in file
                        # sort the fields on the line numerically downward

                        # print them with a space after each

                        print "\n";
                }
        ' |

        # Now just eliminate repeated solutions by sorting the list of
        # lines and eliminating consecutive duplicates.  Note that this
        # is not the best presentation order once you get into multi-digit
        # numbers, since the sort is lexical rather than numeric.

        sort -u >work

        # Report

        echo "Partitions of $n:    count = "`wc -l <work`
        cat work
        echo
        n=`expr $n + 1`
done
rm prev work
--
Mark Brader               "The spaghetti is put there by the designer of
Toronto                    the code, not the designer of the language."

My text in this article is in the public domain.
--



Wed, 09 Jul 2003 02:01:25 GMT  
 recursive solution for counting summations

[snip]

Quote:
> I tried several time to solve this problem with recursion
> but I could not find a good way to avoid duplications

Try to find a representation for your solutions which you can sort
(lexicographically). Then you can just count the unique solutions.

        david

--
fortran was the language of choice for the same reason
that three-legged races are popular.
        -- Ken Thompson, "Reflections on Trusting Trust"
--



Wed, 09 Jul 2003 02:15:33 GMT  
 recursive solution for counting summations
The answer to this is called the nuymber of partitions of an integer and is
a keytopic in number theory. I did a version this once, but in a variation
of Fermat, I cant remember how.

You could do a recursive version which included duplications, like
if N = 1 answer is 1
else
for i = 1 to N-1
answer is all combos of answer(i) and answer(N-i)
- which could be faster by only doing i up to half N

you could write this as a function which returned a pointer to a list of
linked lists, like
answer(3) returns pointer to something like
X-> 3
|
X-> 2->1
|
X->1->2
|
X->1->1->1

then you deal with duplications, maybe by sorting and removing duplicates..


Quote:
> Having been programming for some years, I am ashamed not being able to
> solve this simple recursion problem:

>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.
>         For example:
>             given N = 1, Output
>                 Count           1
>                 combinations    1
>             given N = 2, Output
>                 Count           2
>                 combinations    2
>                                 1 + 1
>             given N = 2, Output
>                 Count           2
>                 combinations    2
>                                 1 + 1
>             given N = 3, Output
>                 # 1+2 is considered a duplicate of 2+1 ...
>                 Count           3
>                 combinations    3
>                                 2 + 1
>                                 1 + 1 + 1
>             given N = 4, Output
>                 Count           5
>                 combinations    4
>                                 3 + 1
>                                 2 + 2
>                                 2 + 1 + 1
>                                 1 + 1 + 1 + 1
>         The output order of combinations doesn't matter but no duplicates
>         i.e.: 1+2+1 == 2+1+1 == 1+1+2, so count and print only once.

> In fact, this is from one of the data structure textbooks i believe.
> No it's not my homework. Both recursion and iterative solutions
> are welcome. I tried several time to solve this problem with recursion
> but I could not find a good way to avoid duplications, though it seems
> the problem lends itself well to a recursive solution. I suppose for
> getting the Count, a static variable inside the function or a global
> will do. Please help.  A working piece of function is most appreciated
> but detailed pseudo code is cool too. TIA.

>    -- Sam Adams
> --


--



Wed, 09 Jul 2003 02:15:40 GMT  
 recursive solution for counting summations


Quote:
> Having been programming for some years, I am ashamed not being able to
> solve this simple recursion problem:

>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.

/*
 * This is, of course, off topic, but what the hell.
 * Phil T
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int recurse(int n, int min, int count);

char buffer[256];

int main(int argc, char *argv[])
{
  if (argc != 2 || atoi(argv[1]) == 0) {
    printf("Pass N as a parameter\n");
  }
  else {
    recurse(atoi(argv[1]), 1, 0);
  }

  return 0;

Quote:
}

int recurse(int n, int min, int count)
{
  int x;

  if (n == 0) printf("%5d : %s\n", ++count, buffer + 2);

  for (x = min ; x <= n ; x++) {
    sprintf(buffer + strlen(buffer), "+ %d ", x);
    count = recurse(n - x, x, count);
    *strrchr(buffer, '+') = '\0';
  }

  return count;

Quote:
}

--



Wed, 09 Jul 2003 02:15:48 GMT  
 recursive solution for counting summations
This is essentially the knapsack problem.
A web search under that name should turn up plenty.
--



Wed, 09 Jul 2003 02:15:51 GMT  
 recursive solution for counting summations

Quote:

>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.

 Once you're into the recursive programming mindset, it's not so hard.
Traversing the space of possible solutions is the trick, visiting each
number only once.

 The attached code finds all solutions and prints a count of them.
Recording and printing the solutions is left as an excercise to the
reader.

 Have fun,
        Frank

int
search (int left, int next)
{
  int i, total=0;

  if ((left -= next) == 0) {
    /* solution found */
    total = 1;
  }
  else {
    for (i=next; i<=left; i++) {
      total += search (left, i);
    }
  }

  return total;

Quote:
}

int
main (int argc, char *argv[])
{
  int total=0, i, what = atoi (argv[1]);

  for (i=1; i<=what; i++) {
    total += search (what, i);
  }

  printf ("%d solutions\n", total);
  return 0;

Quote:
}

--

A supermarket is where you spend half an hour hunting for instant
coffee! - Alfred E. Neuman
--



Wed, 09 Jul 2003 02:15:53 GMT  
 recursive solution for counting summations
Thanks for all who responded to this number partition problem (so
"partition" is the right term for this problem? hmm...) and all
the useful leads. I'll look into the solutions and may post a
working comple C code file once I am done for those who may ask
the same question in the future. In fact, this was in my C midterm
in year 1989 when I was a CS freshman.   -SHC
--



Thu, 10 Jul 2003 13:22:21 GMT  
 recursive solution for counting summations
Quote:

> Having been programming for some years, I am ashamed not being able to
> solve this simple recursion problem:

>         Given a positive integer N, print and count all possible
>         combinations of summations of positive integers that add
>         up to the given positive integer N, include N by itself.

[munched]

Quote:
> In fact, this is from one of the data structure textbooks i believe.

It's your question - don't you know its source?

Quote:
> No it's not my homework.

We must all be skeptics but I am not going to answer the question
as it was asked so I'm not going to sweat it.

Quote:
>  A working piece of function is most appreciated

One earlier response indicated that the question is off-topic;
it is also worth emphasizing that this is not the place to
ask for a working piece of function.

The solutions submitted count the number p(n) of partitions
of n by finding every last one of them. If only p(n) is
desired - and the value of p(n) is more interesting than an
enumeration of the partitions, unless you need such an
enumeration for an assigned problem or some other reason -
then a more efficient method of counting is available. This is
important because p(n) grows very rapidly (exp(k*sqrt(n)) for
some positive k). For that reason the solutions that have
appeared will give inaccurate counts for even small values
of n. Note: p(200) = 3972999029388.

We live in remarkable times. Aound the time of WWI, a
skilled mathematician, Major Percy MacMahon, devoted one
month to the tabulation of p(n) for 1 <= n <= 200. Nowadays
you can post a question to the wrong newsgroup and get several
answers almost immediately.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<float.h>
#include<math.h>

void partition(unsigned int, long double *);

void usage(void)
    {
     printf("usage: partitn n\n"
            "       where n is a positive decimal integer <
3000");      
     exit(EXIT_FAILURE);
    }

int main(int argc , char *argv[])
   {
    unsigned int  n;
    long double *stored_partition_data;
    char warning[] = " the lowest digits of which are inaccurate.";
       if(2 != argc || (n =(unsigned)atoi(argv[1])) > 3000)
       {
        usage();
       }
    stored_partition_data = malloc( 2*sizeof(*stored_partition_data) );
       if(stored_partition_data == NULL)
       {
        printf("\nInsufficient memory. Program will terminate.\n");
        exit(EXIT_FAILURE);
       }
    stored_partition_data[0] =  1;
    stored_partition_data[1] =  1;
    partition(n , stored_partition_data);
    printf("\nThe number of partitions of %u is %.0Lf%s\n",
                                   n, stored_partition_data[n],
            (stored_partition_data[n] < pow(10,LDBL_DIG))? "." :
warning);
    return EXIT_SUCCESS;
   }

void partition(unsigned int n, long double * ptr)
   {
     long double sum;
     unsigned int j , k;
     for( j = 1 ; j <= n ; j++)
     {  
       for( sum =  0 , k = 1 ; j >= k*(3*k - 1)/2 ; k++)
       {
         if( j >= k*(3*k + 1)/2)
           sum += (k % 2 == 1 ? 1 : -1)* (ptr[j - k*(3*k - 1)/2]
                                        + ptr[j - k*(3*k + 1)/2]);
         else  
           sum += ( k % 2 == 1  ? 1 : -1 )* ptr[j - k*(3*k - 1)/2];
       }
       ptr[j] = sum;
     }
   }  

(To reach me, replace my middle name by my first.)
--
Brian Blank                        One learns more from a good
Department of Mathematics           scholar in a rage than from a
Washington University in St. Louis   score of lucid and laborious
St. Louis, MO 63130                   drudges. --Rudyard Kipling
--



Thu, 10 Jul 2003 13:23:46 GMT  
 recursive solution for counting summations

Quote:
> One earlier response indicated that the question is off-topic;

What would have been the right group(s)?

All i knew was i wanted to write a c program to solve what i
thought was a recursion and/or data structure problem that'd
bugged me for quite a long time. I have no experience with
any math.* groups if there are any and i do think it could fit
in comp.lang.c* group(s) depending on the perspective:
mathematicians like you may view at it at the different light
than someone with my mindset. Anyway, thanks for responding
and happy new year. -sam adams
--



Sun, 13 Jul 2003 09:06:41 GMT  
 recursive solution for counting summations

Quote:
>> One earlier response indicated that the question is off-topic;
> What would have been the right group(s)?

Off-topic doesn't necessarily mean there's a better group.  It's
like saying, "You don't want my trash in your house?  Then who on
your block *would* want my trash?  You can't find someone??  Then
I'm giving *you* my trash, whether you like it or not!"

I don't really mean to call your post trash--the connotation is
not the key part of the analogy.  But it is still off-topic, whether
or not there is a better place.

Quote:
> All i knew was i wanted to write a c program to solve what i
> thought was a recursion and/or data structure problem that'd
> bugged me for quite a long time.

Your post made it seem as though you wanted someone *else* to
write that c program.  What *would* have been on-topic is an
honest attempt at solving the stated problem yourself, followed
by an explanation of what you don't understand, and where you
need help specifically.

--

--



Sun, 13 Jul 2003 22:27:51 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. recursive solution for counting summations

2. recursive treenode count function??!?

3. Recursive Solution

4. Bit Count solutions...

5. Recursive to non-recursive

6. float summation

7. HELP: Summation notation for exponential function

8. I18N Summation - is this correct

9. In VS.NET: May a solution contain other solutions

10. How can i count numbers in an int or count characters in a string in the

11. Differencies in compilation: a[count++]=count;

12. Counting the clock... (counting clock cycles)

 

 
Powered by phpBB® Forum Software