Partition Generator

A.第三版

这个小程序应该是动态数组的第三个版本吧，或者说他的应用吧？并且我觉得更应该归类为发生器的序列。对模板类作了三个子类，分别是整数子类

IntList和整数子类的指针所组成的子类PtrList，以及整数指针的指针所组成的子类NodeList。

并写了一个Partition的发生器类，里面有一个NodeList对象，他的每一个元素PtrList就是一个partition,而若干个整数如果出于同一组的话，

那么就存在同一个IntList里。

1。 程序基本说明：当mylist加入的是指针的话，你自然不想让他排序，不然地址排序会变得乱七八糟，所以，我把add函数改了一下，加了一个

	是否排序的参数。同样，find函数也必须加这个参数。结果就是直接在最后一个位置加这个元素进数组。

   	关于partition的发生原理，其实，在我的在我的partition数量递归公式里就体现出了。一个新元素x加入到原来的n-1的集合里，假定

	原来的集合有f(n-1)个partitions, x或者以一个独立的subset形式与f(n-1)个partition进行union组成的每一个集合就是新的n个

	元素的集合的新的partitions。或者x与每一个f(n-1)的partition的每一个subset结合成新的subset，然后这个partition也成为

	一个新的partition。如：3个元素的partition有（a，b，c），（ab，c），(ac,b),(bc,a), (abc)；那么新加一个元素d,首先，

	d作为一个独立子集和每一个partition进行union:（a,b,c,d),(ab,c,d),(bc,a,d),(ac,b,d),(abc,d)；其次，是和每一个

	partition里的每一个子集union再组成partition：（ad,b,c),(a,bd,c),(a,b,cd),   (abd,c),(ab,cd),(acd,b),(ac,bd),

	(bcd,a),(bc,ad),(abcd)；然后，这两种partition再union组成所有的partitions.

2。 程序思路：其实我心里一直对递归调用比较抵触，因为，代码虽然好看，也容易写，可是，对效率实在是不负责任。可是，没有办法，我暂时

	还想不出怎样改。

3。 主要函数介绍：

	A. void Partition::addNumber(int number)

	这个函数是做什么用的？这个就是新加一个元素number时候，怎样生成新的partition,里面PtrList的一个方法

	addNumber(int index, int number)，这个函数生成一个新的PtrList并拷贝原来的所有数据，并且在index指定的IntList里加入

	一个number。	

4。 不足之处：

	A. partition(int number)的参数实际上是number+1,不过，我懒得改了。

	B. 会不会有人不明白怎样使用generator这类的发生类？很可能，所以，我还要写一个遍历每一个partition的方法，以便输出这些

	序列号，以供调用者引用这些数组下标，明白了吗？

#include <iostream>
#include <iomanip>

using namespace std;

template<class T>
class mylist
{
private:
	T *flist;
	int LENGTH;
	int SIZE;
	int counter;
	int bruteForce(T ptr);
protected:
	void uninitialize();
	void initialize();
	bool checksize();
	void expand();
	int locate(T ptr);
	virtual void onRemove(T ptr);  //
	virtual void onDisplay(T ptr);  //derived class must implement their own methods
public:	
	mylist();
	~mylist();
	void add(T ptr, bool sorted=true);
	bool find(T ptr, bool sorted=true);
	void display();
	int count();
	T& items(int index);
	void insert(int index, T ptr);
	void remove(int index);
};

//int list
class IntList: public mylist<int>
{
protected:
	void onDisplay(int ptr);
public:
	IntList& operator=(IntList& dummy);
};

//int* list	
class PtrList: public mylist<IntList*>
{
protected:
	void onRemove(IntList* ptr);
	void onDisplay(IntList* ptr);
public:
	PtrList* addNumber(int index, int number);
	IntList* addItem();
};


//int** list
class NodeList: public mylist<PtrList*>
{
protected:
	void onRemove(PtrList* ptr);
	void onDisplay(PtrList* ptr);
};

class Partition
{
private:
	NodeList lst;
	void addNode();
	void addPtr(int node);
	void addItem(int node, int ptr, int data);
	void addNumber(int number);
	int nodeCount();
	int ptrCount(int node);
	int itemCount(int node, int ptr);
public:
	void partition(int number);
	void display();
};


class Container
{
private:
	void onVisitItem(int data);
	void onVisitNode(IntList* ptr);
	PtrList lst;
	void addNumber(int number);
	void multiplyNumber(int number);
public:
	int nodeCount();
	int itemCount(int node);
	void addItem(int node, int data);
	int getItem(int node, int index);
	void eachNode();
	void eachItem(int node);
	void traverse();
};



int main()
{
	
	Partition P;
	P.partition(4);
	P.display();

	return 0;
}

void Partition::display()
{
	lst.display();
	/*
	int number=0;
	for (int i=0; i<lst.count(); i++)//PtrList*
	{
		cout<<"Partition: ";
		for (int j=0; j<lst.items(i)->count(); j++) //IntList*
		{
			cout<<" group "; 
			for (int k=0; k<lst.items(i)->items(j)->count(); k++)//int
			{
			
				cout<<lst.items(i)->items(j)->items(k)<<"  ";
			}
			cout<<"\t";
		}
		cout<<endl;
		number++;
	}
	cout<<"total number is:"<<number<<endl;
	*/
}

void Partition::addNumber(int number)
{
	int oldCount= lst.count();
	IntList* ptr;
	PtrList* oldPtr, * newPtr;
	for (int i=0; i< oldCount; i++)
	{
		oldPtr = lst.items(i);
		for (int j=0; j<oldPtr->count(); j++)
		{
			newPtr = oldPtr->addNumber(j, number);			
			lst.add(newPtr, false);
		}
		ptr = new IntList;
		ptr->add(number);
		oldPtr->add(ptr, false);
	}
}



void Partition::addNode()
{
	PtrList* ptr = new PtrList;
	lst.add(ptr, false);
}

void Partition::addPtr(int node)
{
	if (node<nodeCount())
	{
		IntList* ptr= new IntList;
		lst.items(node)->add(ptr, false);
	}
	else
	{
		cout<<"Exceed max node!"<<endl;
	}
}

void Partition::addItem(int node, int ptr, int data)
{
	if (node<nodeCount())
	{
		if (ptr<lst.items(node)->count())
		{
			lst.items(node)->items(ptr)->add(data);
		}
	}
	else
	{
		cout<<"Exceed max node or ptr!"<<endl;
	}
}


int Partition::nodeCount()
{
	return lst.count();
}

int Partition::ptrCount(int node)
{
	if (node<lst.count())
	{
		return lst.items(node)->count();
	}
	else
	{
		return -1;
	}
}

int Partition::itemCount(int node, int ptr)
{
	if (node<lst.count())
	{
		if (ptr<lst.items(node)->count())
		{
			return lst.items(node)->items(ptr)->count();
		}
	}
	return -1;
}



void Partition::partition(int number)
{
	if (number==0)
	{
		addNode();
		addPtr(0);
		addItem(0, 0, 0);
	}
	else
	{
		partition(number -1);
		addNumber(number);
	}
}

void Container::traverse()
{
	for (int i=0; i<lst.count(); i++)
	{
		eachItem(i);
	}
}

void Container::eachItem(int node)
{
	cout<<"node is:"<<node<<endl;
	cout<<"and itemcount is:"<<lst.items(node)->count()<<endl;
	onVisitNode(lst.items(node));
}

void Container::onVisitItem(int data)
{
	cout<<data<<endl;
}

void Container::onVisitNode(IntList* ptr)
{
	for (int i=0; i< ptr->count(); i++)
	{		
		onVisitItem(ptr->items(i));
	}
}

int Container::itemCount(int node)
{
	return lst.items(node)->count();
}

int Container::nodeCount()
{
	return lst.count();
}




void Container::addItem(int node, int data)
{
	if (node <lst.count())
	{
		lst.items(node)->add(data);
	}
	else
	{
		cout<<"The node number is exceeding max!"<<endl;
	}
}

int Container::getItem(int node, int index)
{
	return lst.items(node)->items(index);
}

void IntList::onDisplay(int data)
{
	cout<<data<<"  ";
}

IntList& IntList::operator =(IntList& dummy)
{
	for (int i=0; i<dummy.count(); i++)
	{
		add(dummy.items(i), false);
	}
	return *this;
}

void NodeList::onDisplay(PtrList* ptr)
{
	cout<<"one partition is:\n";
	ptr->display();
	cout<<endl;
}

void NodeList::onRemove(PtrList* ptr)
{
	delete ptr;
}

void PtrList::onRemove(IntList* ptr)
{
	delete ptr;
}

IntList* PtrList::addItem()
{
	IntList* ptr = new IntList;
	add(ptr, false);
	return ptr;
}

void PtrList::onDisplay(IntList* ptr)
{
	cout<<"group: ";
	ptr->display();
	cout<<"   ";
}

PtrList* PtrList::addNumber(int index, int number)
{
	PtrList * ptr = new PtrList;
	for (int i=0; i< count(); i++)
	{
		*(ptr->addItem()) = *(items(i));
		if (i==index)
		{
			ptr->items(i)->add(number);
		}
	}
	return ptr;
}


template<class T>
void mylist<T>::onRemove(T ptr)
{
}

template<class T>
void mylist<T>::remove(int index)
{
	int temp= index;
	if (index<counter)
	{
		onRemove(items(index));
		while (temp<counter-1)
		{	
			
			items(temp) = items(temp+1);
			temp++;	
		}
		counter--;
	}
}

template<class T>
void mylist<T>::insert(int index, T ptr)
{
	if (!checksize())
		expand();

	if (counter == 0)
	{
		items(0) = ptr;
		counter++;
	}
	else
	{
		if (index>=0&& index<=counter)
		{
			int i=index;
			T hold1 = items(index), hold2= items(index+1);
			while (i<counter)
			{	
				hold2 = items(i+1);
				items(i+1) = hold1;
				hold1 = hold2;				
				i++;
			}
			items(index) = ptr; //any exception trap???
			counter++;
		}
	}
}
			
template<class T>
int mylist<T>::locate(T ptr)
{
	int index = 0;
	while (items(index) <ptr &&index <counter)
	{
		index++;
	}
	return index;
}

template<class T>
int mylist<T>::bruteForce(T ptr)
{
	for (int index=0; index<counter; index++)
	{
		if (items(index)==ptr)
		{
			break;			
		}
	}
	return index;
}

template<class T>
bool mylist<T>::find(T ptr, bool sorted)
{
	int index = 0;
	if (sorted)
	{
		index = locate(ptr);
	}
	else
	{
		index = bruteForce(ptr);
	}
	if (index == counter)
	{
		return false;
	}
	else
	{
		return (items(index) == ptr);
	}
}


template<class T>
int mylist<T>::count()
{
	return counter;
}

template<class T>
T& mylist<T>::items(int index)
{
	return flist[index];
}

template<class T>
void mylist<T>::onDisplay(T ptr)
{
//	cout<<ptr;
}


template<class T>
void mylist<T>::display()
{
	cout<<setiosflags(ios::showpoint|ios::fixed);
	for (int i = 0; i < counter; i ++)
	{
		onDisplay(flist[i]);
	}
}

template<class T>
void mylist<T>::uninitialize()
{
	for (int i=0; i<counter; i++)
	{
		onRemove(items(i));
	}
	free(flist);
}

template<class T>
mylist<T>::~mylist()
{
	uninitialize();
}


template<class T>
void mylist<T>::add(T ptr, bool sorted)
{ 
	if (sorted)
	{
		int index;
		index = locate(ptr);
		if (items(index)!=ptr)
		{
			insert(index, ptr);
		}
	}
	else
	{
		insert(counter, ptr);
	}
}

template<class T>
void mylist<T>::initialize()
{
	LENGTH = 10;
	SIZE = LENGTH;
	if ((flist =(T*)(malloc(sizeof(T) * SIZE)))==NULL)
	{
		//exception need to be handled here!!
		cout<<"Unable malloc memory for size of "<<SIZE<<endl;  		
	}
	counter = 0;
}

template<class T>
bool mylist<T>::checksize()
{
	return (counter < SIZE);
}

template<class T>
void mylist<T>::expand()
{
	SIZE += LENGTH;
	if ((flist = (T*)(realloc(flist, sizeof(T) * SIZE)))== NULL)
	{
		cout<<"Unable realloc memory for mylist of size "<<SIZE<<endl;
	}
}

template<class T>
mylist<T>::mylist()
{
	initialize();
}

The following is the output which is quite unpleasing.

one partition is:
group: 0     group: 1     group: 2     group: 3     group: 4     
one partition is:
group: 0  1     group: 2     group: 3     group: 4     
one partition is:
group: 0  2     group: 1     group: 3     group: 4     
one partition is:
group: 0     group: 1  2     group: 3     group: 4     
one partition is:
group: 0  1  2     group: 3     group: 4     
one partition is:
group: 0  3     group: 1     group: 2     group: 4     
one partition is:
group: 0     group: 1  3     group: 2     group: 4     
one partition is:
group: 0     group: 1     group: 2  3     group: 4     
one partition is:
group: 0  1  3     group: 2     group: 4     
one partition is:
group: 0  1     group: 2  3     group: 4     
one partition is:
group: 0  2  3     group: 1     group: 4     
one partition is:
group: 0  2     group: 1  3     group: 4     
one partition is:
group: 0  3     group: 1  2     group: 4     
one partition is:
group: 0     group: 1  2  3     group: 4     
one partition is:
group: 0  1  2  3     group: 4     
one partition is:
group: 0  4     group: 1     group: 2     group: 3     
one partition is:
group: 0     group: 1  4     group: 2     group: 3     
one partition is:
group: 0     group: 1     group: 2  4     group: 3     
one partition is:
group: 0     group: 1     group: 2     group: 3  4     
one partition is:
group: 0  1  4     group: 2     group: 3     
one partition is:
group: 0  1     group: 2  4     group: 3     
one partition is:
group: 0  1     group: 2     group: 3  4     
one partition is:
group: 0  2  4     group: 1     group: 3     
one partition is:
group: 0  2     group: 1  4     group: 3     
one partition is:
group: 0  2     group: 1     group: 3  4     
one partition is:
group: 0  4     group: 1  2     group: 3     
one partition is:
group: 0     group: 1  2  4     group: 3     
one partition is:
group: 0     group: 1  2     group: 3  4     
one partition is:
group: 0  1  2  4     group: 3     
one partition is:
group: 0  1  2     group: 3  4     
one partition is:
group: 0  3  4     group: 1     group: 2     
one partition is:
group: 0  3     group: 1  4     group: 2     
one partition is:
group: 0  3     group: 1     group: 2  4     
one partition is:
group: 0  4     group: 1  3     group: 2     
one partition is:
group: 0     group: 1  3  4     group: 2     
one partition is:
group: 0     group: 1  3     group: 2  4     
one partition is:
group: 0  4     group: 1     group: 2  3     
one partition is:
group: 0     group: 1  4     group: 2  3     
one partition is:
group: 0     group: 1     group: 2  3  4     
one partition is:
group: 0  1  3  4     group: 2     
one partition is:
group: 0  1  3     group: 2  4     
one partition is:
group: 0  1  4     group: 2  3     
one partition is:
group: 0  1     group: 2  3  4     
one partition is:
group: 0  2  3  4     group: 1     
one partition is:
group: 0  2  3     group: 1  4     
one partition is:
group: 0  2  4     group: 1  3     
one partition is:
group: 0  2     group: 1  3  4     
one partition is:
group: 0  3  4     group: 1  2     
one partition is:
group: 0  3     group: 1  2  4     
one partition is:
group: 0  4     group: 1  2  3     
one partition is:
group: 0     group: 1  2  3  4     
one partition is:
group: 0  1  2  3  4