تابع Powerset

[رضا جاسبی]

اینم روش بازگشتی:

#include<stdio.h>

long SubSetCount;

void Powerset(int n,char *Str)

{

  char Tmp_Buf[100];

  if (n==0)

   {

      printf(Str);

      printf("   Sub Set Finished %d\n" , ++SubSetCount);

      return;

   }

  sprintf(Tmp_Buf,"%s  0",Str);

  Powerset(n-1,Tmp_Buf);

  sprintf(Tmp_Buf,"%s  1",Str);

  Powerset(n-1,Tmp_Buf);

}

void main (void)

{

   int n=3;

   int i;

   char InitStr[]="   ";

   SubSetCount = 0;

   printf("\n Item Numbers : \n   ");

   for (i=1;i<=n;i++)

     printf(" %2d",i);

   printf("\n");

   Powerset(n,InitStr);

}

در این روش برای وجود یا عدم وجود هر عنصر در زیر مجموعه یک عدد چاپ می شود که صفر به معنای عدم وجود عنصر در زیر مجموعه و یک صفر به معنای وجود آن است.
منطق برنامه به این صورت است که هر عنصر در زیر مجموعه دو حالت دارد : وجود ندارد و یا وجود دارد. پس از آن زیر مجموعه های بقیه مجموعه ( بدون این عنصر که تکلیفش مشخص شد ) را به همین روش محاسبه می کنیم.
با مثال n=3 خروجی برنامه را می نویسم. می توانید هر عددی به جای 3 بگذارید. ولی توصیه می کنم برای عددهای خیلی بزرگ احتیاط کنید.

 Item Numbers : 

     1  2  3

     0  0  0   Sub Set Finished 

     0  0  1   Sub Set Finished 

     0  1  0   Sub Set Finished 

     0  1  1   Sub Set Finished 

     1  0  0   Sub Set Finished 

     1  0  1   Sub Set Finished 

     1  1  0   Sub Set Finished 

     1  1  1   Sub Set Finished 

موفق باشی