کد و الگوریتم پیدا کردن زیرمجموعه های یک مجموعه به زبان ++C

images

همه ما با مفهوم زیر مجموعه (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:

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۴ comments

  • تشکر عالی بود…..

  • یک توضیحی هم بدم که هدف از این کد چاپ زیرمجموعه‌های k عضوی مجموعه بود که با اضافه کردن یک شرط ساده محقق میشه. (که من از کد پاکش کردم)

  • سلام
    از اون جایی که مطلب اخیرتان در مورد بهینه سازی بود گفتم این کد را که ترکیب قسمتی از کدهای شما و یکی از کدهای قدیمم بود را بفرستم براتون شاید برای کسی جالب بود (این کد کمی سریع تر هست (اگر تابع پرینت را در هر دو کامنت کنید)

Leave a Reply

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *