Algoritam kombinacije: Ispišite sve moguće kombinacije R

Što je kombinacija?

Kombinacija je vrsta rasporeda nekih zadanih predmeta. U matematičkom smislu, kombinacija je skup izbora/odabir stavki iz jedinstvenog skupa stavki/objekata. Ovdje redoslijed stavki nije bitan. Također je poznata kao metoda za izračunavanje ukupnog ishoda događaja, pri čemu redoslijed ishoda nije bitan.

Na primjer, dana vam je torba s 5 različitih boja i od vas se traži da generirate uzorak s bilo koje 3 boje. Također možete odabrati bilo koje 3 boje od 4, a zatim ih poredati različitim redoslijedom.

Pretpostavimo da su boje RGYBI(R= crvena, G= zelena, Y= žuta, B= plava, I= indigo). Dakle, mogući uzorak može biti RGB, RGY itd.

Pogledajmo sljedeću sliku:

Objašnjenje:

Uzmite bilo koje 4 boje od 5 i navedite ih
Iz svakog bloka od 4 boje odaberite bilo koje 3 i sve ih navedite. Na primjer, odabrali smo samo "RGBI" na slici i prikazali 4 kombinacije.
Iza toga postoji teorija za izračunavanje ukupnog broja kombinacija koje možemo napraviti. Kombinacija r elemenata od n može se matematički prikazati kao:

Znak "!" znači faktorijel, Na primjer,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Reci, 5! = 5*4*3*2*1 = 120

Dakle, za naš gornji problem, imamo 5 boja što znači n = 5, i u bilo kojem trenutku trebamo odabrati bilo koje 3. Dakle, r = 3. Nakon izračuna, dobivamo,

Za gornji scenarij moguće je ukupno 10 kombinacija boja.

Analiza vremenske složenosti za kombinaciju

Sada, recimo, s obzirom na niz veličine n, od nas se traži da uzmemo r elemenata iz niza i izvedemo kombinacije r elemenata.

Ako je dan niz veličine n, tada će uzeti O(n²) vrijeme za izvršenje zadatka. Također, ako želimo ukloniti dupli unos, tada,

Moramo izvršiti sljedeće korake:

Korak 1) Poredajte podatke ulaznog niza uzlazno. Vremenska složenost sortiranja je O(n*log(n)).

Korak 2) Stvorite još jedno polje koje sadrži jedinstveni element iz zadanih podataka privremenog polja.

Korak 3) Zatim izvedite funkciju kombiniranja.

Dakle, ukupna vremenska složenost postaje = Na²) + O(nLog(n)). Možemo ga smatrati O(n²), kao n²mnogo je veći od n*log(n).

Metoda-1: Fiksni element s rekurzijom

U ovoj metodi odabrat ćemo element, a zatim pronaći kombinaciju r-1 elemenata. Dok biramo element od ostatka elementa, radimo rekurzivno, i zato se to zove fiksni element i rekurzija.

Demonstrirajmo algoritam korak po korak pomoću dijagrama:

Koraci su navedeni u nastavku:

Korak 1) U prvom sloju uzmite n-r+1 elemenata. Znači uzeli smo 3 elementa.

Korak 2) Odaberite element s 2. sloja i odnesite ga do br. Dakle, ako uzmemo "R", tada s R možemo uzeti G, Y i B.

Korak 3) Odaberite element iz 3. sloja i odnesite ga do n-tog elementa, te oblikujte blokove koji sadrže po 3 elementa.

Gornja slika je povratna vrijednost iz rekurzije. Ispisat će se samo posljednji sloj.

Pseudo kod

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

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

Izlaz:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementacija u 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)

Izlaz:

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 (uključi i isključi svaki element)

Ova se metoda temelji na Pascalovom identitetu. Prethodno smo koristili rekurziju za izračunavanje nCr. Ovdje je metoda samo podijeljena umjesto složene petlje.

Prema Pascalovom identitetu,

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

Dakle, postojat će 2 rekurzivne logike za rekurzivni algoritam za pronalaženje kombinacije r elemenata iz zadanog niza veličine n.

Element je uključen u trenutnu kombinaciju
Element je isključen iz trenutne kombinacije

Pseudo kod

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)

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

Izlaz:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementacija u 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)

Izlaz:

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

Rukovanje dvostrukim kombinacijama

Ponekad u ulaznom nizu mogu postojati dupli elementi.

Na primjer,

Ulazni niz sadrži n = {5, 2, 3, 1, 5}.
Ovdje možemo vidjeti da je 5 prisutno 2 puta.
Sada, ako želimo pokrenuti kod za ovaj niz, neke kombinacije će se ponoviti.
Pronaći ćemo {5, 2, 5}, {5, 2, 3} itd. ili bilo koju kombinaciju koja sadrži 5, ponovit će se.

Možemo koristiti ove dvije metode:

Sortiraj ulazni niz. Razvrstavanje će trajati O(nlog(n)) vremena.
Zatim povećajte vrijednost i, dok su i vrijednost i i+1 vrijednost iste. U osnovi stavite sljedeća dva retka koda u funkciju Kombinacija.

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

Korištenje rječnika ili nesređene karte za praćenje dvostrukih kombinacija

Dakle, ako ne želimo sortirati elemente za praćenje duplikata, možemo slijediti navedene korake.

Korak 1) Deklarirajte globalni rječnik ili hashmap.
Korak 2) Gurnite generiranu kombinaciju na hashmap i povećajte vrijednost za jedan. Kombinacija je ključ, a njihova pojava su vrijednosti.
Korak 3) kada funkcija završi s radom, jednostavno ćemo ispisati sve ključeve iz hashmapa ili rječnika.

Evo implementacije u pythonu

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)

Izlaz:

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

Ovdje možete vidjeti da je unos bio "RGYBIB." Općenito, trebale bi se pojaviti neke dvostruke kombinacije. Ali kako smo koristili rječnik i svaku kombinaciju tretirali kao ključ, možemo ispisati samo jedinstvenu kombinaciju.

Sada, ako napišete "print(unique_combination)", možete vidjeti učestalost svake kombinacije. Prikazat će se ovako:

{'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}

Dakle, možemo vidjeti da su se RGB, RYB, GYB pojavili 2 puta. Vremenska složenost umetanja ključa u rječnik je u osnovi O(1). Dakle, ako koristite rječnik, tada će ukupna vremenska složenost za izvođenje koda biti:

O(1) + O(n*n)

Ekvivalent O(n*n).

Koristeći prethodnu metodu za praćenje duplikata, trebamo O(n*log(n)) za sortiranje; za usporedbu nam treba O(n), a sama funkcija uzima O(n*n). Ukupna vremenska složenost bit će:

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

Možda ti se svidi:

Što je kombinacija?

Analiza vremenske složenosti za kombinaciju

Metoda-1: Fiksni element s rekurzijom

Pseudo kod

Implementacija u C/C++

Implementacija u Python

POVEZANI ČLANCI

Metoda 2 (uključi i isključi svaki element)

Pseudo kod

Implementacija u C/C++

Implementacija u Python

Rukovanje dvostrukim kombinacijama

Korištenje rječnika ili nesređene karte za praćenje dvostrukih kombinacija

Evo implementacije u pythonu