Kombinationsalgoritme: Udskriv alle mulige kombinationer af R

Af: Sarah Chen Sarah Chen
Hours Opdateret

Hvad er kombinationen?

Kombinationen er en slags arrangement af nogle givne objekter. I matematiske termer er kombination et sæt af valg/udvælgelse af elementer fra et unikt sæt af elementer/objekter. Her er rækkefølgen af ​​varerne ligegyldig. Det er også kendt som metoden til at beregne det samlede udfald af en begivenhed, hvor rækkefølgen af ​​udfaldet er ligegyldig.

For eksempel får du en taske med 5 forskellige farver og bedt om at generere et mønster med 3 forskellige farver. Du kan også vælge 3 farver ud af 4, og derefter arrangere dem i forskellige rækkefølger.

Lad os antage, at farverne er RGYBI(R= Rød, G= Grøn, Y= Gul, B= Blå, I= Indigo). Så det mulige mønster kan være RGB, RGY osv.

Lad os se på følgende figur:

Farvekombination
Farvekombination

Forklaring:

  • Tag en hvilken som helst 4 farver ud af 5 og angiv dem
  • Fra hver blok med 4 farver skal du vælge 3 og liste dem alle. For eksempel valgte vi kun "RGBI" i figuren og viste 4 kombinationer.
  • Der er en teori bag det for at beregne det samlede antal kombinationer, vi kan lave. En kombination af r elementer ud af n kan matematisk præsenteres som:
Kombinationsformel

Kombinationsformel

Skiltet "!" betyder faktoriel. For eksempel,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Sig, 5! = 5*4*3*2*1 = 120

Så til vores ovenstående problem har vi 5 farver, der betyder n = 5, og på ethvert givet tidspunkt skal vi vælge 3. Så r = 3. Efter beregning får vi,

Combination (Kombination)

I alt 10 farvekombinationer er mulige for ovenstående scenarie.

Tidskompleksitetsanalysen for Kombination

Lad os nu sige, at givet et array af størrelse n, bliver vi bedt om at tage r elementer fra arrayet og udføre kombinationer af r elementer.

Hvis en matrix af størrelse n er givet, vil den tage O(n2) tid til at udføre opgaven. Også, hvis vi ønsker at fjerne den duplikerede post, så

Vi skal udføre følgende trin:

Trin 1) Sorter input-array-dataene på stigende måde. Tidskompleksiteten ved sortering er O(n*log(n)).

Trin 2) Opret et andet array, der indeholder et unikt element fra de givne midlertidige array-data.

Trin 3) Udfør derefter kombinationsfunktionen.

Så den samlede tidskompleksitet bliver = På2) + O(nLog(n)). Vi kan betragte det som O(n2), som n2 er meget større end n*log(n).

Metode-1: Fast element med rekursion

I denne metode vælger vi et element og finder derefter en kombination af r-1 elementer. Når vi vælger et element fra resten af ​​elementet, gør vi rekursivt, og det er derfor, det kaldes fast element og rekursion.

Lad os demonstrere algoritmen trin for trin med et diagram:

Fast element med rekursion

Trin er angivet nedenfor:

Trin 1) I det første lag skal du tage n-r+1 elementer. Det betyder, at vi tog 3 elementer.

Trin 2) Vælg et element fra 2. lag og tag det op til nr. Så hvis vi tager "R", så med R, kan vi tage G, Y og B.

Trin 3) Vælg et element fra det 3. lag og tag det op til det n'te element, og form blokke, der hver indeholder 3 elementer.

Ovenstående tal er returværdien fra rekursionen. Kun det sidste lag udskrives.

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

Output:

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

Gennemførelse 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)

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

RELATEREDE ARTIKLER

Metode 2 (inkluder og ekskluder hvert element)

Denne metode er baseret på Pascals identitet. Tidligere brugte vi rekursion til at beregne nCr. Her er metoden blot opdelt i stedet for en kompleks løkke.

Ifølge Pascals identitet,

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

Så der vil være 2 rekursive logikker for den rekursive algoritme til at finde en kombination af r elementer fra en given matrix af størrelse n.

  1. Element er inkluderet i den aktuelle kombination
  2. Element er udelukket fra den aktuelle kombination

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

Output:

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

Gennemførelse 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)

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

Håndtering af duplikerede kombinationer

Nogle gange kan der være duplikerede elementer i input-arrayet.

For eksempel:

  • Input-arrayet indeholder n = {5, 2, 3, 1, 5}.
  • Her kan vi se, at 5 er til stede i 2 gange.
  • Nu, hvis vi ønsker at køre koden for dette array, vil nogle kombinationer blive gentaget.
  • Vi finder {5, 2, 5}, {5, 2, 3} osv., eller enhver kombination, der indeholder 5, vil blive gentaget.

Vi kan bruge disse to metoder:

  • Sorter input-arrayet. Sortering vil tage O(nlog(n)) tid.
  • Øg derefter værdien af ​​i, mens værdien i og i+1 er den samme. Sæt grundlæggende de følgende to linjer kode i kombinationsfunktionen.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Brug af en ordbog eller uordnet kort til at spore duplikerede kombinationer

Så hvis vi ikke ønsker at sortere elementerne til sporing af duplikatet, kan vi følge de givne trin.

Trin 1) Erklære en global ordbog eller hashmap.
Trin 2) Skub den genererede kombination til hashkortet og øg værdien med én. Kombinationen er nøglen, og deres forekomst er værdier.
Trin 3) når funktionen er færdig med at køre, udskriver vi simpelthen alle nøglerne fra hashmap eller ordbog.

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)

Output: 

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

Her kan du se, at inputtet var "RGYBIB." Generelt bør der forekomme nogle duplikerede kombinationer. Men da vi brugte en ordbog og behandlede hver kombination som nøglen, kan vi kun udskrive den unikke kombination.

Nu, hvis du skriver "print(unique_combination)," kan du se hver kombinations frekvens. Det vil vise sig sådan her:

{'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 er opstået 2 gange. Tidskompleksiteten ved at indsætte nøglen til en ordbog er grundlæggende O(1). Så hvis du bruger en ordbog, vil den samlede tidskompleksitet for at køre koden være:

O(1) + O(n*n)

Svarende til O(n*n).

Ved at bruge den foregående metode til at spore duplikat, skal vi bruge O(n*log(n)) til sortering; for at sammenligne har vi brug for O(n), og selve funktionen tager O(n*n). Den samlede tidskompleksitet vil være:

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