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)‎.

مصادر

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