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

By: Uredništvo Uredništvo
Hours Ažurirano

⚡ Pametni sažetak

Kombinacijski algoritam ispisuje svaki mogući odabir r elemenata iz skupa od n, gdje redoslijed nije bitan. Ovaj resurs objašnjava formulu kombiniranja, vremensku složenost, dvije rekurzivne metode, rukovanje duplikatima i potpuni C. C++i Python implementacije.

  • 🎯 Definicija: Kombinacija odabire r elemenata od n elemenata gdje redoslijed odabira nije važan.
  • 🧮 formula: Broj kombinacija je nCr, jednak n! podijeljeno s r!(nr)!.
  • 🔁 Metoda 1: Rekurzija fiksnih elemenata bira jedan element, a zatim pronalazi kombinacije preostalih r-1 elemenata.
  • ➕ Metoda 2: Rekurzija uključivanja i isključivanja temeljena na Pascalovom identitetu ili koristi ili preskače svaki element.
  • 🗂️ Duplikati: Sortiranje ili rječnik uklanjaju ponovljene kombinacije kada ulaz sadrži duplicirane vrijednosti.
Pročitaj više

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

Kombinacija boja
Kombinacija boja

Objašnjenje:

  • Uzmite bilo koje 4 boje od 5 i navedite ih
  • Iz svakog bloka od 4 boje odaberite bilo koje 3 i navedite ih sve. Na primjer, na slici smo odabrali samo „RGBI“ 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:
Formula kombinacije

Formula kombinacije

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,

Kombinacija

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(n2) 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 = Na2) + O(nLog(n)). Možemo ga smatrati O(n2), kao n2 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:

Fiksni element s rekurzijom

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.

Nadimak 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

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

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

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
Ne propustite:

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.

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

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

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

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 >= 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 neuređene karte za track dupliciranih kombinacija

Dakle, ako ne želimo sortirati elemente za trackralj 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 >= 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).

Korištenjem prethodne metode za track duplikata, za sortiranje nam je potrebno O(n*log(n)); za usporedbu nam je potrebno O(n), a sama funkcija uzima O(n*n). Ukupna vremenska složenost bit će:

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

Pitanja i odgovori

Kombinacija je odabir gdje redoslijed nije bitan, pa se RGB i BGR računaju kao jedan. Permutacija je raspored gdje redoslijed nije bitan, pa se RGB i BGR računaju kao dva. Kombinacije koriste nCr; permutacije koriste nPr.

nCr je broj načina za odabir r elemenata od n elemenata kada redoslijed nije bitan. Izračunava se kao n! podijeljeno s r! puta (nr)!. Na primjer, 5C3 jednako je 10.

Kombinacijski algoritmi pojavljuju se u kvotama na lutriji, odabiru tima ili odbora, pretraživanju podskupova značajki u strojnom učenju, generiranju testnih slučajeva i analizi prostora lozinki ili ključeva. Gdje god odaberete grupu bez obzira na redoslijed, primjenjuju se kombinacije.

Alati umjetne inteligencije mogu generirati sve kombinacije skupa podataka, filtrirati duplikate, pa čak i predložiti najučinkovitiju metodu za velike ulaze. To štedi vrijeme, iako biste trebali provjeriti ispravnost brojanja u odnosu na formulu nCr.

Da. AI asistenti za kodiranje mogu pisati kombinirani kod u C-u, C++, Python, i drugi jezici, uključujući rekurzivne i metode uključivanja i isključivanja. Uvijek testirajte izlaz i provjerite rubne slučajeve poput dupliciranih elemenata ili r većeg od n.

Sažmite ovu objavu uz: