Kombinationsalgoritm: Skriv ut alla möjliga kombinationer av R

Vad är kombinationen?

Kombinationen är ett slags arrangemang av vissa givna föremål. I matematiska termer är kombination en uppsättning val/val av objekt från en unik uppsättning objekt/objekt. Här spelar ordningen på föremålen ingen roll. Det är också känt som metoden för att beräkna det totala resultatet av en händelse, där ordningen på utfallet inte spelar någon roll.

Du får till exempel en påse med 5 olika färger och ombeds skapa ett mönster med valfria 3 färger. Du kan också välja vilka 3 färger som helst av 4 och sedan ordna dem i olika ordningsföljder.

Låt oss anta att färgerna är RGYBI(R= Röd, G= Grön, Y= Gul, B= Blå, I= Indigo). Så det möjliga mönstret kan vara RGB, RGY, etc.

Låt oss ta en titt på följande figur:

Förklaring:

• Ta valfria 4 färger av 5 och lista dem
• Från varje block med fyra färger, välj tre valfria och lista alla. Till exempel valde vi bara "RGBI" i figuren och visade fyra kombinationer.
• Det finns en teori bakom det för att beräkna det totala antalet kombinationer vi kan göra. En kombination av r element ur n kan matematiskt presenteras som:

Skylten "!" betyder faktoriell. Till exempel,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Säg, 5! = 5*4*3*2*1 = 120

Så för vårt ovanstående problem har vi 5 färger som betyder n = 5, och vid varje given tidpunkt måste vi välja vilka 3 som helst. Så, r = 3. Efter beräkning får vi,

Totalt 10 färgkombinationer är möjliga för scenariot ovan.

Tidskomplexitetsanalysen för Kombination

Nu, låt oss säga, givet en array av storlek n, ombeds vi att ta r element från arrayen och utföra kombinationer av r element.

Om en matris med storlek n ges, kommer den att ta O(n²) tid att utföra uppgiften. Dessutom, om vi vill ta bort dubblettposten, då,

Vi måste utföra följande steg:

Steg 1) Sortera inmatningsdatan på ett stigande sätt. Tidskomplexiteten för sortering är O(n*log(n)).

Steg 2) Skapa en annan array som innehåller ett unikt element från givna temporära arraydata.

Steg 3) Utför sedan kombinationsfunktionen.

Så total tidskomplexitet blir = På²) + O(nLog(n)). Vi kan betrakta det som O(n²), som n² är mycket större än n*log(n).

Metod-1: Fast element med rekursion

I den här metoden väljer vi ett element och hittar sedan en kombination av r-1 element. När vi väljer ett element från resten av elementet, gör vi rekursivt, och det är därför det kallas fast element och rekursion.

Låt oss demonstrera algoritmen steg för steg med ett diagram:

Steg ges nedan:

Steg 1) I det första lagret, ta n-r+1 element. Det betyder att vi tog 3 element.

Steg 2) Välj ett element från det andra lagret och ta upp det till nr. Så om vi tar "R" kan vi med R ta G, Y och B.

Steg 3) Välj ett element från det 3:e lagret och ta det upp till det n:e elementet och bilda block som innehåller 3 element vardera.

Ovanstående figur är returvärdet från rekursionen. Endast det sista lagret kommer att skrivas ut.

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

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

Produktion:

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

Genomförande 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 <= 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)

Produktion:

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

Metod 2 (inkludera och exkludera varje element)

Denna metod bygger på Pascals identitet. Tidigare använde vi rekursion för att beräkna nCr. Här är metoden bara uppdelad istället för en komplex loop.

Enligt Pascals identitet,

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

Så det kommer att finnas två rekursiva logiker för den rekursiva algoritmen för att hitta en kombination av r element från en given matris med storlek n.

1. Element ingår i den aktuella kombinationen
2. Element är exkluderat från den aktuella kombinationen

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)

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

Produktion:

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

Genomförande i 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)

Produktion:

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

Hantera dubbletter av kombinationer

Ibland kan det finnas dubbletter av element i inmatningsmatrisen.

Till exempel,

• Inmatningsmatrisen innehåller n = {5, 2, 3, 1, 5}.
• Här kan vi se att 5 är närvarande 2 gånger.
• Om vi ​​nu vill köra koden för denna array, kommer vissa kombinationer att upprepas.
• Vi kommer att hitta {5, 2, 5}, {5, 2, 3} etc eller så kommer alla kombinationer som innehåller 5 att upprepas.

Vi kan använda dessa två metoder:

• Sortera inmatningsmatrisen. Sortering tar O(nlog(n)) tid.
• Öka sedan värdet på i, medan i-värdet och i+1-värdet är samma. Lägg i princip följande två rader kod i kombinationsfunktionen.

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

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

Använda en ordbok eller oordnad karta för att track duplicerade kombinationer

Så, om vi inte vill sortera elementen efter trackunga duplikatet, kan vi följa de givna stegen.

Steg 1) Deklarera en global ordbok eller hashmap.
Steg 2) Skjut den genererade kombinationen till hashkartan och öka värdet med ett. Kombinationen är nyckeln, och deras förekomst är värden.
Steg 3) När funktionen är klar, skriver vi helt enkelt ut alla nycklar från hashkartan eller ordboken.

Här är 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 >= 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)

Produktion:

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

Här kan du se att ingången var "RGYBIB." I allmänhet bör det förekomma några dubbla kombinationer. Men eftersom vi använde en ordbok och behandlade varje kombination som nyckeln, kan vi bara skriva ut den unika kombinationen.

Nu, om du skriver "print(unique_combination)", kan du se varje kombinations frekvens. Det kommer att visas så här:

{'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 att RGB, RYB, GYB har inträffat 2 gånger. Tidskomplexiteten för att infoga nyckeln till en ordbok är i princip O(1). Så om du använder en ordbok kommer den totala tidskomplexiteten för att köra koden att vara:

O(1) + O(n*n)

Motsvarar O(n*n).

Använda den föregående metoden för att track duplikat, vi behöver O(n*log(n)) för sortering; för jämförelse behöver vi O(n), och själva funktionen tar O(n*n). Den totala tidskomplexiteten blir:

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

Vanliga frågor