Kombinační algoritmus: Vytiskněte všechny možné kombinace R

Od: Sarah Chen Sarah Chen
Hours aktualizováno

Co je to Kombinace?

Kombinace je druh uspořádání některých daných objektů. Z matematického hlediska je Kombinace množinou možností/výběru položek z jedinečné množiny položek/objektů. Zde na pořadí položek nezáleží. Je také známá jako metoda výpočtu celkového výsledku události, kde na pořadí výsledku nezáleží.

Například dostanete tašku s 5 různými barvami a požádáte o vytvoření vzoru s libovolnými 3 barvami. Můžete si také vybrat libovolné 3 barvy ze 4 a pak je uspořádat v různém pořadí.

Předpokládejme, že barvy jsou RGYBI (R= červená, G= zelená, Y= žlutá, B= modrá, I= indigová). Takže možný vzor může být RGB, RGY atd.

Podívejme se na následující obrázek:

Barevná kombinace
Barevná kombinace

Vysvětlení:

  • Vezměte libovolné 4 barvy z 5 a uveďte je
  • Z každého bloku 4 barev vyberte libovolné 3 a uveďte je všechny. Například jsme na obrázku vybrali pouze „RGBI“ a ukázali jsme 4 kombinace.
  • Je za tím teorie, jak vypočítat celkový počet kombinací, které můžeme udělat. Kombinace r prvků z n může být matematicky prezentována jako:
Kombinační vzorec

Kombinační vzorec

Znamení "!" znamená faktoriální, Například,
N! = N* (N-1) * (N-2) * … * 3 * 2 * 1
Řekni, 5! = 5*4*3*2*1 = 120

Takže pro náš výše uvedený problém máme 5 barev, což znamená n = 5, a v každém daném okamžiku musíme vybrat libovolné 3. Takže r = 3. Po výpočtu dostaneme,

Kombinace

Pro výše uvedený scénář je možných celkem 10 barevných kombinací.

Analýza časové složitosti pro kombinaci

Nyní řekněme, že máme-li pole o velikosti n, jsme požádáni, abychom z pole vzali r prvků a provedli kombinace r prvků.

Pokud je zadáno pole o velikosti n, bude trvat O(n2) čas na provedení úkolu. Také, pokud chceme odstranit duplicitní záznam, pak

Musíme provést následující kroky:

Krok 1) Seřaďte data vstupního pole vzestupně. Časová složitost řazení je O(n*log(n)).

Krok 2) Vytvořte další pole obsahující jedinečný prvek z daných dat dočasného pole.

Krok 3) Poté proveďte kombinační funkci.

Celková časová složitost se tedy stává = Na2) + O(nLog(n)). Můžeme to považovat za O(n2), jako n2 je mnohem větší než n*log(n).

Metoda 1: Pevný prvek s rekurzí

V této metodě vybereme prvek a pak najdeme kombinaci prvků r-1. Když vybíráme prvek ze zbytku prvku, děláme to rekurzivně, a proto se tomu říká fixní prvek a rekurze.

Ukažme si algoritmus krok za krokem pomocí diagramu:

Pevný prvek s rekurzí

Kroky jsou uvedeny níže:

Krok 1) V první vrstvě vezměte n-r+1 prvků. To znamená, že jsme vzali 3 prvky.

Krok 2) Vyberte prvek z 2. vrstvy a vezměte jej až k č. Takže když vezmeme „R“, pak s R můžeme vzít G, Y a B.

Krok 3) Vyberte prvek ze 3. vrstvy a přeneste jej k n-tému prvku a vytvořte bloky obsahující každý 3 prvky.

Výše uvedený obrázek je návratová hodnota z rekurze. Vytiskne se pouze poslední vrstva.

Pseudo kód

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

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

Výstup:

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

provádění 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)

Výstup:

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

SOUVISEJÍCÍ ČLÁNKY

Metoda 2 (zahrnout a vyloučit každý prvek)

Tato metoda je založena na Pascalově identitě. Dříve jsme pro výpočet nCr používali rekurzi. Zde je metoda pouze rozdělena namísto složité smyčky.

Podle Pascalovy identity

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

Takže pro rekurzivní algoritmus budou existovat 2 rekurzivní logiky k nalezení kombinace r prvků z daného pole o velikosti n.

  1. Prvek je součástí aktuální kombinace
  2. Prvek je vyloučen z aktuální kombinace

Pseudo kód

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)

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

Výstup:

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

provádění 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)

Výstup:

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

Zpracování duplicitních kombinací

Někdy mohou být ve vstupním poli duplicitní prvky.

Například,

  • Vstupní pole obsahuje n = {5, 2, 3, 1, 5}.
  • Zde vidíme, že 5 je přítomno 2krát.
  • Nyní, pokud chceme spustit kód pro toto pole, některé kombinace se budou opakovat.
  • Zjistíme, že {5, 2, 5}, {5, 2, 3} atd. nebo jakákoli kombinace obsahující 5 se bude opakovat.

Můžeme použít tyto dvě metody:

  • Seřadit vstupní pole. Třídění bude trvat O(nlog(n)) čas.
  • Potom zvyšte hodnotu i, zatímco hodnota i a i+1 je stejná. V podstatě vložte následující dva řádky kódu do funkce Kombinace.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Použití slovníku nebo neuspořádané mapy ke sledování duplicitních kombinací

Pokud tedy nechceme třídit prvky pro sledování duplikátu, můžeme postupovat podle uvedených kroků.

Krok 1) Deklarujte globální slovník nebo hashmap.
Krok 2) Posuňte vygenerovanou kombinaci do hashmapy a zvyšte hodnotu o jednu. Kombinace je klíč a jejich výskyt jsou hodnoty.
Krok 3) až funkce skončí, jednoduše vytiskneme všechny klíče z hashmapy nebo slovníku.

Zde je implementace v pythonu

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)

Výstup: 

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

Zde můžete vidět, že vstup byl „RGYBIB“. Obecně by se měly vyskytovat některé duplicitní kombinace. Ale protože jsme použili slovník a považovali jsme každou kombinaci za klíč, můžeme vytisknout pouze jedinečnou kombinaci.

Nyní, když napíšete „print(unique_combination)“, uvidíte frekvenci každé kombinace. Ukáže se to takto:

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

Můžeme tedy vidět, že RGB, RYB, GYB se vyskytly 2krát. Časová náročnost vložení klíče do slovníku je v zásadě O(1). Pokud tedy používáte slovník, celková časová složitost pro spuštění kódu bude:

O(1) + O(n*n)

Ekvivalent O(n*n).

Při použití předchozí metody ke sledování duplikátů potřebujeme O(n*log(n)) pro třídění; pro porovnání potřebujeme O(n) a samotná funkce má O(n*n). Celková časová náročnost bude:

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

Máš rád: