تبلیغات


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

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

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:

 


تبلیغات:

۵ دیدگاه

  • خیلی ممنون از زحمات شما . بسیار مفید بود .

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

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

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

نظر خود را بنویسید.

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