Algoritm de combinație: imprimați toate combinațiile posibile ale lui R
Ce este Combinația?
Combinația este un fel de aranjare a unor obiecte date. În termeni matematici, Combinația este un set de alegeri/selecție de elemente dintr-un set unic de articole/obiecte. Aici, ordinea articolelor nu contează. Este, de asemenea, cunoscută ca metoda de calculare a rezultatului total al unui eveniment, unde ordinea rezultatului nu contează.
De exemplu, vi se oferă o geantă cu 5 culori diferite și vi se cere să generați un model cu oricare 3 culori. De asemenea, puteți alege oricare 3 culori din 4, apoi le aranjați în diferite ordine.
Să presupunem că culorile sunt RGYBI (R= Roșu, G= Verde, Y= Galben, B= Albastru, I= Indigo). Deci, modelul posibil poate fi RGB, RGY etc.
Să aruncăm o privire la următoarea figură:

Explicaţie:
- Luați oricare 4 culori din 5 și enumerați-le
- Din fiecare bloc de 4 culori, alegeți oricare 3 și enumerați-le pe toate. De exemplu, am ales doar „RGBI” în figură și am arătat 4 combinații.
- Există o teorie în spatele ei pentru a calcula numărul total de combinații pe care le putem face. O combinație de r elemente din n poate fi prezentată matematic astfel:
Semnul „!” înseamnă factorial. De exemplu,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Spune, 5! = 5*4*3*2*1 = 120
Deci, pentru problema noastră de mai sus, avem 5 culori care înseamnă n = 5 și, în orice moment, trebuie să alegem orice 3. Deci, r = 3. După calcul, obținem,
Un total de 10 combinații de culori sunt posibile pentru scenariul de mai sus.
Analiza complexității timpului pentru Combination
Acum, să presupunem, având în vedere o matrice de dimensiunea n, ni se cere să luăm r elemente din matrice și să realizăm combinații de r elemente.
Dacă este dată o matrice de dimensiune n, atunci va lua O(n2) timpul pentru îndeplinirea sarcinii. De asemenea, dacă vrem să eliminăm intrarea duplicată, atunci,
Trebuie să parcurgem următorii pași:
Pas 1) Sortați datele matricei de intrare în mod ascendent. Complexitatea timpului a sortării este O(n*log(n)).
Pas 2) Creați o altă matrice care conține un element unic din datele matricei temporare date.
Pas 3) Apoi, efectuați funcția de combinare.
Deci, complexitatea timpului total devine = Pe2) + O(nLog(n)). O putem considera O(n2), ca n2 este mult mai mare decât n*log(n).
Metoda-1: Element fix cu recursivitate
În această metodă, vom alege un element, apoi vom găsi o combinație de elemente r-1. Pe măsură ce alegem un element din restul elementului, procedăm recursiv și de aceea se numește element fix și recursivitate.
Să demonstrăm algoritmul pas cu pas cu o diagramă:
Pașii sunt dați mai jos:
Pas 1) În primul strat, luați n-r+1 elemente. Adică am luat 3 elemente.
Pas 2) Alegeți un element din al 2-lea strat și duceți-l până la nr. Deci, dacă luăm „R”, atunci cu R, putem lua G, Y și B.
Pas 3) Alegeți un element din al 3-lea strat și duceți-l până la al n-lea element și formați blocuri care conțin câte 3 elemente fiecare.
Figura de mai sus este valoarea returnată din recursivitate. Doar ultimul strat va fi imprimat.
Pseudo cod
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
Implementare in 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); }
ieșire:
Combinations: RGY RGB RGI RYB RYI RBI GYB GYI GBI YBI
Implementarea în 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)
ieșire:
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
Metoda 2 (Includeți și excludeți fiecare element)
Această metodă se bazează pe identitatea lui Pascal. Anterior am folosit recursiunea pentru calcularea nCr. Aici, metoda este doar divizată în loc de o buclă complexă.
Conform identității lui Pascal,
nCr = (n-1)Cr + (n-1)C(r-1)
Deci, vor exista 2 logici recursive pentru algoritmul recursiv pentru a găsi o combinație de r elemente dintr-o matrice dată de dimensiune n.
- Elementul este inclus în combinația curentă
- Elementul este exclus din Combinația curentă
Pseudo cod
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)
Implementare in 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); }
ieșire:
Combinations: RGY RGB RGI RYB RYI RBI GYB GYI GBI YBI
Implementarea în 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)
ieșire:
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
Gestionarea combinațiilor duplicate
Uneori pot exista elemente duplicate în matricea de intrare.
De exemplu,
- Matricea de intrare conține n = {5, 2, 3, 1, 5}.
- Aici, putem vedea că 5 este prezent de 2 ori.
- Acum, dacă vrem să rulăm codul pentru această matrice, unele combinații vor fi repetate.
- Vom găsi {5, 2, 5}, {5, 2, 3} etc sau orice combinație care conține 5, se va repeta.
Putem folosi aceste două metode:
- Sortați matricea de intrare. Sortarea va dura O(nlog(n)) timp.
- Apoi crește valoarea lui i, în timp ce valoarea i și valoarea i+1 sunt aceleași. Practic, puneți următoarele două rânduri de cod în funcția Combination.
// For c/c++ while(inputArray[i] == inputArray[i+1]){ i++; }
# for python while inputArray[i]==inputArray[i+1]: i+=1
Utilizarea unui dicționar sau a unei hărți neordonate pentru a urmări combinațiile duplicate
Deci, dacă nu dorim să sortăm elementele pentru urmărirea duplicatului, putem urma pașii dați.
Pas 1) Declarați un dicționar global sau hashmap.
Pas 2) Împingeți combinația generată în hashmap și creșteți valoarea cu unu. Combinația este cheia, iar apariția lor sunt valori.
Pas 3) când funcția se termină de rulat, pur și simplu vom tipări toate cheile din hashmap sau dicționar.
Iată implementarea în python
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)
ieșire:
RGY RGB RGI RYB RYI RBI RBB RIB GYB GYI GBI GBB GIB YBI YBB YIB BIB
Aici, puteți vedea că intrarea a fost „RGYBIB”. În general, ar trebui să apară unele combinații duplicate. Dar, deoarece am folosit un dicționar și am tratat fiecare Combinație ca cheie, putem tipări numai Combinația unică.
Acum, dacă scrieți „print(unique_combination)”, puteți vedea frecvența fiecărei combinații. Se va arăta astfel:
{'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}
Deci, putem vedea că RGB, RYB, GYB au apărut de 2 ori. Complexitatea de timp a inserării cheii într-un dicționar este practic O(1). Deci, dacă utilizați un dicționar, atunci complexitatea de timp totală pentru rularea codului va fi:
O(1) + O(n*n)
Echivalent cu O(n*n).
Folosind metoda anterioară pentru a urmări duplicatele, avem nevoie de O(n*log(n)) pentru sortare; pentru comparare, avem nevoie de O(n), iar funcția în sine ia O(n*n). Complexitatea totală a timpului va fi:
O(n*log(n)) + O(n) +O(n*n)