संयोजन एल्गोरिथ्म: R के सभी संभावित संयोजनों को प्रिंट करें

संयोजन क्या है?

संयोजन कुछ दी गई वस्तुओं की एक तरह की व्यवस्था है। गणितीय शब्दों में, संयोजन वस्तुओं/वस्तुओं के एक अद्वितीय सेट से वस्तुओं के चयन/विकल्पों का एक सेट है। यहाँ, वस्तुओं का क्रम मायने नहीं रखता। इसे किसी घटना के कुल परिणाम की गणना करने की विधि के रूप में भी जाना जाता है, जहाँ परिणाम का क्रम मायने नहीं रखता।

उदाहरण के लिए, आपको 5 अलग-अलग रंगों वाला एक बैग दिया गया है और किसी भी 3 रंगों से पैटर्न बनाने के लिए कहा गया है। आप 3 में से कोई भी 4 रंग चुन सकते हैं, फिर उन्हें अलग-अलग क्रम में व्यवस्थित कर सकते हैं।

मान लें कि रंग RGYBI हैं (R= लाल, G= हरा, Y= पीला, B= नीला, I= नीला)। तो, संभावित पैटर्न RGB, RGY, आदि हो सकता है।

आइये निम्नलिखित चित्र पर नजर डालें:

स्पष्टीकरण:

4 में से कोई भी 5 रंग लें और उनकी सूची बनाएं
4 रंगों के प्रत्येक ब्लॉक से, कोई भी 3 चुनें और उन सभी को सूचीबद्ध करें। उदाहरण के लिए, हमने चित्र में केवल “RGBI” चुना और 4 संयोजन दिखाए।
इसके पीछे एक सिद्धांत है जिससे हम कुल कितने संयोजन बना सकते हैं, इसकी गणना की जा सकती है। n में से r तत्वों के संयोजन को गणितीय रूप से इस प्रकार प्रस्तुत किया जा सकता है:

चिन्ह "!" का मतलब है कारख़ाने का। उदाहरण के लिए,
एन! = एन * (एन-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(n) मान सकते हैं²), जैसा कि एन²n*log(n) से बहुत बड़ा है.

विधि-1: पुनरावृत्ति द्वारा निश्चित तत्व

इस विधि में, हम एक तत्व चुनेंगे और फिर r-1 तत्वों का संयोजन ढूँढेंगे। चूँकि हम बाकी तत्वों में से एक तत्व चुन रहे हैं, इसलिए हम पुनरावर्ती रूप से ऐसा कर रहे हैं, और इसीलिए इसे निश्चित तत्व और पुनरावर्तन कहा जाता है।

आइये एक चित्र के साथ एल्गोरिथ्म को चरण दर चरण प्रदर्शित करें:

चरण नीचे दिए गए हैं:

चरण 1) पहली परत में n-r+1 तत्व लें। मतलब हमने 3 तत्व लिए।

चरण 2) दूसरी परत से एक तत्व चुनें और इसे nr तक ले जाएँ। इसलिए, अगर हम “R” लेते हैं, तो R के साथ, हम G, Y और B ले सकते हैं।

चरण 3) तीसरी परत से एक तत्व चुनें और उसे nवें तत्व तक ले जाएं, तथा तीन तत्वों वाले ब्लॉक बनाएं।

उपरोक्त आंकड़ा पुनरावृत्ति से वापसी मूल्य है। केवल अंतिम परत मुद्रित की जाएगी।

छद्म कोड

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++

#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

कार्यान्वयन 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 & 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

विधि 2 (प्रत्येक तत्व को शामिल करें और निकालें)

यह विधि पास्कल की पहचान पर आधारित है। पहले हम nCr की गणना के लिए रिकर्सन का उपयोग करते थे। यहाँ, विधि जटिल लूप के बजाय बस विभाजित है।

पास्कल की पहचान के अनुसार,

एनसीआर = (एन-1)सीआर + (एन-1)सी(आर-1)

इसलिए, आकार n की दी गई सरणी से r तत्वों का संयोजन खोजने के लिए पुनरावर्ती एल्गोरिथ्म के लिए 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++

#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

कार्यान्वयन Python

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, 2 बार उपस्थित है।
अब, यदि हम इस सारणी के लिए कोड चलाना चाहते हैं, तो कुछ संयोजन दोहराए जाएंगे।
हम {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

डुप्लिकेट संयोजनों को ट्रैक करने के लिए शब्दकोश या अव्यवस्थित मानचित्र का उपयोग करना

इसलिए, यदि हम डुप्लिकेट को ट्रैक करने के लिए तत्वों को सॉर्ट नहीं करना चाहते हैं, तो हम दिए गए चरणों का पालन कर सकते हैं।

चरण 1) वैश्विक शब्दकोश या हैशमैप घोषित करें.
चरण 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 2 बार आए हैं। शब्दकोश में कुंजी डालने की समय जटिलता मूल रूप से O(1) है। इसलिए, यदि आप शब्दकोश का उपयोग करते हैं, तो कोड चलाने के लिए कुल समय जटिलता होगी:

ओ(1) + ओ(एन*एन)

O(n*n) के बराबर.

डुप्लिकेट को ट्रैक करने के लिए पिछली विधि का उपयोग करते हुए, हमें सॉर्टिंग के लिए O(n*log(n)) की आवश्यकता होती है; तुलना करने के लिए, हमें O(n) की आवश्यकता होती है, और फ़ंक्शन स्वयं O(n*n) लेता है। कुल समय जटिलता होगी:

ओ(एन*लॉग(एन)) + ओ(एन) +ओ(एन*एन)

संयोजन क्या है?

संयोजन के लिए समय जटिलता विश्लेषण

विधि-1: पुनरावृत्ति द्वारा निश्चित तत्व

छद्म कोड

सी/ में कार्यान्वयनC++

कार्यान्वयन Python

संबंधित आलेख

विधि 2 (प्रत्येक तत्व को शामिल करें और निकालें)

छद्म कोड

सी/ में कार्यान्वयनC++

कार्यान्वयन Python

डुप्लिकेट संयोजनों को संभालना

डुप्लिकेट संयोजनों को ट्रैक करने के लिए शब्दकोश या अव्यवस्थित मानचित्र का उपयोग करना

यहाँ पायथन में कार्यान्वयन है

दैनिक गुरु99 समाचार पत्र