Generator(2)

A.Second Edition

This is the  second edition of my Generator class. It now generates partition solution to a set. This costs me 

a lot of time to figour out. 

B.Idea of program

1。 Basic idea: 

How to partition an array? I originally want to use recursive method to do the job. It is coming from the 

recursive formula which I solve for the number of partition. But it turned out too complicated. After torture of

several days, I remember that separator idea can solve the partition and it is the simplest idea! Suppose there is

n elements in an array, then there are n-1 space between each two adjacent elements. Imagine one separator is put

on any these n-1 position will divide array into two partitions. And up to n-1 separators could be put to get 

up to n subsets. Then the ways of all these partitions together are all the partitions of this array. Of course, 

don't forget one last partition which are the set itself. 

So, based on this idea, I internally use the combination generating method to do the length-1 combinations. Or

C(n-1, 1), C(n-1, 2), ... C(n-1, n-1).  And finally I separately output all elements in set to give the whole as

a partition as my combination method cannot work with 0.

Before call chooseNumber method, I changed length to length-1, and set isInternal true which allow partition 

output. These are not elegant!!! But I cannot give a better solution.

3。 Major function

A. void partition();

It first set length to length-1 and isInternal to be true. At end of function, set them back.

4。 Further improvement：

All methods need to design a better user interface for people to use it easily.

#include <iostream>

using namespace std;

const int MaxNumber =100;

class Generator
{
private:
	bool isCombination;
	bool isInternal;
	int array[MaxNumber];
	int length;
	int nextDigit();
	int findSmallest(int next);
	void swapIndex(int a, int b);
	void formTail(int next);
	void output();
	void initialize(int number);
	void chooseNumber(int number, int start = 0);	
	void plugNumber(int start, int number);
	bool advance(int index);
	void outputPartition();
protected:
	void doGenerator();
	void doCombination();
public:
	Generator(int number =10, bool combination=false);
	void setLength(int number);
	int getLength() { return length;}	
	void slotMachine();
	void partition();
	void choose(int number);
};


int main()
{
	Generator P(5, true);

	P.partition();

	return 0;
}


void Generator::outputPartition()
{
	for (int i=0;i<length;i++)
	{
		if (array[i]==1)
		{
			cout<<i<<", ";
		}
	}
	cout<<endl;
}

void Generator::partition()
{
	setLength(length-1);
	isInternal = true;
	for (int i=1; i<length;i++)   //the length is length-1;
	{
		chooseNumber(i);
	}
	for (i =0; i< length; i++)
	{
		cout<<i<<", ";
	}
	cout<<endl;
	setLength(length+1);
	isInternal = false;	
	
}


void Generator::plugNumber(int start, int number)
{
	for (int i=start; i< length; i++)
	{
		array[i]= number;
	}
}

void Generator::chooseNumber(int number, int start)
{
	if ((number< length - start) && number>0&& start< length)
	{
		array[start] = 0;
		chooseNumber(number, start +1);
		array[start] = 1;
		chooseNumber(number -1, start+1);
	}
	else
	{
		if (number>=length - start)
		{
			plugNumber(start, 1);
			output();
			plugNumber(start, 0); //restore
		}
		else
		{
			if (number==0)
			{
				plugNumber(start, 0);
				output();
			}	
		}
	}
}




void Generator::choose(int number)
{
	chooseNumber(number);
}

void Generator::doCombination()
{
	int index =0;
	while (true)
	{
		while (array[index])
		{
			array[index] = 0;
			index++;
			if (index==length)
			{
				return;
			}
		}
		array[index] = 1;

		output();	

		index =0;
	}
}

void Generator::doGenerator()
{
	int next =0;
	int small =0;
	while ((next = nextDigit()) != -1)
	{
		small = findSmallest(next);
		swapIndex(next, small);
		formTail(next);
		output();
	}
}

Generator::Generator(int number, bool combination)
{
	setLength(number);
	isInternal = false;
	isCombination = combination;
	initialize(number);
}


void Generator::output()
{
	if (isInternal)
	{
		outputPartition();
		return;
	}
	if (!isCombination)
	{
		cout<<"\nThis is the Permutation:\n";
	
	}
	else
	{
		cout<<"\nThis is the Combination:\n";
	}
	for (int i=0; i< length; i++)
	{
		cout<<array[i]<<(i==length - 1?";":",");
	}
}


void Generator::slotMachine()
{
	output();
	if (!isCombination)
	{
		doGenerator();
	}
	else
	{
		doCombination();
	}
}



void Generator::formTail(int next)
{
	int start = next +1;
	int end = length -1;
	while (end > start)
	{
		swapIndex(start, end);
		start++;
		end--;
	}
}

void Generator::swapIndex(int a, int b)
{
	int temp;
	temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}

int Generator::findSmallest(int next)
{
	int small = length -1;
	while (array[next]> array[small])
	{
		small--;
	}
	return small;
}


void Generator::setLength(int number)
{
	if (number>1)
	{
		 length = number;		 
	}
}




int Generator::nextDigit()
{
	int next = length -2;
	while (array[next]> array[next+1])
	{
		next--;
		if (next<0)
		{
			return -1;
		}
	}
	return next;
}


void Generator::initialize(int number)
{
	if (!isCombination)
	{
		for (int i=0; i< length; i++)
		{
			array[i]= i;
		}	
	}
	else
	{
		for (int i=0; i< length; i++)
		{
			array[i]= 0;
		}
	}
}

This is the permutation:
0,1,2,3;
This is the permutation:
0,1,3,2;
This is the permutation:
0,2,1,3;
This is the permutation:
0,2,3,1;
This is the permutation:
0,3,1,2;
This is the permutation:
0,3,2,1;
This is the permutation:
1,0,2,3;
This is the permutation:
1,0,3,2;
This is the permutation:
1,2,0,3;
This is the permutation:
1,2,3,0;
This is the permutation:
1,3,0,2;
This is the permutation:
1,3,2,0;
This is the permutation:
2,0,1,3;
This is the permutation:
2,0,3,1;
This is the permutation:
2,1,0,3;
This is the permutation:
2,1,3,0;
This is the permutation:
2,3,0,1;
This is the permutation:
2,3,1,0;
This is the permutation:
3,0,1,2;
This is the permutation:
3,0,2,1;
This is the permutation:
3,1,0,2;
This is the permutation:
3,1,2,0;
This is the permutation:
3,2,0,1;
This is the permutation:
3,2,1,0;

This is the Combination:
0,0,0,0;
This is the Combination:
1,0,0,0;
This is the Combination:
0,1,0,0;
This is the Combination:
1,1,0,0;
This is the Combination:
0,0,1,0;
This is the Combination:
1,0,1,0;
This is the Combination:
0,1,1,0;
This is the Combination:
1,1,1,0;
This is the Combination:
0,0,0,1;
This is the Combination:
1,0,0,1;
This is the Combination:
0,1,0,1;
This is the Combination:
1,1,0,1;
This is the Combination:
0,0,1,1;
This is the Combination:
1,0,1,1;
This is the Combination:
0,1,1,1;
This is the Combination:
1,1,1,1;

The following is the partition:( How to interpret it? You see that in an array of 5 elements, each line is one

kind of partition. The number in each line represents that counting from no.0 elements, up to which subscript of

elements are included in a subset. For example, "2,3" means that 0,1,2 elements in array is in first subset, 3

is in second subset, 4 is in third subset. Why is this? Because the number "2,3" means put a separator at place

after element 2(subscript 2 equal to number 3 element), and a separator after element 3(equal number 4 element).

So, you see the number is really the position of separators which do the job of partition of an array.

3,
2,
1,
0,
2, 3,
1, 3,
1, 2,
0, 3,
0, 2,
0, 1,
1, 2, 3,
0, 2, 3,
0, 1, 3,
0, 1, 2,
0, 1, 2, 3,