recursive solution for counting summations
Author |
Message |
Sam Adam #1 / 12
|
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 |
|
|
Gregory Pietsc #2 / 12
|
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 |
|
|
Mark Brad #3 / 12
|
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 |
|
|
David Rubi #4 / 12
|
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 |
|
|
Walter Milne #5 / 12
|
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 |
|
|
Phil Tregonin #6 / 12
|
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 |
|
|
Douglas A. Gwy #7 / 12
|
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 |
|
|
Frank Pilhof #8 / 12
|
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 |
|
|
Sam Adam #9 / 12
|
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 |
|
|
Brian Evan Blan #10 / 12
|
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 |
|
|
Sam Adam #11 / 12
|
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 |
|
|
naisb.. #12 / 12
|
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 |
|
|
|