Representing a natural number as a sum of natural numbers?

[Landoro]

Hey guys! It's been a long time since I visited daniweb,but I need some help understanding something.A friend of mine gave me problem to solve, but the assignment is strange,I can't seem to find the actually meaning of what I need to generate as an answer.Here goes:

By a given natural number n ,find all the possible unordered representations of n as a sum of natural numbers. The ouput must be lexicographical.

Ok,lexicographical would mean alphabetically,which is exactly like the words orderd in dictionaries. So how does this work for numbers?
Let's say the number 6:

1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+1+4
1+5
I have no idea if this is the correct way. Give me some clues,because there is a deadline I want to get this over with. The teacher who gave this problem to my friend told her she needs to be careful about repetitions and that the output is going to be massive,so it's best to print it to a file,and that's the only clue given about assignment . I am posting a code I found ,but it does not output exactly what I need.

#include<stdio.h>

void show(int length, int *psdata){
 int i;

 for(i=1;i<length;i++)
  printf("%d+",psdata[i]);
 printf("%d\n",psdata[length]);
}

void func(int n, int pos, int *pdata){
  int k;
  for(k=n;k>=1;k--)
    {
  if(n!=k){
   pdata[pos]=k;
   if(pdata[pos]<=pdata[pos-1])
    func(n-k, pos+1, pdata);
  }
  else{
   pdata[pos]=k;     
   if(pdata[pos]<=pdata[pos-1])
    show(pos, pdata);
  }
 }
}

int main(){
 int num, *data;

 printf("Enter number: ");
 scanf("%d",&num);
 data = (int*)malloc(sizeof(int)*num);

 data[0]=num+1;

 func(num,1, data);
  system("pause");
 return 0;
}

[ddanbe]

Click Here
What about 1+2+3 ?

[Landoro]

Yes,it must be valid,and it seems lexicographic,but how to generate them all,there must be a correct pattern ?

[Landoro]

Ook , now I did some digging and found out that lexicographical representation is exactly what the code I posted does.
http://oeis.org/wiki/Orderings
Now the only thing left to do is make it print the result in reverse order? How to reverse the recursion in the code so that I get 1+1+1+1+1+1 and end up to 5 + 1 and finish with 6 ?

[jephthah]

so you want us to rework some code for your "friend's" homework assignment, and to hurry up about it, and to do it in a way that satisfies the teacher's requirements.

sounds legit.

[raptr_dflo]

I'm not going to go into the code you "found" that does some of what you want. The purpose of the assignment is to write your own, starting with an understanding of what you are trying to accomplish (or what your friend is trying to accomplish, as the case may be).

Starting with terminology: you've got "sum of natural numbers" down, leaving unordered (1+1+4 is different from 1+4+1 is different from 4+1+1 -- ordered would choose one of those as a preferred ordering, and the others would be considered identical), and as you determined lexicographic means, essentially, "as it would be sorted in a dictionary," though even that is somewhat arbitrary if N is greater than 9, as you have to decide whether "10" should be sorted between "1" and "2", or after "9".

As for the rest of the problem, if you note that a sum of natural numbers adding to N is either N itself, or the sum of (a) some number T1 between 1 and N-1 (inclusive) and (b) the sum of some other natural numbers adding up to (N - T1), you can probably deduce the rest of the algorithm. Recursion is well-suited to this problem, but not strictly necessary. If you choose to use it, you will have a function that at some point calls itself (in a way which is guaranteed to terminate!):

void nameThisSomethingUseful(int *terms_so_far, int num_terms_so_far, int remaining_sum_to_achieve)
{
    if (remaining_sum_to_achieve == 0) {
        /* this is a special case, what do you need to do here? */
    }
    else {
        ...
        /* want all partial sums that start with some value k (how do you choose this?) */
        /* add k to the list of terms */
        /* call this function again with: 
             the revised list of terms (including revised number of terms),
             and revised remaining sum to achieve */
        nameThisSomethingUseful(terms_so_far, num_terms_so_far+1, remaining_sum_to_achieve-k);
        ...
    }
}