حساب مجموع كل العناصر من كل المجاميع الفرعية الممكن

تحسب هذه الخوارزمية مجموع جميع العناصر المتكوّنة من كل المجموعات الفرعية التي يمكن تكوينها من مجموعة تضمّ n من الأعداد الطبيعية.

فمثلًا:

المدخلات : n = 2

المخرجات : 6
المجموعات الفرعية التي يمكن إنشاؤها: {{1}, {2}, {1, 2}}.
مجموع العناصر في المجموعات الفرعية:
1 + 2 + 1 + 2 = 6

المدخلات : n = 3
المخرجات : 24
المجموعات الفرعية التي يمكن إنشاؤها: {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
مجموع العناصر في المجموعات الفرعية:
1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3)

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

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

ولكن يمكن أن تنفّذ الخوارزمية بكفاءة أكبر بالاعتماد على حقيقة مفادها أنّ كل عدد من 1 إلى n يظهر ‎2^(n-1)‎ مرة؛ لذا فإنّ المجموع الذي نرغب في الحصول عليه هو ‎(1 + 2 + 3 + ..+ n) * 2^(n-1)‎. ويمكن كتابته بالصيغة التالية: ‎(n * (n + 1)/2) * 2^(n-1)‎.

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

• C++‎:

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

unsigned long long findSumSubsets(int n) 
{ 
	// مجموع عناصر المجموعات الفرعية يساوي
	// (n * (n + 1) / 2) * pow(2, n-1) 
	return (n * (n + 1) / 2) * (1 << (n - 1)); 
} 

int main() 
{ 
	int n = 3; 
	cout << findSumSubsets(n); 
	return 0; 
}

• بايثون:

def findSumSubsets( n): 

	# مجموع عناصر المجموعات الفرعية يساوي
	# (n * (n + 1) / 2) * pow(2, n-1) 
	return (n * (n + 1) / 2) * (1 << (n - 1)) 
	
# اختبار الدالة السابقة
n = 3
print(findSumSubsets(n))

• جافا:

class GFG { 
	static long findSumSubsets(int n) 
	{ 
		// مجموع عناصر المجموعات الفرعية يساوي
		// (n * (n + 1) / 2) * pow(2, n-1) 
		return (n * (n + 1) / 2) * (1 << (n - 1)); 
	} 

	// اختبار الدالة السابقة
	public static void main(String[] args) 
	{ 
		int n = 3; 
		System.out.print(findSumSubsets(n)); 
	} 
}

مصادر

• صفحة Sum of all subsets of a set formed by first n natural numbers في توثيق الخوارزميات في موقع GeeksforGeeks.