Algorithms/difference between sum of two subsets

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

فمثلاً:

المدخلات : n = 4
المخرجات : مجموع عناصر المجموعة الفرعية الأولى = 5 
         مجموع عناصر المجموعة الفرعية الأولى = 5
         الفارق = 0

التوضيح:
المجموعة الفرعية 1: 1 4 
المجموعة الفرعية 2: 2 3

المدخلات : n = 6
المخرجات : مجموع عناصر المجموعة الفرعية الأولى = 10 
         مجموع عناصر المجموعة الفرعية الأولى = 11
         الفارق = 0

التوضيح:
المجموعة الفرعية 1: 1 3 6 
المجموعة الفرعية 2: 2 4 5

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

تعتمد هذه الخوارزمية على حقيقة مفادها أنّ بالإمكان تقسيم أي أربعة أرقام متتابعة إلى مجموعتين، تتضمن المجموعة الأولى العددين الوسطيين، والمجموعة الثانية العددين الطرفيين. إن كان عدد الأرقام n من مضاعفات العدد 4 فإنّ الفارق بين مجموعي عناصر كل من المجموعتين يساوي 0. هذا يعني أنّ مجموع عناصر أي من المجموعتين سيساوي نصف مجموع العناصر في المجموعة الأصلية، والذي يمكن حسابه باستخدام العلاقة: sum = n*(n+1)/2

هناك ثلاث حالات إضافية لا يمكن فيه تقسيم المجموعات إلى 4 عناصر، وسيكون الفارق في هذه الحالات هو 1 و 2 و 3:

1. إن كان الفارق يساوي 1 فإنّ جميع العناصر الأخرى n-1 ستقسّم في مجموعات من 4 عناصر وبهذا فإن مجموع هذه العناصر سيساوي int(sum/2)‎ أما مجموع عناصر النصف الآخر فيساوي int(sum/2+1)‎، ويساوي الفارق بينهما 1 دائمًا.
2. إذا كان باقي قسمة n على 4 يساوي 2 فإنّنا سنتبع الخطوات السابقة نفسها، إذ سنكوّن مجموعات تتضمن أربعة عناصر تبدأ من الرقم 3 وما بعده، وسيتبقى رقمان هما 1 و2، فيضاف الرقم 1 إلى مجموعة ويضاف الرقم 2 إلى الأخرى.
3. إذا كان باقي قسمة n على 4 يساوي 3، فسنكوّن مجموعات تتضمن أربعة عناصر تبدأ من الرقم 4، وستتبقى الأرقام 1 و2 و 3. يضاف الرقمان 1 و 2 إلى مجموعة، ويضاف الرقم 3 إلى الأخرى، وبهذا يساوي الفارق 0 ويكون مجموع عناصر كل مجموعة مساويًا للمقدار sum/2.

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

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

• C++‎:

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

void subsetDifference(int n) 
{ 
	// مجموع عناصر المجموعة الأصلية
	int s = n * (n + 1) / 2; 

	// إن كان عدد العناصر يقبل القسمة على 4
	if (n % 4 == 0) { 
		cout << "First subset sum = "
			<< s / 2; 
		cout << "\nSecond subset sum = "
			<< s / 2; 
		cout << "\nDifference = " << 0; 
	} 
	else { 

		// إن كان باقي القسمة يساوي 1 أو 2.
		// إن كان باقي القسمة يساوي 2 فسنقسم العناصر
		// من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر
		// ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
		// يساوي الفارق في هذه الحالة 1
		if (n % 4 == 1 || n % 4 == 2) { 

			cout << "First subset sum = "
				<< s / 2; 
			cout << "\nSecond subset sum = "
				<< s / 2 + 1; 
			cout << "\nDifference = " << 1; 
		} 

		// نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات
		// ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي
		// 1 و 2 و 3 إلى (1,2) و (3)
		else
		{ 
			cout << "First subset sum = "
				<< s / 2; 
			cout << "\nSecond subset sum = "
				<< s / 2; 
			cout << "\nDifference = " << 0; 
		} 
	} 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int n = 6; 
	subsetDifference(n); 
	return 0; 
}

• بايثون:

def subsetDifference( n ): 

	# مجموع عناصر المجموعة الأصلية 
	s = int(n * (n + 1) / 2) 
	
	# إن كان عدد العناصر يقبل القسمة على 4
	if n % 4 == 0: 
		print("First subset sum = ", int(s / 2)) 
		print("Second subset sum = ",int(s / 2)) 
		print("Difference = " , 0) 

	else: 

		# إن كان باقي القسمة يساوي 1 أو 2. 
		# إن كان باقي القسمة يساوي 2 فسنقسم العناصر 
		# من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر 
		# ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
		#  يساوي الفارق في هذه الحالة 1
		if n % 4 == 1 or n % 4 == 2: 
			print("First subset sum = ",int(s/2)) 
			print("Second subset sum = ",int(s/2)+1) 
			print("Difference = ", 1) 
			
		# نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات 
		# ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي 
		# 1 و 2 و 3 إلى (1,2) و (3) 
		else: 
			print("First subset sum = ", int(s / 2)) 
			print("Second subset sum = ",int(s / 2)) 
			print("Difference = " , 0) 
			
# اختبار الدالة السابقة
n = 6
subsetDifference(n)

• جافا:

import java.util.*; 

class GFG { 
	
	static void subsetDifference(int n) 
	{ 
		// مجموع عناصر المجموعة الأصلية
		int s = n * (n + 1) / 2; 
	
		// إن كان عدد العناصر يقبل القسمة على 4
		if (n % 4 == 0) { 

				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + s / 2); 
				System.out.println("Difference = " + 0); 
		} 
		else { 
	
			// إن كان باقي القسمة يساوي 1 أو 2.
			// إن كان باقي القسمة يساوي 2 فسنقسم العناصر
			// من الرقم 3 إلى الرقم المعطى إلى مجموعات ذات 4 عناصر
			// ونضيف الرقم 1 إلى إحدى المجموعات و 2 إلى مجموعة أخرى
			// يساوي الفارق في هذه الحالة 1
			if (n % 4 == 1 || n % 4 == 2) { 
	
				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + ((s / 2) + 1)); 
				System.out.println("Difference = " + 1); 
			} 
	
			// نضع العناصر من الرقم 4 إلى العدد المعطى في مجموعات 
			//  ذات أربعة عناصر. يمكن تقسيم العناصر الباقية وهي
			// 1 و 2 و 3 إلى (1,2) و (3) 
			else
			{ 
				System.out.println("First subset sum = " + s / 2); 
				System.out.println("Second subset sum = " + s / 2); 
				System.out.println("Difference = " + 0); 
			} 
		} 
	} 
	
	/* اختبار الدالة السابقة */
	public static void main(String[] args) 
	{ 
		int n = 6; 
		subsetDifference(n); 
	} 
}

مصادر

• صفحة Minimize the absolute difference of sum of two subsets في توثيق الخوارزميات في موقع GeeksforGeeks.