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

[marandi]

سلام
از دوستان عزیز کسی در مورد به دست آوردن زیر مجموعه های یک مجموعه n عضوی اطلاعی داره ؟ (البته ترجیجا به یکی از زبان های VB یا VB.NET)

با تشکر

[علیرضا جاوید]

دو تا روش داره اولی نانریکرسیو دومی ریکرسیو:
روش نانریکرسیو:
تو این روش یک حلقه میذارید از 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]

سلام

میشه مجموعه 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]

در ادامه ی پست قبلی بگم که 0 0 0 مجموعه ی تهی رو میده و 1 1 1 خود مجموعه رو. در حقیقت برای مجموعه ی n عضوی ما به صورت دودویی از صفر تا n-1 رو مینویسیم.

[marandi]

سلام
از همه دوستان ممنونم