Following is my question:
Write C++ function that finds all possible ways of dividing n
apples among k persons. 
For example, when n=3 and k=3 function should print:

     person1 person2 person3
	0	0	3
	0	1 	2
	0	2	1
	0	3	0
	1	0	2
	1	1	1
	1	2	0
	2	0	1
	2	1	0
	3	0	0

I tried to solve this problem and found this much:
number of columns= number of persons
sum of row in each row= number of persons

I have tried to write my function following way:

void dividingApple(int apples, int persons) 
//apples >=0 and persons >=1
{
   int i;  // counter of for loop
    if(person == 1)  // when person = 1, only one way to divie apples!
    {
	cout << "     Person1" << endl;
	cout << '\t' << apples << endl; 	
    }
    else if(apple == 0) // When apple=0, all persons get 0 apples!
    {   
	cout << "    ";
	for (i = 1; i <= persons; i++)
	   cout << "Person" << i << '\t';
        cout << endl;
    }
    else
    {
      // I have trouble in this part. Please help me to complete
      // this function.
	
    } 	 	
}

After completing above function, I need help to analyse its time complexity
also, but if you don't like to give analysis of time complexity that's ok. If 
you think there another efficient way to write function than I have started
you are welcome.

---

Clarification of Question by fastfun-ga on 07 Sep 2004 16:20 PDT

Thanks for giving interest on my question,

It's nice to have in ordered pattern, but order does not matter. Condition is
that we can not break apple into piece (numbers should be integer). I am simply
looking for output of all possible divisions among all persons. This
possibility includes 0 also i.e. person do not get any one, that is
also possibility, right? (0, 1, 2, 3,  .... upto number of apples!)

And I am sorry,
"Sum of column in each row = number of apples" is correct.

"sum of row in each row= number of persons" is wrong!
(If you see example above, each row totals 3 because we are dividing 3 apples.)
Thanks.

---

Request for Question Clarification by mathtalk-ga on 07 Sep 2004 16:23 PDT

Hi, fastfun-ga:

I could point you to the Pricing Guidelines, but $4.50 will not often
buy much in the way of programming.  However a Researcher may take a
special interest in your Question.

I'll suggest one approach to writing the function using recursion. 
The "basis" case is k = 1.  Only one solution is possible, namely
attributing all n apples to the one person.

Now consider a method for reducing the problem of k+1 persons to that
involving k persons.  Decide how many (between 0 and n) of the
remaining apples to give the first person.  Then after deducting that
number (say m) from the pool of apples, call the function to determine
the ways to distribute n-m apples among the other k persons.

There's a clever way to think about how many such solutions there are.
 Imagine the n apples to be set out in a row, and suppose that we have
at our disposal k-1 "posts" that can be placed among the apples. 
These posts act as dividers so that we obtain k distinct "groupings"
of the apples (some possibly containing no apples, as two posts might
be placed next to one another).  Looking left to right, the first
person gets all the apples in the first group, and so on.

Now consider the number of arrangements of the n apples and k-1 posts.
 The apples are indistinguishable from one another, and the posts also
indistinguishable.  Thus there are:

(n + k - 1)! / ( n! (k - 1)! )

distinct arrangements, or C(n+k-1,n) = combinations of n+k-1 things
taken n at a time.

regards, mathtalk-ga

Does the order matter?

I mean for example if we have:

1 2 0
2 0 1

are they to be considered as different solution, or they are
duplicates and should be treated as one?

Cosmin Banu

Judging by the example of n = 3, k = 3 fully sketched above,
fastfun-ga intends that "order" does matter.  The two specific
solutions 1 2 0 and 2 0 1 are indeed listed as distinct.

The name for such solutions is ordered partitions of an integer n
(apples) into k summands (persons receiving apples), and a function
which returns the set of all such solutions is often provided by
computer algebra packages.  See for example:

[GAP Manual: Ordered Partitions]
http://www-gap.dcs.st-and.ac.uk/~gap/Gap3/Manual3/C046S014.htm

There is a technical difference between the function implemented above
and the one which fastfun-ga has asked about.  GAP's
OrderedPartitions(n,k) provides solutions containing only positive
summands, where fastfun-ga wishes to entertain summands that allow
nonnegative summands (zero as well as positive integers).  Results for
one problem are easily related to those for the other by the simple
expedient of contributing an extra one to each summand in the
nonnegative version, or subtracting one from each summand in the
positive version.  Of course the "total" n is adjusted up or down by k
accordingly.

regards, mathtalk-ga