Partitions of a set

Post date: Nov 28, 2013 1:07:45 AM

در این پست برنامه‌ای هست که تعداد افرازهای یه مجموعه n عضوی رو چاپ می‌کند. همه افرازهای مجموعه {1,2,3} این‌ها هستند:

{{1,2,3}}

{{1,2},{3}}

{{1,3},{2}}

{{1},{2,3}}

{{1},{2},{3}}

پس یک افراز برای مجموعه {1,2,3} همه دسته بندی‌های اعضای آن است. دانستن یک نکته خیلی ضروری است. ترتیب، برای اعضایی که بین { و } قرار می‌گیرند مهم نیست. پس

{1,2} = {2,1}

و

{{1,3},{2}} = {{2},{1,3}} = {{2},{3,1}}

پس برنامه باید فقط یکی از این مجموعه‌های مساوی را چاپ کند.

افراز برای مجموعه‌های n عضوی شبیه مثال سه عضوی بالاست.

اگر با مفهوم مجموعه مشکل دارید، مسئله را می‌شود به شکل دیگری بیان کرد: فرض کنید n سکه با قطرهای مختلف داریم که روی میز از بزرگ به کوچک روی هم چیده شد‌ه‌اند. این n سکه را به چند صورت می‌شود در دسته‌های چندتایی روی میز چید که سکه پایینی بزرگ تر از بالایی باشد:

در این شکل 5 حالت ممکن از چیدن سه سکه روی میز نشان داده شده است. می‌بینید که همه این حالت‌ها متناظر با 5 افرازی است که در بالا نشان داده شده است.

حالا برنامه‌ای که افرازهای یک مجموعه n عضوی را چاپ می‌کند:

#include <conio.h>

#include <iostream>

#include <vector>

using namespace std;

template<typename type>

class Set

{

public://

vector<type> v;

bool Contains(type element)

{

unsigned size = v.size();

for(unsigned i = 0; i < size; i++)

{

if(element == v[i])

return true;

}

return false;

}

//-------------------------------------------

void Empty()

{

v.clear();

}

//-------------------------------------------

void NotMultiple()

{

for(unsigned i = 0; i < v.size(); i++)

for(unsigned j = i + 1; j < v.size(); j++)

{

if(v[i] == v[j])

{

v.erase(v.begin() + j);

j--;

}

}

}

//-------------------------------------------

void// Pop()

{

v.pop_back();

}

//-------------------------------------------

bool Push(type element)

{

if(!Contains(element))

{

v.push_back(element);

return true;

}

return false;

}

//-------------------------------------------

unsigned Size()

{

return v.size();

}

//-------------------------------------------

type& operator [](unsigned i)

{

if(Size() <= i)

i = Size() - 1;

return v[i];

}

//-------------------------------------------

bool operator == (Set<type> set)

{

vector<type> v1 = v;

vector<type> v2 = set.v;

while(true)

{

if(v1.size() == 0)

{

if(v2.size() == 0)

return true;

else

return false;

}

bool found = false;

for(unsigned i = 0; i < v2.size(); i++)

{

if(v1[0] == v2[i])

{

v2.erase(v2.begin() + i);

found = true;

}

}

if(found == false)

return false;

v1.erase(v1.begin());

}

return true;

}

public:

Set(vector<type> v)

:v(v)

{

NotMultiple();

}

//-------------------------------------------

Set()

{

}

};

class Partitioner

{

vector<int> set;

public:

Set<Set<Set<int> > > SSS;

void Print()

{

unsigned size_sss = SSS.Size();

for(unsigned k = 0; k < size_sss; k++)

{

cout<< "{";

unsigned size_ss = SSS[k].Size();

for(unsigned j = 0; j < size_ss; j++)

{

cout<< "{";

unsigned size_s = SSS[k][j].Size();

for(unsigned i = 0; i < size_s; i++)

{

cout<< SSS[k][j][i];

if(i < size_s - 1)

cout<< ",";

}

cout<< "}";

if(j < size_ss - 1)

cout<< ",";

}

cout << "}\n";

}

}

//------------------------------------------

void Run()

{

unsigned size = set.size();

unsigned i = size - 1; /* sweeper item can be any number between 0 & size - 1 */

if(size == 0)

return;

Set<Set<int> > SS;

Set<int> S;

S.Push(set[i]);

SS.Push(S);

if(size == 1)

{

SSS.Push(SS);

return;

}

vector<int> subset;

for(unsigned j = 0; j < size; j++)

{

if(i != j)

subset.push_back(set[j]);

}

Partitioner P(subset);

unsigned P_size = P.Size();

for(unsigned k = 0; k < P_size; k++)

{

unsigned size_k = P[k].Size();

for(unsigned j = 0; j <= size_k; j++)

{

bool change = P[k][j].Push(set[i]);

SSS.Push(P[k]);

if(change)

P[k][j].Pop();

}

bool change = P[k].Push(S);

SSS.Push(P[k]);

if(change)

P[k].Pop();

}

}

//------------------------------------------

unsigned Size()

{

return SSS.Size();

}

//------------------------------------------

Set<Set<int> >& operator[](unsigned i)

{

if(Size() <= i)

i = Size() - 1;

return SSS[i];

}

public:

Partitioner(vector<int> set)

{

Set<int> S(set);

this -> set = S.v;

Run();

}

};

int main()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4); // v1 = {1,2,3,4}

Partitioner P(v1);

P.Print();

cout<< P.Size();

_getch();

}

Output:

{{1,2,3,4}}

{{1,2,3},{4}}

{{1,2,4},{3}}

{{1,2},{3,4}}

{{1,2},{3},{4}}

{{1,3,4},{2}}

{{1,3},{2,4}}

{{1,3},{2},{4}}

{{1,4},{2,3}}

{{1},{2,3,4}}

{{1},{2,3},{4}}

{{1,4},{2},{3}}

{{1},{2,4},{3}}

{{1},{2},{3,4}}

{{1},{2},{3},{4}}

15

در این برنامه، کلاس Set یک مجموعه را شبیه سازی می‌کند با خاصیت مهمی که گفتم: ترتیب در مجموعه مهم نیست. تساوی‌ای که در کلاس Set تعریف شده مجموعه‌های مساوی را با توجه به عدم اهمیت ترتیب معین می‌کند. این تساوی مهم ترین علت نوشتن این کلاس است. البته می‌شد از کلاس‌های استاندارد هم برای این کار استفاده کرد.

علت استفاده از

Set<Set<Set<int> > > SSS;

این است که مجموعه همه افرازها، یک مجموعه است؛ هر افراز هم مجموعه است و هر افراز شامل چند مجموعه است. پس سه دسته تو در تو از مجموعه‌ها داریم.

این برنامه از بازگشت استفاده می‌کند و نوشتن برنامه بدون استفاده از بازگشت شاید کاری بسیار سخت و طاقت فرسا باشد. اما شاید همین مفهوم بازگشت را بشود با لیست‌ها، بازسازی کرد به طوری که دیگر نشود اسمش را بازگشت گذاشت.