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(n²) 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 = Pe²) + O(nLog(n)). O putem considera O(n²), ca n² 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 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

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 < 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);
}

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 <= 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)

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.

1. Elementul este inclus în combinația curentă
2. Elementul este exclus din Combinația curentă

Pseudo 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)

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 < 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);
}

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

Folosind un dicționar sau o hartă neordonată pentru a track combinații duplicate

Deci, dacă nu vrem să sortăm elementele pentru tracdupă ce am obținut duplicatul, putem urma pașii indicaț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 >= 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 track duplicat, avem nevoie de O(n*log(n)) pentru sortare; pentru comparare, avem nevoie de O(n), iar funcția însăși ia O(n*n). Complexitatea totală în timp va fi:

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

Întrebări frecvente