إنشاء جميع المجموعات الفرعية لمجموعة

في تحديد جميع المجموعات الفرعية لمجموعة معينة، يلعب عدد العناصر (n) دورًا حاسمًا . تسخر الخوارزمية الفعالة التقنيات العودية لتحقيق ذلك.

الخوارزمية العودية

تعمل الخوارزمية العودية على مبدأ أنه لكل عنصر، يمكن تقسيم المجموعات الفرعية إلى قسمين الفئات: تلك التي تحتوي على العنصر وتلك التي تستثنيه. يشترك هذان القسمان في مجموعات فرعية متطابقة.

بداية بـ n=1، لدينا مجموعتان فرعيتان: {} (المجموعة الفارغة) و{1}.

بالنسبة لـ n>1، نحدد المجموعات الفرعية من 1،...،n-1 وتكرارها. سيتم إضافة مجموعة واحدة إلى كل مجموعة فرعية، بينما ستبقى المجموعة الأخرى دون تغيير. اتحاد هاتين المجموعتين ينتج عنه المجموعة الكاملة للمجموعات الفرعية.

مثال توضيحي

لنقم بإنشاء المجموعات الفرعية {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: خذ {} , {1} وأضف 2. الاتحاد مع {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: أضف 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: أضف 4: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}، {4}، {1، 4}، {2، 4}، {1، 2، 4}، {3، 4}، {1، 3، 4}، {2، 3، 4}، { 1, 2, 3, 4}}
• n=5: أضف 5: {{} , {1} , {2} , {1, 2} , {3} , {1، 3}، {2، 3}، {1، 2، 3}، {4}، {1، 4}، {2، 4}، {1، 2، 4}، {3، 4}، {1، 3، 4}، {2، 3، 4}، {1، 2، 3، 4}، {5}، {1، 5}، {2، 5}، {1، 2، 5}، {3، 5}، {1، 3، 5}، {2، 3، 5}، {1، 2، 3، 5}، {4، 5}، {1، 4، 5}، {2، 4 , 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4 , 5}}

وبالتالي، نصل إلى جميع المجموعات الفرعية الـ 32 من {1، 2، 3، 4، 5}.