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ă:

Combinație de culori
Combinație de culori

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:
Formula de combinare

Formula de combinare

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,

Combinație

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ă:

Element fix cu recursivitate

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.

  1. Elementul este inclus în combinația curentă
  2. 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)

Buletin informativ zilnic Guru99

Începe-ți ziua cu cele mai recente și importante știri despre inteligența artificială, livrate chiar acum.