PDA

View Full Version : الگوریتم بدست آوردن زیر مجموعه ها



marandi
یک شنبه 07 فروردین 1384, 08:08 صبح
سلام
از دوستان عزیز کسی در مورد به دست آوردن زیر مجموعه های یک مجموعه n عضوی اطلاعی داره ؟ (البته ترجیجا به یکی از زبان های VB یا VB.NET)

با تشکر

علیرضا جاوید
دوشنبه 08 فروردین 1384, 00:42 صبح
دو تا روش داره اولی نانریکرسیو دومی ریکرسیو:
روش نانریکرسیو:
تو این روش یک حلقه میذارید از 0 تا 2 به توان n منهای 1 بعد به ازای تک تک اعداد به دست آمده در حلقه، در الگوی بیتی، به ازای وجود هر عدد یک، عنصر مورد متناظر مورد نظر را به عنوان عضو زیر مجموعه نشان میدهید.
کدی شبیه به زیر:


for i:=1 to Power(2, n) -1 do
begin
write('{');
for j := 0 to n-1 do
if power(2, j) AND i <> 0 then write(item[j])
write('}');
end;

روش ریکرسیو:

این روش هم شبیه الگوریتم perm میمونه که الان دقیقا حضور ذهن ندارم ولی اگر خیلی فوری باشه حتما پیداش میکنم :wink:

javad20563
پنج شنبه 11 فروردین 1384, 04:22 صبح
سلام

میشه مجموعه n عضوی رو به صورت بیت ها در نظر گرفت

برای مثال اگر یک مجموعه ی 3 عضوی داشته باشیم شامل a,b,c ، سه بیت بقل هم براش در نظر میگیریم و تمام حالتهای بیتها رو مینویسیم. یعنی
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
1 1 1
1 1 1

حالا هر جا 0 داشتیم چیزی نمیگذاریم و هر جا یک معادلش رو میذاریم. برای مثال برای 0 1 1 مینویسیم
a b.

البته یک روش رکرسیو هم وجود داره.

javad20563
پنج شنبه 11 فروردین 1384, 04:24 صبح
در ادامه ی پست قبلی بگم که 0 0 0 مجموعه ی تهی رو میده و 1 1 1 خود مجموعه رو. در حقیقت برای مجموعه ی n عضوی ما به صورت دودویی از صفر تا n-1 رو مینویسیم.

marandi
پنج شنبه 11 فروردین 1384, 12:05 عصر
سلام
از همه دوستان ممنونم