مجموعة القوة

مجموعة القوة Power Set هي المجموعة التي تضمّ جميع المجموعات المتفرّعة من المجموعة الأصلية. فعلى سبيل المثال:

S = {a, b, c}
P(S) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

إن احتوت المجموعة S على n من العناصر فإنّ مجموعة القوة P(S)‎ ستحتوي على ‎2^n‎ من العناصر.

الخوارزمية

يمكن تقسيم الخوارزمية إلى الخطوات التالية:

1. حساب عدد العناصر في مجموعة القوة باستخدام العلاقة المذكورة في أعلاه.
2. إنشاء حلقة تكرارية تبدأ من 0 وتنتهي بالعدد المساوي لعدد العناصر في مجموعة القوة:

أ - إنشاء حلقة تكرارية تبدأ من i = 0 وتنتهي بالعدد المساوي لعدد العناصر في المجموعة الأصلية.

1- إن كان البت bit ذو الترتيب i معيّنًا، فسنطبع العنصر ذا الترتيب i من المجموعة في هذه المجموعة الفرعية

ب - طباعة فاصل للمجموعات الفرعية (سطر جديد)

مثال:

المجموعة  = [a,b,c]
power_set_size = pow(2, 3) = 8
عداد ثنائي = من 000 إلى 111

قيمة العداد            المجموعة الفرعية
    000                    -> مجموعة فارغة
    001                    -> a
    010                    -> b
    011                    -> ab
    100                    -> c
    101                    -> ac
    110                    -> bc
    111                    -> abc

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
#include <math.h> 
using namespace std; 

class gfg 
{ 
	
public: 
void printPowerSet(char *set, int set_size) 
{ 
	/*حساب عدد عناصر مجموعة القوة باستخدام العلاقة المذكورة أعلاه*/
	unsigned int pow_set_size = pow(2, set_size); 
	int counter, j; 
	/* إنشاء حلقة تكرارية تبدأ من العداد 000..0 إلى 111..1 */
	for(counter = 0; counter < pow_set_size; counter++) 
	{ 
	for(j = 0; j < set_size; j++) 
	{ 
		/* j التحقق من تعيين قيمة للبت ذي الترتيب 
		فإن كان كذلك نطبع العنصر المقابل في المجموعة */
		if(counter & (1 << j)) 
			cout << set[j]; 
	} 
	cout << endl; 
	} 
} 
}; 

/* اختبار الدالة السابقة */
int main() 
{ 
	gfg g; 
	char set[] = {'a','b','c'}; 
	g.printPowerSet(set, 3); 
	return 0; 
}

• بايثون:

import math; 

def printPowerSet(set,set_size): 
	
	# حساب عدد عناصر مجموعة القوة باستخدام العلاقة المذكورة أعلاه 
	pow_set_size = (int) (math.pow(2, set_size)); 
	counter = 0; 
	j = 0; 
	
	# إنشاء حلقة تكرارية تبدأ من العداد 000..0 إلى 111..1 
		for j in range(0, set_size): 
			
			# j التحقق من تعيين قيمة للبت ذي الترتيب  
			# فإن كان كذلك نطبع العنصر المقابل في المجموعة 
			if((counter & (1 << j)) > 0): 
				print(set[j], end = ""); 
		print(""); 

# اختبار الدالة السابقة
set = ['a', 'b', 'c']; 
printPowerSet(set, 3);

• جافا:

import java .io.*; 

public class GFG { 
	
	static void printPowerSet(char []set, 
							int set_size) 
	{ 
		
		/*حساب عدد عناصر مجموعة القوة باستخدام العلاقة المذكورة أعلاه*/
		long pow_set_size = 
			(long)Math.pow(2, set_size); 
		int counter, j; 
	
		/*إنشاء حلقة تكرارية تبدأ من العداد 000..0 إلى 111..1*/
		for(counter = 0; counter < 
				pow_set_size; counter++) 
		{ 
			for(j = 0; j < set_size; j++) 
			{ 
				/* j التحقق من تعيين قيمة للبت ذي الترتيب 
				فإن كان كذلك نطبع العنصر المقابل في المجموعة */
				if((counter & (1 << j)) > 0) 
					System.out.print(set[j]); 
			} 
			
			System.out.println(); 
		} 
	} 
	
	// اختبار الدالة السابقة
	public static void main (String[] args) 
	{ 
		char []set = {'a', 'b', 'c'}; 
		printPowerSet(set, 3); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n2^2)‎.

تنفيذ الخوارزمية بطرق تعاودية

يمكن إيجاد مجموعة القوة لمجموعة معين باستخدام عدد من الطرق التعاودية.

الطريقة الأولى

تثبّت هذه الطريقة سابقة prefix، ثم تنشئ جميع المجموعات الفرعية التي تبدأ بالسابقة الحالية، وبعد إنشاء جميع المجموعات الفرعية باستخدام سابقة معينة يحل أحد الحروف المتبقية محلّ الحرف الأخير.

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// str : يخزن السلسلة النصية المدخلة
// curr : يخزّن المجموعة الفرعية الحالية
// index : الموقع في المجموعة الفرعية الحالية 
void powerSet(string str, int index = -1, 
			string curr = "") 
{ 
	int n = str.length(); 

	// الحالة الأساس
	if (index == n) 
		return; 

	// طباعة المجموعة الفرعية الحالية أولاً
	cout << curr << "\n"; 

	// محاولة إلحاق بقية الحروف بالمجموعة الفرعية الحالية
	for (int i = index + 1; i < n; i++) { 

		curr += str[i]; 
		powerSet(str, i, curr); 

		// "curr" بعد طباعة جميع المجموعات الفرعية التي تبدأ بالقيمة الأولية لـ 
		// يحذف الحرف الأخير وذلك لاستخدام سابقة أخرى
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	string str = "abc"; 
	powerSet(str); 
	return 0; 
}

• بايثون:

# str : يخزن السلسلة النصية المدخلة 
# curr : يخزّن المجموعة الفرعية الحالية
# index : الموقع في المجموعة الفرعية الحالية 
def powerSet(str1, index, curr): 
	n = len(str1) 

	# الحالة الأساس
	if (index == n): 
		return

	# طباعة المجموعة الفرعية الحالية أولاً
	print(curr) 

	# محاولة إلحاق بقية الحروف بالمجموعة الفرعية الحالية
	for i in range(index + 1, n): 
		curr += str1[i] 
		powerSet(str1, i, curr) 

		# "curr" بعد طباعة جميع المجموعات الفرعية التي تبدأ بالقيمة الأولية لـ 
		# يحذف الحرف الأخير وذلك لاستخدام سابقة أخرى 
		curr = curr.replace(curr[len(curr) - 1], "") 

	return

# اختبار الدالة السابقة
if __name__ == '__main__': 
	str = "abc"; 
	powerSet(str, -1, "")

• جافا:

import java.util.*; 

class GFG 
{ 

	// str : يخزن السلسلة النصية المدخلة
	// curr : يخزّن المجموعة الفرعية الحالية
	// index : الموقع في المجموعة الفرعية الحالية 
	static void powerSet(String str, int index, 
							String curr) 
	{ 
		int n = str.length(); 

		// الحالة الأساس 
		if (index == n) 
		{ 
			return; 
		} 

		// طباعة المجموعة الفرعية الحالية أولاً
		System.out.println(curr); 

		// محاولة إلحاق بقية الحروف بالمجموعة الفرعية الحالية
		for (int i = index + 1; i < n; i++) 
		{ 
			curr += str.charAt(i); 
			powerSet(str, i, curr); 

			// "curr" بعد طباعة جميع المجموعات الفرعية التي تبدأ بالقيمة الأولية لـ 
			// يحذف الحرف الأخير وذلك لاستخدام سابقة أخرى
			curr = curr.substring(0, curr.length() - 1); 
		} 
	} 

	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		String str = "abc"; 
		int index = -1; 
		String curr = ""; 
		powerSet(str, index, curr); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

a
ab
abc
ac
b
bc
c

الطريقة الثانية

تأخذ هذه الطريقة حالتين لكل حرف هما:

1. الحرف الحالي جزء من المجموعة الفرعية الحالية
2. الحرف الحالي ليس جزءًا من المجموعة الفرعية الحالية

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// str : يخزن السلسلة النصية المدخلة
// curr : يخزّن المجموعة الفرعية الحالية
// index : الموقع في المجموعة الفرعية الحالية 
void powerSet(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.length(); 

	// الحالة الأساس
	if (index == n) { 
		cout << curr << endl; 
		return; 
	} 

	// هناك حالتان لكل حرف:
	// (1) الحرف الحالي جزء من المجموعة الحالية
	// (2) الحرف الحالي ليس جزءًا من المجموعة الحالية
	powerSet(str, index + 1, curr + str[index]); 
	powerSet(str, index + 1, curr); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	string str = "abc"; 
	powerSet(str); 
	return 0; 
}

• بايثون:

def powerSet(string , index , curr): 
	
	# str : يخزن السلسلة النصية المدخلة 
	# curr : يخزّن المجموعة الفرعية الحالية
	# index : الموقع في المجموعة الفرعية الحالية 
	if index == len(string): 
		print(curr) 
		return
	
	powerSet(string, index + 1, 
			curr + string[index]) 
	powerSet(string, index + 1, curr) 
	
# اختبار الدالة السابقة
if __name__ == "__main__": 

	s1 = "abc"
	index = 0
	curr = "" 
	powerSet(s1, index , curr)

• جافا:

class GFG { 

	// str : يخزن السلسلة النصية المدخلة
	// curr : يخزّن المجموعة الفرعية الحالية
	// index : الموقع في المجموعة الفرعية الحالية static void powerSet(String str, int index, 
			String curr) 
	
{ 
	int n = str.length(); 

	// base case 
	if (index == n) 
	{ 
		System.out.println(curr); 
		return; 
	} 

	// هناك حالتان لكل حرف:
	// (1) الحرف الحالي جزء من المجموعة الحالية
	// (2) الحرف الحالي ليس جزءًا من المجموعة الحالية
	powerSet(str, index + 1, curr + str.charAt(index)); 
	powerSet(str, index + 1, curr); 

} 

// اختبار الدالة السابقة
public static void main(String[] args) 
{ 
	String str = "abc"; 
		int index = 0; 
		String curr=""; 
	powerSet(str,index,curr); 

	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

abc
ab
ac
a
bc
b
c

الطريقة الثالثة

تأخذ هذه الطريقة العناصر واحدًا تلو الآخر من المجموعة المدخلة، ثم تنتج المجموعة الفرعية بالطريقة نفسها، وتستمر هذه الخطوات بطريقة تعاودية.

تستخدم ArrayList لهذا الغرض، فمثلاً:

f(0) = {a}, {}
// {} إن لم نضف أي عنصر إلى المجموعة فإنّها ستكون فارغة
f(1) = {a}, {}, {b}, {a, b}
// يجب نسخ جميع العناصر من f(0)‎ ثم إضافة العنصر التالي من المجموعة (أي b)، وهكذا فإن f(1) = f(0) + 1
f(2) = {a}, {}, {b}, {a, b}, {a, c}, {c}, {b, c}, {a, b, c} .So f(2) = f(1) +2;

الصيغة العامة: f(n) = f(n-1) + n.

يعرض المثال التالي كيفية تنفيذ هذه الطريقة في لغة Java:

// Java Recursive code to print 
// all subsets of set using ArrayList 
import java.util.ArrayList; 

public class PowerSet { 

	public static void main(String[] args) 
	{ 

		String[] set = { "a", "b", "c" }; 

		int index = set.length - 1; 
		ArrayList<ArrayList<String> > result = getSubset(set, index); 
		System.out.println(result); 
	} 

	static ArrayList<ArrayList<String> > getSubset(String[] set, int index) 
	{ 
		ArrayList<ArrayList<String> > allSubsets; 
		if (index < 0) { 
			allSubsets = new ArrayList<ArrayList<String> >(); 
			allSubsets.add(new ArrayList<String>()); 
		} 

		else { 
			allSubsets = getSubset(set, index - 1); 
			String item = set[index]; 
			ArrayList<ArrayList<String> > moreSubsets 
				= new ArrayList<ArrayList<String> >(); 

			for (ArrayList<String> subset : allSubsets) { 
				ArrayList<String> newSubset = new ArrayList<String>(); 
				newSubset.addAll(subset); 
				newSubset.add(item); 
				moreSubsets.add(newSubset); 
			} 
			allSubsets.addAll(moreSubsets); 
		} 
		return allSubsets; 
	} 
}

تعطي الشيفرة السابقة المخرجات التالية:

[[], [a], [b], [a, b], , [a, c], [b, c], [a, b, c]]

مصادر

• صفحة Power Set في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Recursive program to generate power set في توثيق الخوارزميات في موقع GeeksforGeeks.