مجموعات فرعية من مجموعة هي مفهوم مهم في الرياضيات والبرمجة. إنها تمثل جميع المجموعات الممكنة لعناصر مجموعة معينة ، بما في ذلك المجموعة الفارغة والمجموعة نفسها. يعد العثور على جميع المجموعات الفرعية مهمة صعبة حسابيا ، ولكن هناك حل بسيط وفعال لهذه المشكلة.
طريقة واحدة للعثور على جميع مجموعات فرعية من مجموعة هو استخدام بيتماسك. قناع البت هو سلسلة من البتات ، كل منها يتوافق مع عنصر من المجموعة. إذا كانت البتة واحدة ، فسيتم تضمين العنصر في المجموعة الفرعية ، إذا كانت البتة صفرا ، فلن يتم تضمين العنصر.
الخوارزمية البسيطة والفعالة للعثور على جميع المجموعات الفرعية لمجموعة باستخدام قناع البت هي كما يلي:
- إنشاء متغير من شأنها أن تمثل بيتماسك
- انتقل من خلال جميع الأرقام من 0 إلى 2 إلى قوة ن ، أين ن هو عدد عناصر المجموعة
- قم بإنشاء مجموعة فرعية جديدة لكل رقم ، بما في ذلك العناصر التي تتوافق مع الوحدات الموجودة في القناع النقطي فقط
- مجموعات فرعية من المجموعة: كيف أجدهم جميعا?
- مجموعة الابتدائية ومجموعة فرعية
- حل بسيط للمشكلة: التكرار من خلال جميع التوليفات الممكنة
- حل فعال للمشكلة: استخدام الأقنعة النقطية
- أمثلة وخوارزميات عملية
- 1. خوارزمية العودية
- 2. باستخدام قناع بت
- 3. باستخدام قناع البت العودية
- الاستنتاجات: اختيار الحل الأكثر فعالية
- سؤال وجواب
- كيف يمكنني العثور على جميع مجموعات فرعية من مجموعة?
- ما هو الحل البسيط والفعال للعثور على جميع المجموعات الفرعية للمجموعة?
- ما هي المزايا التي تتمتع بها طريقة تشغيل البت للعثور على جميع المجموعات الفرعية للمجموعة?
- هل من الممكن استخدام طريقة تشغيل البت للعثور على جميع المجموعات الفرعية لمجموعة تحتوي على عناصر مكررة?
مجموعات فرعية من المجموعة: كيف أجدهم جميعا?
مجموعة فرعية من مجموعة هي أي مجموعة من العناصر المضمنة في هذه المجموعة. على سبيل المثال ، بالنسبة للمجموعة {1 ، 2 ، 3} ، ستكون المجموعات الفرعية: {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. يمكن أن يكون العثور على جميع المجموعات الفرعية للمجموعة مفيدا في مهام مختلفة ، على سبيل المثال ، في التوافقية أو خوارزميات التكرار أو مهام إنشاء مجموعة فرعية.
هناك طرق مختلفة للعثور على جميع المجموعات الفرعية للمجموعة ، ولكن الطريقة البسيطة والفعالة هي استخدام عمليات البت. يتم تعيين كل عنصر من عناصر المجموعة قليلا يشير إلى ما إذا كان العنصر مدرجا في المجموعة الفرعية. وبالتالي ، يمكن تمثيل كل مجموعة فرعية من المجموعة بمجموعة من قيم البت.
الخوارزمية للعثور على جميع المجموعات الفرعية للمجموعة:
- لنفترض أن لدينا مجموعة س من ن عناصر.
- لكل رقم أنا من 0 إلى 2^ن-1:
على سبيل المثال ، بالنسبة للمجموعة {1 ، 2 ، 3} ، ستتكرر الخوارزمية على الأرقام من 0 إلى 7 (2^ن-1) ولكل رقم ستقوم ببناء مجموعة فرعية تتوافق مع تدوينها الثنائي:
| العدد | تدوين ثنائي | مجموعة فرعية (العناصر المقابلة لـ 1) |
|---|---|---|
| 0 | 000 | {} |
| 1,001 | {3} | |
| 2 | 010 | {2} |
| 3 | 011 | {2, 3} |
| 4 | 100 | {1} |
| 5 | 101 | {1, 3} |
| 6 | 110 | {1, 2} |
| 7 | 111 | {1, 2, 3} |
وبالتالي ، تسمح لك الخوارزمية بالعثور على جميع المجموعات الفرعية للمجموعة باستخدام عمليات بت بسيطة وتكرار على الأرقام من 0 إلى 2^ن — 1.
مجموعة الابتدائية ومجموعة فرعية
المجموعة هي كائن رياضي عبارة عن مجموعة من العناصر التي ليس لها ترتيب ولا تكرار. يمكن أن تكون عناصر المجموعة كائنات عشوائية ، مثل الأرقام أو الحروف أو الكلمات أو مجموعات أخرى.
المجموعة الأولية هي مجموعة تتكون من عنصر واحد فقط. على سبيل المثال ، المجموعة {1} هي مجموعة أولية ، لأنها تحتوي على عنصر واحد فقط – الرقم 1.
المجموعة الفرعية هي مجموعة تكون عناصرها أيضا عناصر من مجموعة أخرى. إذا كان كل عنصر من عناصر المجموعة أ هو أيضا عنصر من عناصر المجموعة ب ، فيقال إن أ هي مجموعة فرعية من ب ، ومكتوبة كـ أ B ب. إذا كانت المجموعة أ هي مجموعة فرعية من المجموعة ب ، ولكنها ليست مساوية لها ، فيقال إن المجموعة أ هي مجموعة فرعية مناسبة من المجموعة ب ، ومكتوبة كـ أ B ب.
على سبيل المثال ، يجب ألا تكون هناك مجموعة أ = {1 ، 2} ومجموعة ب = {1 ، 2 ، 3}. في هذه الحالة ، المجموعة أ هي مجموعة فرعية من المجموعة ب ، لأن كل عنصر من عناصر المجموعة أ هو أيضا عنصر من عناصر المجموعة ب. أيضا ، المجموعة أ هي مجموعة فرعية مناسبة من المجموعة ب ، لأن المجموعة ب تحتوي على عناصر مفقودة من المجموعة أ.
يستخدم الرمز verify للتحقق من أن عنصر ينتمي إلى مجموعة. على سبيل المثال ، إذا كان س ينتمي إلى المجموعة أ ، فاكتب س A أ.
حل بسيط للمشكلة: التكرار من خلال جميع التوليفات الممكنة
لحل مشكلة العثور على جميع المجموعات الفرعية للمجموعة ، هناك طريقة بسيطة تعتمد على التكرار من خلال جميع المجموعات الممكنة. تتكون هذه الطريقة من عدة خطوات:
- قم بتهيئة قائمة فارغة تحتوي على جميع المجموعات الفرعية التي تم العثور عليها.
- لكل عنصر في المجموعة الأصلية ، اتبع الخطوات التالية:
- قم بإنشاء قائمة جديدة تحتوي على العنصر الحالي فقط.
- أضف هذه القائمة الجديدة إلى قائمة جميع المجموعات الفرعية.
- استدعاء الخوارزمية للعناصر المتبقية بشكل متكرر عن طريق إضافة قائمة جديدة إلى المجموعة الفرعية الحالية.
- إرجاع قائمة بجميع المجموعات الفرعية.
فيما يلي مثال على حل المشكلة: سنجد جميع المجموعات الفرعية للمجموعة {1 ، 2 ، 3}.
| خطوة | العنصر الحالي | مجموعة فرعية من |
|---|---|---|
| 1 | 1 | {1} |
| 2 | 2 | {2} |
| 3 | 3 | {3} |
| 4 | 2 | {1, 2} |
| 5 | 3 | {1, 3} |
| 6 | 3 | {2, 3} |
| 7 | 3 | {1, 2, 3} |
بعد التكرار من خلال جميع المجموعات ، نحصل على القائمة التالية لجميع المجموعات الفرعية للمجموعة {1, 2, 3}: { {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }.
هذه الطريقة سهلة التنفيذ وتسمح لك بالعثور على جميع المجموعات الفرعية للمجموعة. ومع ذلك ، تعتمد فعاليتها على حجم المجموعة الأصلية. مع وجود عدد كبير من العناصر ، يمكن أن يكون المرور بجميع المجموعات عملية طويلة.
حل فعال للمشكلة: استخدام الأقنعة النقطية
يمكن استخدام الأقنعة النقطية لحل مشكلة البحث عن جميع المجموعات الفرعية للمجموعة. قناع البت هو سلسلة من البتات حيث يتوافق كل بت مع وجود أو عدم وجود عنصر في مجموعة فرعية. يمكن تمثيل كل عنصر بواحد إذا كان موجودا ، أو صفر إذا كان غائبا.
باستخدام الأقنعة النقطية ، يمكننا التكرار من خلال جميع المجموعات الممكنة لعناصر المجموعة. للقيام بذلك ، نكرر من 0 إلى 2^ن-1 ، أين ن هو عدد العناصر في المجموعة. ستمثل كل قيمة تكرار مزيجا فريدا من مجموعة فرعية.
لكل تكرار ، سوف نتحقق من كل جزء من القناع. إذا كان البت هو 1 ، فسيتم تضمين العنصر الذي يحتوي على الفهرس المقابل في المجموعة الفرعية. إذا كان البت 0 ، فلن يتم تضمين العنصر الذي يحتوي على هذا الفهرس في المجموعة الفرعية.
مثال على الخوارزمية:
- تهيئة مجموعة فارغة لتخزين مجموعات فرعية.
- كرر من 0 إلى 2^ن-1 ، أين ن هو عدد العناصر في المجموعة الأصلية.
- لكل تكرار ، نقوم بإنشاء مجموعة فرعية جديدة عن طريق تكرار المجموعة.
- كرر على كل بت من القناع.
- إذا كان البت هو 1 ، أضف العنصر مع الفهرس المقابل إلى المجموعة الفرعية.
- نضيف المجموعة الفرعية الناتجة إلى القائمة العامة للمجموعات الفرعية.
لكل تكرار للخوارزمية ، يكون عدد العمليات مساويا لعدد العناصر في المجموعة. العدد الإجمالي للعمليات في الخوارزمية هو 2^ن ، أين ن هو عدد العناصر في المجموعة الأصلية. هذا الحل هو واحد من الأكثر فعالية ، لأن تعقيده هو س(2^ن).
مثال على تنفيذ الخوارزمية في بايثون:
ديف فيند_ سوبسيتس (نومس):
مجموعات فرعية = []
ن = لين (أرقام)
لأني في النطاق (2 * * ن):
مجموعة فرعية = []
إلى عن على ي في النطاق (ن):
إذا أنا & (1 < < ي):
مجموعة فرعية.إلحاق (أرقام [ي])
مجموعات فرعية.إلحاق (مجموعة فرعية)
عودة مجموعات فرعية
سيؤدي استدعاء الدالة العثور على مجموعات فرعية([1 ، 2 ، 3]) إلى إرجاع قائمة بجميع المجموعات الفرعية لهذه المجموعة: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].
يتيح استخدام الأقنعة النقطية حل مشكلة البحث عن جميع المجموعات الفرعية للمجموعة بشكل فعال. يعمل هذا الحل في الوقت الأسي ، ولكنه مثالي وفعال لهذه المهمة.
أمثلة وخوارزميات عملية
فيما يلي بعض الأمثلة والخوارزميات العملية للعثور على جميع المجموعات الفرعية للمجموعة.
1. خوارزمية العودية
واحدة من أبسط الطرق وأكثرها فعالية للعثور على جميع المجموعات الفرعية للمجموعة هي خوارزمية متكررة. يعتمد على الفكرة التالية:
- المجموعة الفارغة هي مجموعة فرعية من أي مجموعة.
- لكل عنصر من عناصر المجموعة ، هناك خياران: يمكن تضمين عنصر في مجموعة فرعية أو عدم تضمينه.
- باستخدام العودية ، نقوم بإنشاء جميع المجموعات الفرعية ، بدءا من مجموعة فارغة وإضافة عناصر بالتتابع.
مثال على خوارزمية العودية:
ديف فيند_ سوبسيتس (ق ، كور ، مؤشر):# الحالة الأساسية : تم الوصول إلى نهاية المجموعة
إذا مؤشر = = لين (ق):
طباعة (كور)
العودة
# استدعاء الدالة بشكل متكرر لكلا الخيارين: لتضمين وعدم تضمين العنصر الحالي
العثور على مجموعات فرعية (ق ، كور ، مؤشر + 1)
ابحث عن مجموعات فرعية (ق ، كور + [ق [فهرس]] ، فهرس + 1)
س = [1 ، 2 ، 3]
ابحث عن مجموعات فرعية(مجموعات فرعية ، [] ، 0)
. يتم تحقيق الحالة الأساسية عندما يكون الفهرس مساويا لطول المجموعة ، وفي هذه الحالة يتم عرض المجموعة الفرعية. ثم يتم استدعاء وظيفتين بشكل متكرر: واحدة للحالة عندما لا يتم تضمين العنصر الحالي ، والآخر للحالة عندما يتم تضمينه. في كلتا الحالتين ، يتم زيادة المؤشر بمقدار واحد.
2. باستخدام قناع بت
هناك طريقة أخرى للعثور على جميع المجموعات الفرعية للمجموعة وهي استخدام قناع البت. يعتمد على الفكرة التالية:
- يتوافق كل عنصر من عناصر المجموعة مع بت معين في قناع البت.
- إذا كان البت هو 1 ، فسيتم تضمين العنصر في المجموعة الفرعية ، وإذا كان البت هو 0 ، فلن يتم تضمين العنصر.
- نقوم بتشغيل جميع المجموعات الممكنة من قيم البت ، وتوليد جميع المجموعات الفرعية.
مثال على خوارزمية باستخدام قناع البت:
مواطنه العثور على _ سوبسيتس (ق):ن = لين (ق)
# تشغيل من خلال جميع المجموعات الممكنة من قيم البت من 0 إلى 2^ن-1
لأني في النطاق (1 < < ن):
مجموعة فرعية = []
# تحقق من كل بت في المجموعة الحالية
إلى عن على ي في النطاق (ن):
إذا أنا & (1 < < ي):
مجموعة فرعية.إلحاق (ق [ي])
طباعة (مجموعة فرعية)
س = [1 ، 2 ، 3]
ابحث عن مجموعات فرعية(مجموعات فرعية)
. داخل الحلقة المتداخلة ، نتحقق من كل بت في المجموعة الحالية ونضيف العنصر المقابل إلى المجموعة الفرعية. بعد ذلك ، نعرض المجموعة الفرعية على الشاشة.
3. باستخدام قناع البت العودية
الجمع بين النهجين السابقين ، يمكنك استخدام بيتماسك العودية للعثور على جميع مجموعات فرعية من مجموعة:
مجموعات فرعية (مجموعات فرعية ، مجموعة فرعية ، فهرس):ن = لين (ق)
# حالة القاعدة: نهاية المجموعة
تم الوصول إليه إذا كان الفهرس = = ن:
طباعة (مجموعة فرعية)
العودة
# استدعاء الدالة بشكل متكرر لكلا الخيارين: تمكين العنصر الحالي وعدم تمكينه
ابحث عن مجموعات فرعية (مجموعات فرعية ، مجموعة فرعية ، فهرس + 1)
ابحث عن مجموعات فرعية (مجموعات فرعية + [مجموعات فرعية[فهرس]] ، فهرس + 1)
س = [1 ، 2 ، 3]
ابحث عن مجموعات فرعية(مجموعات فرعية ، [] ، 0)
. يتم تحقيق الحالة الأساسية عندما يكون الفهرس مساويا لطول المجموعة ، وفي هذه الحالة يتم عرض المجموعة الفرعية. ثم يتم استدعاء وظيفتين بشكل متكرر: واحدة للحالة عندما لا يتم تضمين العنصر الحالي ، والآخر للحالة عندما يتم تضمينه. في كلتا الحالتين ، يتم زيادة المؤشر بمقدار واحد.
كما يتبين من الأمثلة ، يمكن العثور على جميع المجموعات الفرعية للمجموعة بطرق مختلفة. كل واحد منهم له مزاياه ويمكن استخدامه اعتمادا على سياق ومتطلبات المهمة.
الاستنتاجات: اختيار الحل الأكثر فعالية
عند حل مشكلة العثور على جميع المجموعات الفرعية للمجموعة ، هناك عدة طرق ، لكل منها مزاياها وعيوبها. أحد العوامل الرئيسية التي يجب مراعاتها عند اختيار الحل الأكثر فعالية هو وقت تنفيذ الخوارزمية.
يمكن تقسيم الحلول المقدمة في المقالة إلى مجموعتين: النهج العودي والنهج التكراري.
- النهج العودية:
- رمز بسيط وواضح;
- من السهل فهم ومراقبة تنفيذ الخوارزمية;
- يمكن أن تكون فعالة للمجموعات الصغيرة ، ولكن لديها تعقيد وقت تشغيل مرتفع للمجموعات الكبيرة.;
- قد يؤدي استدعاء دالة متكررة إلى تجاوز سعة المكدس;
- إذا كانت المجموعة تحتوي على عناصر مكررة ، يمكن للنهج العودي إخراج التكرارات.
- نهج تكراري:
- عادة ما يكون أكثر كفاءة من حيث وقت التنفيذ ، خاصة بالنسبة للمجموعات الكبيرة;
- لا يتطلب استخدام استدعاءات الدالة العودية;
- استدعاء وظيفة يستغرق كمية ثابتة من الذاكرة;
- يعمل بشكل جيد مع مجموعات تحتوي على عناصر مكررة;
- قد يكون من الصعب فهم وتصحيح الأخطاء بسبب تعقيد الخوارزمية.
نتيجة لذلك ، يعتمد اختيار الحل الفعال على المهمة المحددة وخصائص المجموعة. إذا كانت الشفرة البسيطة والمفهومة مهمة ، فقد يكون من الأفضل اتباع نهج تكراري. ومع ذلك ، إذا كان وقت التنفيذ مهما ويمكن أن تكون المجموعة كبيرة ، فقد يكون النهج التكراري خيارا أكثر ملاءمة.
سؤال وجواب
كيف يمكنني العثور على جميع مجموعات فرعية من مجموعة?
للعثور على جميع المجموعات الفرعية للمجموعة ، يمكنك استخدام طريقة عمليات البت. يتوافق كل عنصر من عناصر المجموعة مع بعض الشيء ، يمكن أن تكون قيمته 0 أو 1 ، مما يشير إلى وجود أو عدم وجود هذا العنصر في المجموعة الفرعية.
ما هو الحل البسيط والفعال للعثور على جميع المجموعات الفرعية للمجموعة?
الحل البسيط والفعال للعثور على جميع المجموعات الفرعية للمجموعة هو استخدام طريقة تشغيل البت. باستخدام عمليات البت ، يمكنك التكرار من خلال جميع المجموعات الممكنة لعناصر المجموعة والحصول على جميع مجموعاتها الفرعية.
ما هي المزايا التي تتمتع بها طريقة تشغيل البت للعثور على جميع المجموعات الفرعية للمجموعة?
تتميز طريقة تشغيل البت للعثور على جميع المجموعات الفرعية للمجموعة بالعديد من المزايا. أولا ، إنها طريقة بسيطة وفعالة تسمح لك بالحصول على جميع المجموعات الفرعية لمجموعة في الوقت الخطي. ثانيا ، لا يتطلب استخدام ذاكرة إضافية ، حيث يتم إنشاء مجموعات فرعية على الطاير. ثالثا ، يمكن تكييف هذه الطريقة بسهولة للعمل مع أنواع البيانات المختلفة والأحجام المحددة.
هل من الممكن استخدام طريقة تشغيل البت للعثور على جميع المجموعات الفرعية لمجموعة تحتوي على عناصر مكررة?
نعم ، يمكن أيضا استخدام طريقة تشغيل البت للعثور على جميع المجموعات الفرعية لمجموعة تحتوي على عناصر متكررة. للقيام بذلك ، يجب عليك أولا إزالة العناصر المكررة من المجموعة. ثم يمكنك تطبيق طريقة تشغيل البت للحصول على جميع المجموعات الفرعية دون تكرار.