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

ما هو الجمع؟

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

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

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

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

مزيج الألوان
مزيج الألوان

التفسير:

  • خذ 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 مجموعات ألوان للسيناريو أعلاه.

الوقت كومplexتحليل ity للجمع

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

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

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

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

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

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

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

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

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

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

عنصر ثابت مع العودية

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

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

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

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

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

كود مزيف

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 & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = 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

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

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = 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. هنا، يتم تقسيم الطريقة فقط بدلاً من complex عقدة.

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

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

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

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

كود مزيف

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 & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = 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

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

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = 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 هي نفسها. ضع الفولو بشكل أساسيwing سطرين من التعليمات البرمجية في وظيفة الجمع.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}
# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

استخدام قاموس أو خريطة غير مرتبة لتتبع المجموعات المكررة

لذلك، إذا لم نرغب في فرز العناصر لتتبع التكرار، فيمكننا اتباع الخطوات المحددة.

الخطوة 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 & gt; = 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 قد حدث مرتين. الوقت كومplexإن إمكانية إدخال المفتاح إلى القاموس هي في الأساس O(1). لذلك، إذا كنت تستخدم القاموس، فإن إجمالي الوقت complexستكون ميزة تشغيل الكود هي:

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

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

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

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