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 kijken naar het vervolgwing figuur:

Kleurencombinatie
Kleurencombinatie

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:
Formule van combinatie

Formule van combinatie

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:

Combinatie (combination)

Voor het bovenstaande scenario zijn in totaal 10 kleurencombinaties mogelijk.

De tijd complexiteitsanalyse 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 nodig2) tijd om de taak uit te voeren. Als we de dubbele invoer willen verwijderen, dan:

We moeten het volgende uitvoerenwing stappen:

Stap 1) Sorteer de invoerarraygegevens oplopende wijze. De Tijd Complexsorteergraad 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.

Dus totale tijd complexiteit wordt = Aan2) + O(nLog(n)). We kunnen het beschouwen als O(n2), als n2 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:

Vast element met recursie

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. Voorheen gebruikten we recursie voor het berekenen van nCr. Hier is de methode gewoon verdeeld in plaats van een complex 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.

  1. Element is opgenomen in de huidige combinatie
  2. 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 waarde van i en i+1 hetzelfde zijn. Kortom, de following 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 en GYB 2 keer zijn voorgekomen. De tijd complexDe kwaliteit van het invoegen van de sleutel in een woordenboek is in principe O(1). Dus als je een woordenboek gebruikt, dan is de totale tijd complexheid voor het uitvoeren van de code zal zijn:

O(1) + O(n*n)

Equivalent aan O(n*n).

Als we de vorige methode gebruiken om duplicaten bij te houden, hebben we O(n*log(n)) nodig voor het sorteren; om te vergelijken hebben we O(n) nodig, en de functie zelf heeft O(n*n) nodig. Totale tijd complexHet zal zijn:

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