Combinatiealgoritme: druk alle mogelijke combinaties van R af

Wat is de combinatie?

De Combinatie is een soort arrangement van enkele gegeven objecten. In wiskundige termen is Combinatie een reeks keuzes/selectie van items uit een unieke set items/objecten. Hier doet de volgorde van de items er niet toe. Het staat ook bekend als de methode om de totale uitkomst van een gebeurtenis te berekenen, waarbij de volgorde van de uitkomst er niet toe doet.

U krijgt bijvoorbeeld een tas met vijf verschillende kleuren en u wordt gevraagd een patroon te genereren met drie willekeurige kleuren. Je kunt ook 5 van de 3 kleuren kiezen en ze vervolgens in verschillende volgorden rangschikken.

Laten we aannemen dat de kleuren RGYBI zijn (R= Rood, G= Groen, Y= Geel, B= Blauw, I= Indigo). Het mogelijke patroon kan dus RGB, RGY, enz. zijn.

Laten we eens naar de volgende afbeelding kijken:

Uitleg:

Neem 4 van de 5 kleuren en noteer ze
Kies uit elk blok van 4 kleuren 3 kleuren en noteer ze allemaal. We hebben bijvoorbeeld alleen ‘RGBI’ in de figuur gekozen en vier combinaties weergegeven.
Er zit een theorie achter om het totale aantal combinaties te berekenen dat we kunnen maken. Een combinatie van r-elementen uit n kan wiskundig worden weergegeven als:

Het teken "!" betekent het faculteit. Bijvoorbeeld,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Zeg, 5! = 5*4*3*2*1 = 120

Dus voor ons bovenstaande probleem hebben we 5 kleuren, wat n = 5 betekent, en op elk gegeven moment moeten we er 3 kiezen. Dus r = 3. Na het berekenen krijgen we:

Voor het bovenstaande scenario zijn in totaal 10 kleurencombinaties mogelijk.

De tijdcomplexiteitsanalyse voor combinatie

Laten we nu zeggen dat, gegeven een array met grootte n, ons wordt gevraagd r-elementen uit de array te nemen en combinaties van r-elementen uit te voeren.

Als een array met grootte n wordt gegeven, is O(n nodig²) tijd om de taak uit te voeren. Als we de dubbele invoer willen verwijderen, dan:

We moeten de volgende stappen uitvoeren:

Stap 1) Sorteer de invoerarraygegevens op oplopende wijze. De tijdcomplexiteit van sorteren is O(n*log(n)).

Stap 2) Maak nog een array met een uniek element uit de opgegeven tijdelijke arraygegevens.

Stap 3) Voer vervolgens de combinatiefunctie uit.

De totale tijdcomplexiteit wordt dus = Aan²) + O(nLog(n)). We kunnen het beschouwen als O(n²), als n²is veel groter dan n*log(n).

Methode-1: Vast element met recursie

Bij deze methode kiezen we een element en vinden we vervolgens een combinatie van r-1-elementen. Terwijl we een element uit de rest van het element kiezen, doen we dat recursief, en daarom wordt het vast element en recursie genoemd.

Laten we het algoritme stap voor stap demonstreren met een diagram:

Hieronder vindt u de stappen:

Stap 1) Neem in de eerste laag n-r+1 elementen. Dit betekent dat we 3 elementen hebben genomen.

Stap 2) Kies een element uit de 2e laag en neem het mee naar nr. Dus als we ‘R’ nemen, kunnen we met R G, Y en B nemen.

Stap 3) Kies een element uit de derde laag en breng het naar het zoveelste element, en vorm blokken van elk drie elementen.

De bovenstaande afbeelding is de retourwaarde van de recursie. Alleen de laatste laag wordt afgedrukt.

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

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

Output:

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

implementatie in 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)

Output:

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

Methode 2 (elk element opnemen en uitsluiten)

Deze methode is gebaseerd op de identiteit van Pascal. Eerder gebruikten we recursie om nCr te berekenen. Hier is de methode gewoon verdeeld in plaats van een complexe lus.

Volgens de identiteit van Pascal,

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

Er zijn dus twee recursieve logica voor het recursieve algoritme om een combinatie van r-elementen te vinden uit een gegeven array met grootte n.

Element is opgenomen in de huidige combinatie
Element is uitgesloten van de huidige combinatie

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)

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

Output:

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

implementatie in 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)

Output:

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

Dubbele combinaties verwerken

Soms kunnen er dubbele elementen in de invoerarray voorkomen.

Bijvoorbeeld

De invoerarray bevat n = {5, 2, 3, 1, 5}.
Hier kunnen we zien dat 5 2 keer aanwezig is.
Als we nu de code voor deze array willen uitvoeren, zullen sommige combinaties worden herhaald.
We vinden {5, 2, 5}, {5, 2, 3} etc. of elke combinatie die 5 bevat, wordt herhaald.

We kunnen deze twee methoden gebruiken:

Sorteer de invoerarray. Het sorteren kost O(nlog(n)) tijd.
Verhoog vervolgens de waarde van i, terwijl de i-waarde en i+1-waarde hetzelfde zijn. Plaats in principe de volgende twee regels code in de combinatiefunctie.

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

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

Een woordenboek of ongeordende kaart gebruiken om dubbele combinaties bij te houden

Dus als we de elementen voor het volgen van het duplicaat niet willen sorteren, kunnen we de gegeven stappen volgen.

Stap 1) Verklaar een mondiaal woordenboek of hashmap.
Stap 2) Duw de gegenereerde combinatie naar de hashmap en verhoog de waarde met één. De combinatie is de sleutel, en hun voorkomen zijn waarden.
Stap 3) wanneer de functie klaar is, printen we eenvoudigweg alle sleutels uit de hashmap of het woordenboek.

Hier is de implementatie in 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)

Output:

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

Hier kunt u zien dat de invoer "RGYBIB" was. Over het algemeen zouden er enkele dubbele combinaties moeten voorkomen. Maar omdat we een woordenboek gebruikten en elke combinatie als sleutel behandelden, kunnen we alleen de unieke combinatie afdrukken.

Als u nu 'print(unieke_combinatie)' schrijft, kunt u de frequentie van elke combinatie zien. Het zal als volgt worden weergegeven:

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

We kunnen dus zien dat RGB, RYB, GYB 2 keer zijn voorgekomen. De tijdcomplexiteit van het invoegen van de sleutel in een woordenboek is in principe O(1). Dus als u een woordenboek gebruikt, is de totale tijdcomplexiteit voor het uitvoeren van de code:

O(1) + O(n*n)

Equivalent aan O(n*n).

Met behulp van de vorige methode om duplicaten te volgen, hebben we O(n*log(n)) nodig voor het sorteren; voor het vergelijken hebben we O(n) nodig, en de functie zelf heeft O(n*n). De totale tijdcomplexiteit zal zijn:

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

Je houdt misschien van:

Wat is de combinatie?

De tijdcomplexiteitsanalyse voor combinatie

Methode-1: Vast element met recursie

Pseudo-code

Implementatie in C/C++

implementatie in Python

GERELATEERDE ARTIKELEN

Methode 2 (elk element opnemen en uitsluiten)

Pseudo-code

Implementatie in C/C++

implementatie in Python

Dubbele combinaties verwerken

Een woordenboek of ongeordende kaart gebruiken om dubbele combinaties bij te houden

Hier is de implementatie in Python