خوارزمية المجموعة: طباعة جميع المجموعات الممكنة من R

ما هو الجمع؟

المجموعة هي نوع من الترتيب لبعض الكائنات المحددة. من الناحية الرياضية، الجمع هو مجموعة من الاختيارات/تحديد العناصر من مجموعة فريدة من العناصر/الكائنات. هنا، ترتيب العناصر لا يهم. تُعرف أيضًا باسم طريقة حساب النتيجة الإجمالية لحدث ما، حيث لا يهم ترتيب النتيجة.

على سبيل المثال، تم إعطاؤك حقيبة بها 5 ألوان مختلفة ويطلب منك إنشاء نمط باستخدام أي 3 ألوان. يمكنك أيضًا اختيار أي 3 ألوان من أصل 4، ثم ترتيبها بترتيبات مختلفة.

لنفترض أن الألوان هي RGYBI(R= أحمر، G= أخضر، Y= أصفر، B= أزرق، I= نيلي). لذلك، يمكن أن يكون النمط المحتمل هو RGB، RGY، وما إلى ذلك.

دعونا نلقي نظرة على الشكل التالي:

التفسير:

• خذ 4 ألوان من أصل 5 وقم بإدراجها
• من كل مجموعة من 4 ألوان، اختر أي 3 ألوان واكتبها جميعًا. على سبيل المثال، اخترنا فقط "RGBI" في الشكل وعرضنا 4 تركيبات.
• هناك نظرية وراء ذلك لحساب العدد الإجمالي للمجموعات التي يمكننا صنعها. يمكن تمثيل مجموعة عناصر r من n رياضيًا على النحو التالي:

الإشارة "!" يعني مضروب. على سبيل المثال،
ن! = ن* (ن-1)* (ن-2)* … *3*2*1
قل 5! = 5*4*3*2*1 = 120

لذا، بالنسبة للمشكلة المذكورة أعلاه، لدينا 5 ألوان بمعنى n = 5، وفي أي وقت محدد، نحتاج إلى اختيار أي 3. لذا، r = 3. بعد الحساب، نحصل على:

من الممكن الحصول على إجمالي 10 مجموعات ألوان للسيناريو أعلاه.

تحليل التعقيد الزمني للتركيبة

الآن، لنفترض أنه نظرًا لمصفوفة بحجم n، يُطلب منا أخذ عناصر r من المصفوفة وتنفيذ مجموعات من عناصر r.

إذا تم إعطاء مصفوفة بالحجم n، فسوف يستغرق الأمر O(n²) الوقت لأداء المهمة. وأيضًا، إذا أردنا إزالة الإدخال المكرر، فعندئذٍ،

نحن بحاجة إلى تنفيذ الخطوات التالية:

الخطوة 1) قم بفرز بيانات المصفوفة المدخلة بطريقة تصاعدية. تعقيد الوقت للفرز هو يا(ن*سجل(ن)).

الخطوة 2) قم بإنشاء مصفوفة أخرى تحتوي على عنصر فريد من بيانات المصفوفة المؤقتة المحددة.

الخطوة 3) ثم قم بتنفيذ وظيفة الجمع.

لذا، يصبح التعقيد الزمني الإجمالي = على²) + O(nLog(n)). يمكننا أن نعتبرها O(n²) ، كما ن² أكبر بكثير من n*log(n).

الطريقة الأولى: عنصر ثابت مع التكرار

في هذه الطريقة، سنختار عنصرًا ثم نوجد مجموعة من عناصر r-1. عندما نختار عنصرًا من بقية العنصر، فإننا نقوم بذلك بشكل متكرر، ولهذا السبب يطلق عليه اسم العنصر الثابت والتكرار.

دعنا نوضح الخوارزمية خطوة بخطوة باستخدام رسم تخطيطي:

يتم إعطاء الخطوات أدناه:

الخطوة 1) في الطبقة الأولى، خذ عناصر n-r+1. بمعنى أننا أخذنا 3 عناصر.

الخطوة 2) اختر عنصرًا من الطبقة الثانية وارفعه إلى العدد. لذا، إذا أخذنا "R"، فمن خلال R، يمكننا أخذ G وY وB.

الخطوة 3) اختر عنصرًا من الطبقة الثالثة وانقله إلى العنصر التاسع، وشكل كتلًا تحتوي كل منها على 3 عناصر.

الشكل أعلاه هو قيمة الإرجاع من العودية. سيتم طباعة الطبقة الأخيرة فقط.

كنية Code

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

التنفيذ في C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i < r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

الإخراج:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

التنفيذ في Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i <= end and end - i + 1 >= r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

الإخراج:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

الطريقة الثانية (تضمين واستبعاد كل عنصر)

تعتمد هذه الطريقة على هوية باسكال. في السابق، استخدمنا التكرار لحساب nCr. هنا، تعتمد الطريقة على التقسيم فقط بدلاً من حلقة معقدة.

وفقا لهوية باسكال،

nCr = (n-1)Cr + (n-1)C(r-1)

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

1. يتم تضمين العنصر في المجموعة الحالية
2. تم استبعاد العنصر من المجموعة الحالية

كنية Code

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

التنفيذ في C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j < r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i >= n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

الإخراج:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

التنفيذ في Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

الإخراج:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

التعامل مع المجموعات المكررة

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

على سبيل المثال،

• تحتوي مصفوفة الإدخال على n = {5, 2, 3, 1, 5}.
• هنا، يمكننا أن نرى أن الرقم 5 موجود مرتين.
• الآن، إذا أردنا تشغيل التعليمات البرمجية لهذه المصفوفة، فسيتم تكرار بعض المجموعات.
• سنجد {5، 2، 5}، {5، 2، 3} إلخ أو أي مجموعة تحتوي على 5، سيتم تكرارها.

يمكننا استخدام هاتين الطريقتين:

• فرز مجموعة الإدخال. سيستغرق الفرز وقتًا O(nlog(n)) .
• ثم قم بزيادة قيمة i، مع العلم أن قيمة i وقيمة i+1 متماثلتان. ببساطة، ضع السطرين التاليين من التعليمات البرمجية في دالة التجميع.

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

استخدام قاموس أو خريطة غير مرتبة لـ track من التركيبات المكررة

لذا، إذا كنا لا نريد فرز العناصر لـ tracبعد العثور على النسخة المكررة، يمكننا اتباع الخطوات الموضحة.

الخطوة 1) قم بتعريف قاموس عالمي أو hashmap.
الخطوة 2) ادفع المجموعة التي تم إنشاؤها إلى علامة التجزئة وقم بزيادة القيمة بمقدار واحد. التركيبة هي المفتاح، وحدوثها هو القيم.
الخطوة 3) عند الانتهاء من تشغيل الوظيفة، سنقوم ببساطة بطباعة جميع المفاتيح من الهاشماب أو القاموس.

وهنا التنفيذ في بيثون

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

الإخراج:

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

هنا، يمكنك أن ترى أن الإدخال كان "RGYBIB". بشكل عام، ينبغي أن تحدث بعض المجموعات المكررة. ولكن نظرًا لأننا استخدمنا قاموسًا وعاملنا كل مجموعة كمفتاح، فيمكننا طباعة المجموعة الفريدة فقط.

الآن، إذا كتبت "print(unique_combination)"، فيمكنك رؤية تردد كل مجموعة. وسوف تظهر مثل هذا:

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

لذا، يمكننا أن نرى أن RGB وRYB وGYB حدثت مرتين. إن التعقيد الزمني لإدخال المفتاح إلى القاموس هو O(2) بشكل أساسي. لذا، إذا كنت تستخدم القاموس، فإن التعقيد الزمني الإجمالي لتشغيل الكود سيكون:

يا(1) + يا(ن*ن)

أي ما يعادل O(ن*ن).

باستخدام الطريقة السابقة لـ tracفي حالة وجود k تكرار، نحتاج إلى O(n*log(n)) للفرز؛ وللمقارنة، نحتاج إلى O(n)، وتستغرق الدالة نفسها O(n*n). إجمالي التعقيد الزمني سيكون:

O(n*log(n)) + O(n) +O(n*n)

الأسئلة الشائعة