Number Divider

A.First Edition

This is the first edition of my Number Divider. It is rather a small program and the function is very simple--

giving out all possible ways of sum of a number. For example, there are 7 different ways to form number 5:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

B.Idea of program

1。 Basic idea: 

A number n can simply be summed up by 1 till n terms: say 5 can be divided into from 1 term up to 5 terms such 

that the sum of all terms are equal to 5. We eliminated 0 terms which is useless in practical life. So, I just 

write a recursive function to do the "partition" from 1 up to n. 

And in order not to give repeating ways, all number must be in a ascending order. To keep them in this order, 

I have to guarantee all terms would not be smaller than terms before. Every time, I subtract 1 from last term 

and add to previous term unless ascending order cannot hold. So, the difference between last term and its preceding

term must be at least 2, right? This seems to be correct. But my mistake just arise from here. even the difference 

is 1, it can be OK as long as this one(1) can be added into some term before. So, I write an awkward method to find 

this preceding term. 

3。 Major function

A. void doPartition(int number, int divided);

If the difference between last term and its preceding term is bigger than 1, then simply subtract one from last term and add 

it to its preceding term, then recursively call itself with number minus last term and size minus one. 

But if the difference is exactly one, it can only recursively call itself unless a previous term can be found such

that it is smaller then its sequent term. 

4。 Further improvement：

What is use of this class?

#include <iostream>

using namespace std;

const int MaxLength = 50;

class Partition
{
private:
	int lst[MaxLength];
	int length;
	void setLength(int newLength) { length = newLength;}
public:
	void initialize(int number, int divided);
	void doPartition(int number, int divided);
	void partition(int number);
	void display();
};

int counter=0;

int main()
{
	Partition P;
	P.partition(10);
	cout<<"\nThe total is:"<<counter<<endl;
	return 0;
}

void Partition::initialize(int number, int divided)
{
	for (int i=0;i <divided;i++)
	{
		lst[i] = 1;
	}
	lst[divided-1] = number -divided+1;
}

void Partition::display()
{
	counter++;
	for (int i=0; i<length; i++)
	{
		cout<<lst[i]<<"  ";
	}
	cout<<endl;
}


void Partition::partition(int number)
{
	for (int i=0;i<number; i++)
	{
		lst[i]= 1;
	}
	for (i =number; i>0; i--)
	{
		setLength(i);
		initialize(number, i);
		doPartition(number, i);
	}
}
	

void Partition::doPartition(int number, int divided)
{
	display();
	while (lst[divided-1] > lst[divided-2]&&divided>=2)
	{
		if (lst[divided-1]-lst[divided-2]>1)
		{
			lst[divided-2]++;
			lst[divided-1]--;
		}
		else
		{
			int index = divided-2;
			while (index>0&&lst[index]==lst[index-1])
			{
				index--;
			}
			if (index>0)
			{
				lst[divided-1]--;
				lst[index-1]++;
			}
			else
			{
				break;
			}
		}
		doPartition(number - lst[divided-1], divided-1);		
	}	
}


	

The following is the partition:

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 3
1 1 1 1 1 1 2 2
1 1 1 1 1 1 4
1 1 1 1 1 2 3
1 1 1 1 2 2 2
1 1 1 1 1 5
1 1 1 1 2 4
1 1 1 1 3 3
1 1 1 2 2 3
1 1 2 2 2 2
1 1 1 1 6
1 1 1 2 5
1 1 1 3 4
1 1 2 2 4
1 1 2 3 3
1 2 2 2 3
2 2 2 2 2
1 1 1 7
1 1 2 6
1 1 3 5
1 2 2 5
1 2 3 4
2 2 2 4
2 2 3 3
1 1 8
1 2 7
1 3 6
2 2 6
2 3 5
2 4 4
3 3 4
1 9
2 8
3 7
4 6
5 5
10

The total is:39