همه ما با مفهوم زیر مجموعه (subset) آشناییم, اما در اینجا مفهوم دیگری با نام اصل تناظر یک به یک داریم که به این شکل تعریف میشود:

اصل تناظر یک به یک: هر گاه بتوان به هر عضو مجموعه ی A یک و فقط یک عضو از مجموعه ی B و به هر عضو مجموعه ی B یک و فقط یک عضو از مجموعه ی A را متناظر کرد, آنگاه تعداد اعضای مجموعه ی B و A برابرند. در این حالت میگوییم بین مجموعه های  B و A  تناظر یک به یک برقرار است.

در این مثال هر زیر مجموعه را به یک رشته از صفرها و یک ها متناظر میکنیم. فرض کنید مجموعه ی n عضوی را به یک رشته ی n تایی از صفر و یک ها متناظر کنیم که در آن عضو i ام  رشته متناظر با عضو i ام مجموعه است که صفربودن کاراکتر i ام نشان دهنده ی نبود عضو i ام مجموعه  در زیر مجموعه و یک بودن کاراکتر i ام در رشته نشان دهنده ی وجود عضو i ام مجموعه در زیرمجموعه است. چون میدانیم به ازای هر رشته با این ویژگی یک زیر مجموعه وجود دارد و برعکس, پس طبق اصل تناظر یک به یک تعداد زیر مجموعه ها با تعداد رشته ها برابر است.

در این الگوریتم از یک رشته ی n+1 تایی استفاده شده که از n تا از کاراکترها برای تناظر یک به یک با زیرمجموعه ها و از یک کارکتر دیگر برای چک کردن  تولید تمام رشته های ممکن از صفر و یک استفاده شده است که  یک شدن آن نشان دهنده ی اتمام تولید تمام رشته های n تایی ممکن از صفر و یک هاست.

تولید تمام رشته های ممکن: برای این کار از جمع باینری اعداد بصورت کارکتری استفاده شده است. آرگومان اول رشته و آرگومان دوم یک واحد کمتر از تعداد اعضای مجموعه است چون شماره گذاری از صفر تا۱- (n+1) انجام میشود.

مثال:

  {a, b, c} -> مجموعه

“۰۰۰۰″ –> {} شروع الگوریتم –>  زیرمجموعه ی اول

“۰۰۰۱″ –>{c}  زیرمجموعه ی دوم

“۰۰۱۰″ –>{b} زیرمجموعه ی سوم

“۰۰۱۱″ –>{b, c} زیرمجموعه ی چهارم

“۰۱۰۰″ –> {a} زیرمجموعه ی پنجم

“۰۱۰۱″ –> {a, c} زیرمجموعه ی ششم

“۰۱۱۰″ –> {a,b} زیرمجموعه ی هفتم

“۰۱۱۱″ –> {a, b, c} زیرمجموعه ی هشتم

“۱۰۰۰″ –> اتمام الگوریتم

کد به زبان ++C:

#include "stdafx.h"
#include <iostream>
using namespace std;
void subset(char adder[],int n)
{
	for(int i=0; i<n+1; i++)
		adder[i]='0';
	do
	{
		for(int i=1; i<n+1; i++)
		{
			if(adder[i]=='1')
				cout<<"x"<<i<<" ";
		}
		cout<<endl;
		if(adder[n]=='0')
		{
			adder[n]='1';
		}
		else
		{
			int l=n;
			while(adder[l]=='1')
			{
				adder[l]='0';
				l--;
			}
			adder[l]='1';
		}
	}
	while(adder[0]=='0');
}
int main(void)
{
	int n;
	char* adder;
	cout<<"Enter the sumber of elemnets: ";
	cin>>n;
	adder=new char [n+1];
	subset(adder,n);
	cin.get();
	return 0;
}