تابع Powerset

[Ebrahim_T]

با سلام

اگر S مجموعه ای با n عنصر باشد تابع Powerset تمامی زیرمجموعه های ان را بدست می اورد

اگر امکان دارد هم به صورت بازگشتی و هم بصورت غیر بازگشتی این تابع را حل کنید

البته با راهنمایی و توضیح

با تشکر :)

:flower:

[Ebrahim_T]

یعنی کسی نمیتونه این مسله رو حل کنه؟ :گیج: :گیج: :گیج:
:(

[رضا جاسبی]

دوست عزیز. شما مشابه این مشکل رو قبلا داشتی و در "کمک برای حل یک الگوریتم" مطرح کردی که دوستمون B-Vedadian برنامه کاملش رو نوشت. برای این مساله می تونی از همون جواب استفاده کنی فقط اونجا باید مجموع اعداد رو با یک عدد مقایسه می کردی و اینجا نیاز نداری.
البته اون روش غیر بازگشتی بود که از 1 تا 2 به توان n رو در نظر بگیری و بیت به بیت کنترل کنی.
روش بازگشتی رو در پیام بعدی مطرح می کنم
موفق باشی

[رضا جاسبی]

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


#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

موفق باشی

[Ebrahim_T]

سلام مخصوص خدمت اقای جاسبی :flower:
دست شما درد نکنه
خیلی ممنون
البته من روش غیر بازگشتی را که توضیح دادید متوجه نشدم :sorry:

در ضمن اگر می شود همین برنامه ای که ابنجا توضیح دادید را طوری بازسازی کنید که ورودی بصورت ارایه باشد
در ضمن ایا میشود برنامه ای که در ان یکی تاپیک توضیح دادید را بصورت بازگشتی نوشت ؟؟؟؟؟؟؟؟؟؟ :گیج:
البته شرمنده :oops:

خداحافظ و موفق باشید :موفق:

[small_programmer]

این هم به زبان #C

public static ArrayList PowerSet(ArrayList aSet)
{
ArrayList mainA=new ArrayList();
if(aSet.Count==0)
{
mainA.Add(new ArrayList());
return mainA;
}
ArrayList aSet2=(ArrayList)aSet.Clone();
aSet2.RemoveAt(0);
ArrayList subA=PowerSet(aSet2);
ArrayList a2=CopyArrayList(subA);
for(int i=0;i<a2.Count;i++)
{
((ArrayList)a2[i]).Add(aSet[0]);
}
mainA.AddRange(a2);
mainA.AddRange(subA);
return mainA;
}

public static ArrayList CopyArrayList(ArrayList list)
{
ArrayList a1=new ArrayList();
for(int i=0;i<list.Count;i++)
{
a1.Add(((ArrayList)list[i]).Clone());
}
return a1;
}

public static string PrintArrayList(ArrayList aList)
{
StringBuilder str=new StringBuilder("");
for(int i=0;i<aList.Count;i++)
{
ArrayList subA=(ArrayList)aList[i];
for(int j=0;j<subA.Count;j++)
{
str.Append(subA[j].ToString()+" ");
}
str.Append("\r\n");
}
return str.ToString();
}
که یک ArrayList می گیرد

[Ebrahim_T]

خیلی ممنون

دست شما درد نکنه
در ضمن اقای جاسبی با توجه به راهنمایی شما توانستم مسله را حل کنم :تشویق:

اما باز هم یک سوال در مورد ان یکی مسله این که می شود ان را بصورت بازگشتی نوشت ؟ :گیج:

[رضا جاسبی]

بله برادر می شود. در این روش ما در خط (if (n==0 به یک زیر مجموعه رسیده ایم. شما فقط باید در داخل این if به جای اینکه نتیجه را چاپ کنی مجموع را بدست بیاوری و با عدد خواسته شده مقایسه کنی. برای بدست آوردن مجموع دو راه به نظر من می رسد. اول اینکه رشته Str را پیمایش کنیم و هر جا به یک برخورد کردیم عنصر مورد نظر را به مجموع قبلی اضافه کنیم. راه دوم که من بیشتر می پسندم این است که یک پارامتر دیگر اضافه کنیم که مجموع را نگه دارد. به این صورت :


void Powerset(int n,char *Str,int Sum) // New Version: ,int Sum
{
char Tmp_Buf[100];
if ((n==0) && (Sum == DesiredSum)) // New Version: && (Sum == ...
{
printf(Str);
printf(" Sub Set Finished %d\n" , ++SubSetCount);
return;
}
sprintf(Tmp_Buf,"%s 0",Str);
Powerset(n-1,Tmp_Buf , Sum); // New Version: ,Sum
sprintf(Tmp_Buf,"%s 1",Str);
Powerset(n-1,Tmp_Buf,Sum+Array[n]); // New Version: ,Sum+Array[n]
}

البته می تونی یک مقداری Enhancement هم در نظر بگیری مثلا


if ( Sum > DesiredSum ) return;
if ( Sum == DesiredSum)
{
printf ( ... )
return;
}
if ( n ==0 ) // Without Sum == DesiredSum because They are not equal ( passed last if )
{
return;
}
...

مقدار دهی های اولیه برای مقادیر Sum, DesiredSum و Array با خودت.
در ضمن من منظورت رو متوجه نشدم که:

در ضمن اگر می شود همین برنامه ای که ابنجا توضیح دادید را طوری بازسازی کنید که ورودی بصورت ارایه باشد

ضمنا این را هم اضافه کنم که در این مساله به نظر من روش غیر بازگشتی بهتر است. و دیگر اینکه من در این مساله سه پارامتر برای تابع بازگشتی در نظر گرفتم که در تعداد بالا مشکل ایجاد خواهد کرد. در روشهای بازگشتی باید سعی کنیم که مقادیری که در Stack قرار می گیرند کمترین حجم ممکن را داشته باشند.

[Ebrahim_T]

خیلی ممنون از جوابی که دادید :تشویق:

در ضمن منظورم این بود که ورودی بصورت ارایه ای از اعداد وارد بشود چون در این حالت باید
پارامتر دیگری را نیز اضافه کنیم

با تشکر فراوان :flower:

[رضا جاسبی]

اگر منظورت این است که چیزی که در خروجی چاپ می شود به جای صفر و یک عناصر آرایه باشد کار چندان دشورای نیست. گرفتن اعداد آرایه از ورودی که هیچ ! فکر نمی کنم لزومی به نوشتنش باشه ! حداکثر گرفتن یک عدد به عنوان سایز آرایه و یک حلقه برای گرفتن عناصر آرایه . حالا در خط ;(sprintf(Tmp_Buf,"%s 1",Str به جای 1 قرار می دی مثلا d% و بعد از Str هم [Array[n و طبیعتا برای 0 هیچ چیزی نداریم و جای عنصر خالی است. یعنی :


sprintf(Tmp_Buf,"%s",Str);
...
sprintf(Tmp_Buf,"%s %d",Str,Array[n]);

در مورد پارامتر دیگر هم اگر منظورت Sum است به نظر من در روش بازگشتی چاره ای نداریم جز اینکه یک پارامتر اضافه کنیم. البته می توان این پارامتر را به عنوان خروجی تابع در نظر گرفت اما در آن صورت بهینه سازی را که قبلا توضیح دادم مشکل برخورد می کند.
موفق باشی

[رضا جاسبی]

الان داشتم موضوع رو مرور می کردم که دیدم یک اشتباه کپی رایتی پیش اومده و من هم دقت نکردم.

در ضمن ایا میشود برنامه ای که در ان یکی تاپیک توضیح دادید را بصورت بازگشتی نوشت ؟؟؟؟؟؟؟؟؟؟
آن مساله را دوستمون B-Vedadian حل کرده نه من ! من فقط چون دیدم نیاز به توضیح داره کمی در موردش حرف زدم.

[Ebrahim_T]

با سلام خدمت اقای جاسبی

خیلی ممنون از کمکهای شما :تشویق: :flower:

لطف کردید

با تشکر :flower:

[Ebrahim_T]

باز هم سلام و سوال

من تصمیم دارم تا این زیر مجموعه ها را ذخیره کنم حالا چند تا راه حل به فکر من رسید : :تشویق:
یکی اینکه از لیست های پیوندی استفاده کنم و روش بعد استفاده از ارایه ای از نوع رکورد است
حالا اگه امکان داره اساتید محترم به سوال بنده جواب بدهند که کدام روش بهتر است
و یا انکه روش دیگری نیز وجود دارد ؟

با تشکر :)

[رضا جاسبی]

کدام زیر مجموعه ها را ؟ همه زیر مجموعه های ممکن و یا آنهایی که مجموعشون برابر عددی می شود ؟ و ضمنا ذخیره برای چه منظوری ؟ استفاده در یک بخش دیگر برنامه و یا ذخیره در سیستم ( که در این حالت باید در فایل ذخیره کنی )
اما برای استفاده در یک بخش دیگر برنامه . اگر همه زیر مجموعه ها آرایه مناسبتر است. پیشنهاد من تخصیص حافظه پویا ( Dynamic Allocation ) است. اگر فقط آنهایی که مجموعشون برابر یک عدد است باتوجه به اینکه تعدادشون تا آخر مساله مشخص نیست من لیست رو ترجیح می دم.

[son8989]

زیرمجموعه یه رشته به روش بازگشتی بازبان سی شارپ



using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace AlgorithmDesign
{
class Program
{
public string[] str = new string[100];
public int x = 1;
public int y = 1;

public string PowerSet<T>(T[] list, int n)
{

if (n==0)
{
Console.Write("{({}),");
return string.Empty;
}
else
{


PowerSet<T>(list, n - 1);
if (str[x]==null)
{
Console.Write("({0}),", list[n - 1]);
str[x] = Convert.ToString(list[n - 1]);
y++;
}
else
{
Console.Write("({0}),", list[n - 1]);
str[y++] = Convert.ToString(list[n - 1]);


while (str[x]!=null && str[x]!=Convert.ToString(list[n-1]))
{
Console.Write(str[x] + list[n - 1]+",");
str[y++] = Convert.ToString(str[x]+""+list[n - 1]);
x++;


}
x = 1;


}
}
return string.Empty;
}


static void Main(string[] args)
{
char[] ch = new[] {'a', 'b','c','d'};
Program a=new Program();
a.PowerSet(ch, ch.Length);
}
}
}