Algorithms/min max product subset

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

إيجاد مجموعة فرعية من مصفوفة تعطي أقل حاصل ضرب ممكن

المطلوب في هذه المسألة هو استخراج مجموعة فرعية من العناصر الموجودة في مصفوفة من الأعداد الصحيحة، بشرط الحصول على أقل قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية، ويمكن أن تتكوّن المجموعة الفرعية من عنصر واحدٍ فقط.

مثال:

المدخلات : a[] = { -1, -1, -2, 4, 3 }
المخرجات : ‎-24
التوضيح : ‎( -2 * -1 * -1 * 4 * 3 ) = -24

المدخلات : a[] = { -1, 0 }
المخرجات : ‎-1
التوضيح : ‎-1 عنصر واحد فقط 

المدخلات : a[] = { 0, 0, 0 }
المخرجات : 0

خطوات الخوارزمية

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

أما الحل الأفضل فيستند على الحقائق التالية:

• إن كان هناك عدد زوجي من الأعداد السالبة ولم يكن هناك أصفار، فإنّ النتيجة هي حاصل ضرب جميع الأعداد باستثناء أكبر عدد سالب.
• إن كان هناك عدد فردي من الأعداد السالبة ولم يكن هناك أصفار، فإنّ النتيجة هي حاصل ضرب جميع الأعداد.
• إن كان هناك أصفار وأعداد موجبة ولم يكن هناك أعداد سالبة، فإنّ النتيجة هي 0.
• هناك حالة استثنائية وهي عندما تكون جميع الأعداد موجبة فتكون النتيجة حينئذٍ هي أصغر عدد موجب.

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

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

• C++‎:

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

int minProductSubset(int a[], int n) 
{ 
	if (n == 1) 
		return a[0]; 

	// إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب
	// وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر
	int max_neg = INT_MIN; 
	int min_pos = INT_MAX; 
	int count_neg = 0, count_zero = 0; 
	int prod = 1; 
	for (int i = 0; i < n; i++) { 

		// إن كان العدد صفرًا فلن نضربه مع الناتج
		if (a[i] == 0) { 
			count_zero++; 
			continue; 
		} 

		// إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب
		if (a[i] < 0) { 
			count_neg++; 
			max_neg = max(max_neg, a[i]); 
		} 

		// تتبع أصغر عدد موجب في المصفوفة
		if (a[i] > 0) 
			min_pos = min(min_pos, a[i]);		 

		prod = prod * a[i]; 
	} 

	// إن كانت جميع الأعداد في المصفوفة أصفارًا
	// أو كان هناك أعداد سالبة في المصفوفة
	if (count_zero == n || 
	(count_neg == 0 && count_zero > 0)) 
		return 0; 

	// إن كانت جميع الأعداد موجبة
	if (count_neg == 0) 
		return min_pos; 

	// إن كان هناك عدد زوجي من الأعداد السالبة
	// ولم يساو عداد الأعداد السالبة الصفر
	if (!(count_neg & 1) && count_neg != 0) { 

		// تكون النتيجة فيما عدا ذلك
		// حاصل ضرب جميع الأعداد غير الصفرية
		// مقسومًا على أكبر عدد سالب
		prod = prod / max_neg; 
	} 

	return prod; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int a[] = { -1, -1, -2, 4, 3 }; 
	int n = sizeof(a) / sizeof(a[0]); 
	cout << minProductSubset(a, n); 
	return 0; 
}

• بايثون:

def minProductSubset(a, n) :	 
	if (n == 1) : 
		return a[0] 

	# إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب 
	# وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر 
	max_neg = float('-inf') 
	min_pos = float('inf') 
	count_neg = 0
	count_zero = 0
	prod = 1
	for i in range(0,n) : 

		# إن كان العدد صفرًا فلن نضربه مع الناتج 
		if (a[i] == 0) :	 
			count_zero = count_zero + 1
			continue

		# إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب 
		if (a[i] < 0) :	 
			count_neg = count_neg + 1
			max_neg = max(max_neg, a[i]) 
		
		# تتبع أصغر عدد موجب في المصفوفة 
		if (a[i] > 0) : 
			min_pos = min(min_pos, a[i]) 

		prod = prod * a[i] 
	

	# إن كانت جميع الأعداد في المصفوفة أصفارًا
	# أو كان هناك أعداد سالبة في المصفوفة 
	if (count_zero == n or (count_neg == 0
					and count_zero > 0)) : 
		return 0; 

	# إن كانت جميع الأعداد موجبة 
	if (count_neg == 0) : 
		return min_pos 

	# إن كان هناك عدد زوجي من الأعداد السالبة
	# ولم يساو عداد الأعداد السالبة الصفر
	if ((count_neg & 1) == 0 and
					count_neg != 0) : 

		#  تكون النتيجة فيما عدا ذلك 
		# حاصل ضرب جميع الأعداد غير الصفرية
		# مقسومًا على أكبر عدد سالب
		prod = int(prod / max_neg) 

	return prod; 

# اختبار الدالة السابقة
a = [ -1, -1, -2, 4, 3 ] 
n = len(a) 
print (minProductSubset(a, n))

• جافا:

class GFG { 

	static int minProductSubset(int a[], int n) 
	{ 
		if (n == 1) 
			return a[0]; 
	
		// إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب 
		// وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر 
		int negmax = Integer.MIN_VALUE; 
		int posmin = Integer.MAX_VALUE; 
		int count_neg = 0, count_zero = 0; 
		int product = 1; 
		
		for (int i = 0; i < n; i++) 
		{ 
			
			//  إن كان العدد صفرًا فلن نضربه مع الناتج 
			if(a[i] == 0){ 
				count_zero++; 
				continue; 
			} 
			
		// إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب 
		if(a[i] < 0) 
		{ 
				count_neg++; 
				negmax = Math.max(negmax, a[i]); 
			} 
			
			// تتبع أصغر عدد موجب في المصفوفة 
			if(a[i] > 0 && a[i] < posmin) 
			posmin = a[i]; 
			
			product *= a[i]; 
		} 
		
		// إن كانت جميع الأعداد في المصفوفة أصفارًا 
		// أو كان هناك أعداد سالبة في المصفوفة 
		if (count_zero == n || 
			(count_neg == 0 && count_zero > 0)) 
			return 0; 
			
		// إن كانت جميع الأعداد موجبة
		if (count_neg == 0) 
			return posmin; 
			
		// إن كان هناك عدد زوجي من الأعداد السالبة
		// ولم يساو عداد الأعداد السالبة الصفر
		if (count_neg % 2 == 0 && count_neg != 0) 
		{ 
	
			// تكون النتيجة فيما عدا ذلك 
			// حاصل ضرب جميع الأعداد غير الصفرية 
			// مقسومًا على أكبر عدد سالب 
			product = product / negmax; 
		} 
		
		return product; 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		
		int a[] = { -1, -1, -2, 4, 3 }; 
		int n = 5; 
		
		System.out.println(minProductSubset(a, n)); 
	} 
}

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

-24

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

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n)‎.

إيجاد مجموعة فرعية من مصفوفة تعطي أكبر حاصل ضرب ممكن

المطلوب في هذه المسألة هو استخراج مجموعة فرعية من العناصر الموجودة في مصفوفة من الأعداد الصحيحة، بشرط الحصول على أكبر قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية، ويمكن أن تتكوّن المجموعة الفرعية من عنصر واحدٍ فقط.

مثال:

المدخلات : a[] = { -1, -1, -2, 4, 3 }
المخرجات : ‎24
التوضيح : ‎( -2 * -1 * 4 * 3 ) = 24

المدخلات : a[] = { -1, 0 }
المخرجات : 0
التوضيح : ‎0 عنصر واحد فقط 

المدخلات : a[] = { 0, 0, 0 }
المخرجات : 0

خطوات الخوارزمية

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

أما الحل الأفضل فيستند على الحقائق التالية:

• إن كان هناك عدد زوجي من الأعداد السالبة ولم يكن هناك أصفار، فإنّ النتيجة هي حاصل ضرب جميع الأعداد.
• إن كان هناك عدد فردي من الأعداد السالبة ولم يكن هناك أصفار، فإنّ النتيجة هي حاصل ضرب جميع الأعداد باستثناء أكبر عدد سالب.
• إن كان هناك أصفار فإن النتيجة هي حاصل ضرب جميع الأعداد باستثناء الأصفار.
• هناك حالة استثنائية وهي عندما يكون هناك عدد سالب واحد وبقية الأعداد هي أصفار فتكون النتيجة حينئذٍ صفرًا.

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

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

• C++‎:

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

int maxProductSubset(int a[], int n) 
{ 
	if (n == 1) 
		return a[0]; 

	// إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب
	// وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر
	int max_neg = INT_MIN; 
	int count_neg = 0, count_zero = 0; 
	int prod = 1; 
	for (int i = 0; i < n; i++) { 

		// إن كان العدد صفرًا فلن نضربه مع الناتج 
		if (a[i] == 0) { 
			count_zero++; 
			continue; 
		} 

		// إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب 
		if (a[i] < 0) { 
			count_neg++; 
			max_neg = max(max_neg, a[i]); 
		} 

		prod = prod * a[i]; 
	} 

	// إن كانت جميع الأعداد في المصفوفة أصفارًا 
	if (count_zero == n) 
		return 0; 

	// إن كان هناك عدد فردي من الأعداد السالبة
	if (count_neg & 1) { 

		// حالة استثنائية: هناك عدد سالب واحد وبقية الأعداد هي أصفار
		if (count_neg == 1 && 
			count_zero > 0 && 
			count_zero + count_neg == n) 
			return 0; 

		// إن لم يتحقق أي من الشروط السابقة
		// فإن النتيجة هي حاصل ضرب جميع الأعداد
		// باستثناء الأصفار مقسومًا على أكبر عدد سالب
		prod = prod / max_neg; 
	} 

	return prod; 
} 

int main() 
{ 
	int a[] = { -1, -1, -2, 4, 3 }; 
	int n = sizeof(a) / sizeof(a[0]); 
	cout << maxProductSubset(a, n); 
	return 0; 
}

• بايثون:

def maxProductSubset(a, n): 
	if n == 1: 
		return a[0] 

	# إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب
	# وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر 
	max_neg = -999999999999
	count_neg = 0
	count_zero = 0
	prod = 1
	for i in range(n): 

		# إن كان العدد صفرًا فلن نضربه مع الناتج  
		if a[i] == 0: 
			count_zero += 1
			continue

		# إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب 
		if a[i] < 0: 
			count_neg += 1
			max_neg = max(max_neg, a[i]) 

		prod = prod * a[i] 

	# إن كانت جميع الأعداد في المصفوفة أصفارًا 
	if count_zero == n: 
		return 0

	# إن كان هناك عدد فردي من الأعداد السالبة 
	if count_neg & 1: 

		# حالة استثنائية: هناك عدد سالب واحد وبقية الأعداد هي أصفار 
		if (count_neg == 1 and count_zero > 0 and
			count_zero + count_neg == n): 
			return 0

		# إن لم يتحقق أي من الشروط السابقة
		# فإن النتيجة هي حاصل ضرب جميع الأعداد 
		# باستثناء الأصفار مقسومًا على أكبر عدد
		prod = int(prod / max_neg) 

	return prod 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	a = [ -1, -1, -2, 4, 3 ] 
	n = len(a) 
	print(maxProductSubset(a, n))

• جافا:

class GFG { 

	static int maxProductSubset(int a[], int n) { 
		if (n == 1) { 
			return a[0]; 
		} 

		// إحصاء الأعداد السالبة والأصفار وأكبر عدد سالب 
		// وأصغر عدد موجب وحاصل ضرب الأعداد باستثناء الصفر 
		int max_neg = Integer.MIN_VALUE; 
		int count_neg = 0, count_zero = 0; 
		int prod = 1; 
		for (int i = 0; i < n; i++) { 

			//إن كان العدد صفرًا فلن نضربه مع الناتج  
			if (a[i] == 0) { 
				count_zero++; 
				continue; 
			} 

			// إحصاء الأعداد السالبة والاستمرار في متابعة أكبر عدد سالب negative. 
			if (a[i] < 0) { 
				count_neg++; 
				max_neg = Math.max(max_neg, a[i]); 
			} 

			prod = prod * a[i]; 
		} 

		// إن كانت جميع الأعداد في المصفوفة أصفارًا 
		if (count_zero == n) { 
			return 0; 
		} 

		// إن كان هناك عدد فردي من الأعداد السالبة
		if (count_neg % 2 == 1) { 

			// حالة استثنائية: هناك عدد سالب واحد وبقية الأعداد هي أصفار
			if (count_neg == 1
					&& count_zero > 0
					&& count_zero + count_neg == n) { 
				return 0; 
			} 

			// إن لم يتحقق أي من الشروط السابقة
			// فإن النتيجة هي حاصل ضرب جميع الأعداد 
			// باستثناء الأصفار مقسومًا على أكبر عدد سالب 
			prod = prod / max_neg; 
		} 

		return prod; 
	} 

// اختبار التابع السابق
	public static void main(String[] args) { 
		int a[] = {-1, -1, -2, 4, 3}; 
		int n = a.length; 
		System.out.println(maxProductSubset(a, n)); 

	} 
}

مصادر

• صفحة Minimum product subset of an array في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Maximum product subset of an array في توثيق الخوارزميات في موقع GeeksforGeeks.