Container

    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。

>        B. void Partition::display()

>        要显示每一个成员，实际上只要每一个从mylist继承下来的类，在onDisplay函数实现以下，就可以了，我原来为了检验，进行三重

>        循环遍历，效果和一句调用lst.display()是一样的。

    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