توليد المجموعات الجزئية باستخدام الأقنعة الثنائية

المجموعة الجزئية لأي مصفوفة هي مجموعة يتم إنشاؤها من بعض عناصر المصفوفة (ربما بدون أي عنصر). على سبيل المثال، بالنسبة للمصفوفة {1, 3, 5, 6, 7}، المجموعات مثل {1, 3}، {3, 5, 7}، و {1, 3, 5, 6, 7} هي مجموعات جزئية من المصفوفة، بينما المجموعات مثل {1, 4}، {2, 7} ليست مجموعات جزئية من المصفوفة.

ترميز المجموعات الجزئية كأعداد ثنائية

بالنسبة لمصفوفة طولها \(n\)، يمكن تمثيل كل مجموعة جزئية باستخدام عدد ثنائي مكون من \(n\) بت حيث كل عنصر في المصفوفة لديه بت يقابله في العدد الثنائي. في هذا الترميز، يكون البت قيمته 1 إذا كان العنصر المقابل ضمن المجموعة الجزئية، و0 إذا لم يكن ضمن المجموعة.

على سبيل المثال، المصفوفة {5, 3, 1}. الترميزات الثنائية لمجموعاتها الجزئية هي:

مجموعة جزئية من {5, 3, 1}	الترميز (ثنائي)	الترميز (عشري)
{}	000	0
{5}	001	1
{3}	010	2
{5, 3}	011	3
{1}	100	4
{5, 1}	101	5
{3, 1}	110	6
{5, 3, 1}	111	7

Noteملحوظة

بالنسبة لمصفوفة طولها \(n\)، عدد المجموعات الجزئية المختلفة هو \(2^n\).

توليد المجموعات الجزئية

يمكننا ملاحظة أنه بالنسبة لمصفوفة طولها \(n\)، يمكن ترقيم كل المجموعات الجزئية من 0 إلى \(2^n - 1\). باستخدام هذا الترقيم، يمكننا المرور عبر جميع الأعداد الصحيحة من 0 إلى \(2^n - 1\) وتوليد كل مجموعة جزئية عن طريق التحقق من البتات.

على سبيل المثال، افترض أننا نريد كتابة برنامج يطبع كل المجموعات الجزئية من المصفوفة a، كل واحدة في سطر منفصل.

#include <iostream>
using namespace std;

int main() {
  int n = 3;
  int a[3] = {5, 3, 1};

  for(int i = 0; i < (1 << n); i++) {   // 2^n - 1 يمر بجميع الأعداد من 0 إلى
    cout << i << ": ";

    for(int j = 0; j < n; j++) {        // i يتكرر عبر جميع البتات للرقم 
      bool set = (i & (1 << j)) != 0;   // i قيمته 1 في الرقم  j يتحقق إذا كان البت 
      if(set) {
        cout << a[j] << ' ';
      }
    }

    cout << endl;
  }
}

سيطبع هذا البرنامج التالي:

0: 
1: 5 
2: 3 
3: 5 3 
4: 1 
5: 5 1 
6: 3 1 
7: 5 3 1