برنامج لطباعة المجموعات الجزئية بلغة c++

مرحباً بك، 

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

بالتوفيق.

بتاريخ 11 ساعات قال عبود سمير:

مرحباً بك، 

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

بالتوفيق.

للأسف هذه هي المشكلة لاأعلم ماذا تعني المجموعات الجزئية في المصفوفة

مجموعة جزئية  مصطلح رياضي في فرع نظرية المجموعات . هي العناصر المشتركة بين مجموعتين فإذا كانت مجموعة A عناصر في مجموعة B أيضاً هنا تسمى المجموعة A مجموعة جزئية لوجود عناصر مشتركة بينها مع B أو جميع العناصر مشتركة  بينهم .

فمثلاً وجود مجموعة {1,2,3,4} وجود مجموعة {1,2,7} فهنا العناصر المشتركة {1, 2} وهناص تسمى مجموعة جزئية .

وأيضاً أي مجموعة هي مجموعة جزئية من ذاتها .

وهذه الصورة سوف توضح لك : حيث B هنا مجموعة جزئية في المثال الأول على اليمين  :

والمثال الأخر على اليسار B ليست مجموعة جزئية  لأنها لا تشترك مع A:

مرحبا أسماء،

المجموعات الجزئية من مجموعة عناصر تنتمي لمجموهعة ما تكون بالشكل التالي:

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

S تمثل مجموعة العناصر 
a , b , c عناصر مفردة ضمن المجموعة
ثم المجموعات الجزئية من هذه المجموعة

إذا كانت S تحتوي على n من العناصر ، فستحتوي (P (s على 2 قوة N من العناصر

If S has n elements in it then P(s) will have 2^n elements

طريقة اختيار كل مجموعة جزئية تعتمد على الخوارزمية العودية حيث عند كل عنصر في كل مرة لدينا احتمالين إما نضيفه للحل الجزئي أو نتركه مما يعطينا فضاء احتمالي 2 قوة N 

الشيفرة البرمجية :

// CPP للعثور على جميع المجموعات الفرعية عن طريق التراجع.
#include <bits/stdc++.h> 
using namespace std; 

// في المصفوفة A  في كل خطوة لدينا خيارين اثنان
// اختيارات لكل عنصر إما نستطيع
// تجاهل العنصر أو يمكننا تضمين
// عنصر في مجموعتنا الفرعية

void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
				vector<int>& subset, int index) 
{ 
	res.push_back(subset); 
	for (int i = index; i < A.size(); i++) { 

		// تضمين العنصر في المجموعة الفرعية A[i]  
		subset.push_back(A[i]); 

		// الانتقال للخطوة التالية
		subsetsUtil(A, res, subset, i + 1); 

		// تجاهل العنصر و إزالته من المجموعة الفرعية 
		 
		subset.pop_back(); 
	} 

	return; 
} 

// vector الإجرائية التي تعيد المجموعة الجزئية على شكل مصفوفة  
vector<vector<int> > subsets(vector<int>& A) 
{ 
	vector<int> subset; 
	vector<vector<int> > res; 

	// 0 تحديد أول عنصر مع الدليل  
	int index = 0; 
	subsetsUtil(A, res, subset, index); 

	return res; 
} 

// التابع الرئيسي
int main() 
{ 
	// مصفوفة البدء 
	vector<int> array = { 1, 2, 3 }; 

    // res سيخزن جميع المجموعات الفرعية.
    //  (2 ^ n (عدد العناصر داخل المصفوفة))
    // لأنه في كل خطوة لدينا خياران
    // إما تضمين أو تجاهل.
	vector<vector<int> > res = subsets(array); 

	// طباعة النتائج
	for (int i = 0; i < res.size(); i++) { 
		for (int j = 0; j < res[i].size(); j++) 
			cout << res[i][j] << " "; 
		cout << endl; 
	} 

	return 0; 
} 

أمثلة:

الدخل 
Input: array = {1, 2, 3}
مثال أول 
الخرج
Output:  null // المجموعة الفارغة
         1
         1 2
         1 2 3
         1 3
         2
         2 3
         3

مثال ثاني
الدخل
Input: array = {1, 2}
الخرج
Output:  null // المجموعة الفارغة
         1 
         2
         1 2

يوجد توثيق لحسوب يشرح نفس الفكرة ويستخدم شيفرة برمجية مختلفة الرابط من هنا

شرح للخوارزمية العودية/ التعاودية من هنا

بالتوفيق

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

ولكن هذا  الحل في  برنامج C ++ لإنشاء جميع المجموعات الفرعية لمجموعة معينة في ترتيب رسومات Lexico. تطبع هذه الخوارزمية كل التركيبات الممكنة لكل طول من مجموعة الصفيف المحددة بترتيب تصاعدي. التعقيد الزمني لهذه الخوارزمية هو O (n * (2 ^ n)).

#include<iostream>
using namespace std;
void Sorting(int a[], int n) //array sorting {
   int i, j, t;
   for(i = 0; i < n; i++) {
      for(j = i+1; j < n; j++) {
         if(a[i] > a[j]) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
         }
      }
   }
}
void GenAllSubset(int a[], int reqLen, int s, int currLen, bool check[], int len) {
   if(currLen > reqLen)
      return;
   else if (currLen == reqLen) {
      cout<<"\t";
      cout<<"{ ";
      for (int i = 0; i < len; i++) {
         if (check[i] == true) {
            cout<<a[i]<<" ";
         }
      }
      cout<<"}\n";
      return;
   }
   if (s == len) {
      return;
   }
   check[s] = true;
   GenAllSubset(a, reqLen, s + 1, currLen + 1, check, len);
   check[s] = false;
   GenAllSubset(a, reqLen, s + 1, currLen, check, len);
}
int main() {
   int i, n;
   bool ch[n];
   cout<<"Enter the number of element array have: ";
   cin>>n;
   int arr[n];
   cout<<"\n";
   for (i = 0; i < n; i++) {
      cout<<"Enter "<<i+1<<" element: ";
      cin>>arr[i];
      ch[i] = false;
   }
   Sorting(arr, n);
   cout<<"\nThe all subset of the given set in the lexicographic order: \n";
   cout<<"\t{ }\n";
   for(i = 1; i <= n; i++) {
      GenAllSubset(arr, i, 0, 0, ch, n);
   }
   return 0;
}

الناتج : 

Enter the number of element array have: 6
Enter 1 element:3
Enter 2 element: 2
Enter 3 element: 1
Enter 4 element:7
Enter 5 element:6
Enter 6 element: 5
The all subset of the given set in the lexicographic order:
{ },{ 1 }{ 2 }{ 3 }{ 5 }{ 6 }{ 7 }{ 1 2 }{ 1 3 }{ 1 5 }{ 1 6 }{ 1 7 }{ 2 3 }
{ 2 5 }{ 2 6 }{ 2 7 }{ 3 5 }{ 3 6 }{ 3 7 }{ 5 6 }{ 5 7 }{ 6 7 }{ 1 2 3 }{ 1 2 5 }
{ 1 2 6 }{ 1 2 7 }{ 1 3 5 }{ 1 3 6 }{ 1 3 7 }{ 1 5 6 }{ 1 5 7 }{ 1 6 7 }{ 2 3 5 }
{ 2 3 6 }{ 2 3 7 }{ 2 5 6 }{ 2 5 7 }{ 2 6 7 }{ 3 5 6 }{ 3 5 7 }{ 3 6 7 }{ 5 6 7 }
{ 1 2 3 5 }{ 1 2 3 6 }{ 1 2 3 7 }{ 1 2 5 6 }{ 1 2 5 7 }{ 1 2 6 7 }{ 1 3 5 6 }{ 1 3 5 7 }
{ 1 3 6 7 }{ 1 5 6 7 }{ 2 3 5 6 }{ 2 3 5 7 }{ 2 3 6 7 }{ 2 5 6 7 }{ 3 5 6 7 }{ 1 2 3 5 6 }
{ 1 2 3 5 7 }{ 1 2 3 6 7 }{ 1 2 5 6 7 }{ 1 3 5 6 7 }{ 2 3 5 6 7 }{ 1 2 3 5 6 7 }