Kombinasjonsalgoritme: Skriv ut alle mulige kombinasjoner av R

by: Sarah Chen Sarah Chen
Hours oppdatert

Hva er kombinasjonen?

Kombinasjonen er et slags arrangement av noen gitte objekter. I matematiske termer er kombinasjon et sett med valg/utvalg av elementer fra et unikt sett med elementer/objekter. Her spiller rekkefølgen på varene ingen rolle. Det er også kjent som metoden for å beregne det totale utfallet av en hendelse, der rekkefølgen på utfallet ikke spiller noen rolle.

Du får for eksempel en pose med 5 forskjellige farger og bedt om å generere et mønster med 3 forskjellige farger. Du kan også velge hvilke som helst 3 farger av 4, og deretter ordne dem i forskjellige rekkefølger.

La oss anta at fargene er RGYBI(R= Rød, G= Grønn, Y= Gul, B= Blå, I= Indigo). Så det mulige mønsteret kan være RGB, RGY, etc.

La oss ta en titt på følgende figur:

Fargekombinasjon
Fargekombinasjon

Forklaring:

  • Ta hvilke som helst 4 farger av 5 og liste dem opp
  • Fra hver blokk med 4 farger, velg hvilke som helst 3 og liste dem alle. For eksempel valgte vi bare "RGBI" i figuren og viste 4 kombinasjoner.
  • Det er en teori bak det for å beregne det totale antallet kombinasjoner vi kan lage. En kombinasjon av r elementer ut av n kan matematisk presenteres som:
Kombinasjonsformel

Kombinasjonsformel

Skiltet "!" betyr fakultet. For eksempel,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Si, 5! = 5*4*3*2*1 = 120

Så, for problemet ovenfor, har vi 5 farger som betyr n = 5, og til enhver tid må vi velge hvilke som helst 3. Så, r = 3. Etter å ha beregnet, får vi,

Kombinasjon

Totalt 10 fargekombinasjoner er mulig for scenariet ovenfor.

Tidskompleksitetsanalysen for Kombinasjon

Nå, la oss si, gitt en matrise med størrelse n, blir vi bedt om å ta r elementer fra matrisen og utføre kombinasjoner av r elementer.

Hvis en matrise med størrelse n er gitt, vil den ta O(n2) tid til å utføre oppgaven. Dessuten, hvis vi ønsker å fjerne den dupliserte oppføringen,

Vi må utføre følgende trinn:

Trinn 1) Sorter inndatamatrisedataene i stigende måte. Tidskompleksiteten til sortering er O(n*log(n)).

Trinn 2) Opprett en annen matrise som inneholder et unikt element fra de gitte midlertidige matrisedataene.

Trinn 3) Utfør deretter kombinasjonsfunksjonen.

Så total tidskompleksitet blir = På2) + O(nLog(n)). Vi kan vurdere det O(n2), som n2 er mye større enn n*log(n).

Metode-1: Fast element med rekursjon

I denne metoden velger vi et element og finner deretter en kombinasjon av r-1-elementer. Når vi velger et element fra resten av elementet, gjør vi rekursivt, og det er derfor det kalles fast element og rekursjon.

La oss demonstrere algoritmen trinn for trinn med et diagram:

Fast element med rekursjon

Fremgangsmåten er gitt nedenfor:

Trinn 1) I det første laget tar du n-r+1-elementer. Det betyr at vi tok 3 elementer.

Trinn 2) Velg et element fra det andre laget og ta det opp til nr. Så hvis vi tar "R", så med R kan vi ta G, Y og B.

Trinn 3) Velg et element fra det tredje laget og ta det opp til det n'te elementet, og lag blokker som inneholder 3 elementer hver.

Figuren ovenfor er returverdien fra rekursjonen. Bare det siste laget vil bli skrevet ut.

Pseudokode

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

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

Utgang:

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

Gjennomføring i 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)

Utgang:

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

RELATERTE ARTIKLER

Metode 2 (inkluder og ekskluder hvert element)

Denne metoden er basert på Pascals identitet. Tidligere brukte vi rekursjon for å beregne nCr. Her er metoden bare delt i stedet for en kompleks sløyfe.

I følge Pascals identitet,

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

Så, det vil være 2 rekursive logikk for den rekursive algoritmen for å finne en kombinasjon av r elementer fra en gitt matrise med størrelse n.

  1. Element er inkludert i gjeldende kombinasjon
  2. Element er ekskludert fra gjeldende kombinasjon

Pseudokode

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)

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

Utgang:

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

Gjennomføring i 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)

Utgang:

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

Håndtering av dupliserte kombinasjoner

Noen ganger kan det være dupliserte elementer i inndatamatrisen.

For eksempel,

  • Inndatamatrisen inneholder n = {5, 2, 3, 1, 5}.
  • Her kan vi se at 5 er tilstede for 2 ganger.
  • Nå, hvis vi ønsker å kjøre koden for denne matrisen, vil noen kombinasjoner bli gjentatt.
  • Vi finner {5, 2, 5}, {5, 2, 3} osv., ellers vil enhver kombinasjon som inneholder 5 bli gjentatt.

Vi kan bruke disse to metodene:

  • Sorter inndatamatrisen. Sortering vil ta O(nlog(n)) tid.
  • Øk deretter verdien av i, mens i-verdien og i+1-verdien er den samme. Sett i utgangspunktet følgende to linjer med kode i kombinasjonsfunksjonen.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Bruke en ordbok eller uordnet kart for å spore dupliserte kombinasjoner

Så hvis vi ikke vil sortere elementene for å spore duplikatet, kan vi følge de gitte trinnene.

Trinn 1) Erklær en global ordbok eller hashmap.
Trinn 2) Skyv den genererte kombinasjonen til hashmapet og øk verdien med én. Kombinasjonen er nøkkelen, og deres forekomst er verdier.
Trinn 3) når funksjonen er ferdig, skriver vi ut alle nøklene fra hashmap eller ordbok.

Her er implementeringen i 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)

Utgang: 

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

Her kan du se at inngangen var "RGYBIB." Vanligvis bør det forekomme noen dupliserte kombinasjoner. Men siden vi brukte en ordbok og behandlet hver kombinasjon som nøkkelen, kan vi bare skrive ut den unike kombinasjonen.

Nå, hvis du skriver "print(unique_combination)," kan du se hver kombinasjons frekvens. Det vil vise seg slik:

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

Så vi kan se at RGB, RYB, GYB har skjedd 2 ganger. Tidskompleksiteten ved å sette inn nøkkelen til en ordbok er i utgangspunktet O(1). Så hvis du bruker en ordbok, vil den totale tidskompleksiteten for å kjøre koden være:

O(1) + O(n*n)

Tilsvarer O(n*n).

Ved å bruke den forrige metoden for å spore duplikat, trenger vi O(n*log(n)) for sortering; for å sammenligne trenger vi O(n), og selve funksjonen tar O(n*n). Total tidskompleksitet vil være:

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