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