Kombinációs algoritmus: Nyomtassa ki az R összes lehetséges kombinációját

By: Sarah Chen Sarah Chen
Hours korszerűsített

Mi az a kombináció?

A kombináció bizonyos objektumok egyfajta elrendezése. Matematikai értelemben a kombináció választások/elemek készlete egyedi tételek/objektumok halmazából. Itt a tételek sorrendje nem számít. Más néven módszer egy esemény teljes kimenetelének kiszámítására, ahol az eredmény sorrendje nem számít.

Például kapsz egy táskát 5 különböző színnel, és megkérnek, hogy generálj egy mintát bármelyik 3 színből. Kiválaszthat 3 színt a 4 közül, majd különböző sorrendbe rendezheti őket.

Tegyük fel, hogy a színek RGYBI (R= piros, G= zöld, Y= sárga, B= kék, I= indigó). Tehát a lehetséges minta lehet RGB, RGY stb.

Nézzük a következő ábrát:

Színkombináció
Színkombináció

Magyarázat:

  • Válassz ki 4 színt az 5-ből, és sorold fel őket
  • Minden 4 színből álló blokkból válassz 3-at, és sorold fel az összeset. Például az ábrán csak az „RGBI”-t választottuk, és 4 kombinációt mutattunk be.
  • Van mögötte egy elmélet, amely kiszámolja az általunk alkotható kombinációk számát. Az n-ből r elem kombinációja matematikailag a következőképpen ábrázolható:
Kombinációs képlet

Kombinációs képlet

A jel „!” azt jelenti faktoriális. Például,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Mondjuk 5! = 5*4*3*2*1 = 120

Tehát a fenti feladatunkhoz 5 színünk van, amelyek jelentése n = 5, és bármikor bármelyik 3-at ki kell választanunk. Tehát r = 3. Kiszámítás után azt kapjuk, hogy

Kombináció

Összesen 10 színkombináció lehetséges a fenti forgatókönyv szerint.

A kombináció időbeli összetettségének elemzése

Most, tegyük fel, hogy adott egy n méretű tömb, arra kérünk, hogy vegyünk ki r elemet a tömbből, és hajtsunk végre r elem kombinációit.

Ha adott egy n méretű tömb, akkor az O(n2) ideje a feladat elvégzésére. Továbbá, ha el akarjuk távolítani az ismétlődő bejegyzést, akkor

A következő lépéseket kell végrehajtanunk:

Step 1) Rendezze a bemeneti tömb adatait növekvő sorrendben. A válogatás időbeli összetettsége az O(n*log(n)).

Step 2) Hozzon létre egy másik, egyedi elemet tartalmazó tömböt a megadott ideiglenes tömbadatokból.

Step 3) Ezután hajtsa végre a kombinációs funkciót.

Tehát a teljes időbonyolultság = lesz Tovább2) + O(nLog(n)). Tekinthetjük O(n2), mint az n2 sokkal nagyobb, mint n*log(n).

1. módszer: Rögzített elem rekurzióval

Ebben a módszerben kiválasztunk egy elemet, majd megtaláljuk az r-1 elemek kombinációját. Miközben az elem többi részéből választunk ki egy elemet, rekurzívan csináljuk, ezért nevezzük fix elemnek és rekurziónak.

Lépésről lépésre mutassuk be az algoritmust egy diagrammal:

Javított elem rekurzióval

A lépések az alábbiak:

Step 1) Az első rétegben vegyünk n-r+1 elemet. Ez azt jelenti, hogy 3 elemet vettünk.

Step 2) Válasszon ki egy elemet a 2. rétegből, és vigye fel a nr. Tehát, ha „R”-t vesszük, akkor R-vel vehetjük G-t, Y-t és B-t.

Step 3) Válasszon ki egy elemet a 3. rétegből, és vigye fel az n-edik elemre, és alkosson egyenként 3 elemet tartalmazó blokkokat.

A fenti ábra a rekurzióból származó visszatérési érték. Csak az utolsó réteg kerül kinyomtatásra.

Álkó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

Megvalósítás 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

Végrehajtás 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

KAPCSOLÓDÓ CIKKEK

2. módszer (minden elem felvétele és kizárása)

Ez a módszer Pascal azonosságán alapul. Korábban rekurziót használtunk az nCr kiszámításához. Itt a metódus csak fel van osztva összetett ciklus helyett.

Pascal személye szerint

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

Tehát 2 rekurzív logika lesz a rekurzív algoritmus számára, hogy megtalálja az r elem kombinációját egy adott n méretű tömbből.

  1. Az elem benne van a jelenlegi kombinációban
  2. Az elem ki van zárva a jelenlegi kombinációból

Álkó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)

Megvalósítás 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

Végrehajtás 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

Ismétlődő kombinációk kezelése

Néha előfordulhatnak ismétlődő elemek a bemeneti tömbben.

Például,

  • A bemeneti tömb n = {5, 2, 3, 1, 5} értéket tartalmaz.
  • Itt láthatjuk, hogy 5 2 alkalommal van jelen.
  • Most, ha le akarjuk futtatni ennek a tömbnek a kódját, néhány kombináció megismétlődik.
  • Meg fogjuk találni, hogy az {5, 2, 5}, {5, 2, 3} stb. vagy bármilyen kombináció, amely 5-öt tartalmaz, megismétlődik.

Ezt a két módszert használhatjuk:

  • Rendezze a bemeneti tömböt. A rendezés O(nlog(n)) időt vesz igénybe.
  • Ezután növeljük az i értékét, miközben az i érték és az i+1 érték megegyezik. Alapvetően tegye a következő két kódsort a Combination függvénybe.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Szótár vagy rendezetlen térkép használata az ismétlődő kombinációk nyomon követésére

Ha tehát nem szeretnénk a duplikáció nyomon követéséhez szükséges elemeket rendezni, akkor a megadott lépéseket követhetjük.

Step 1) Globális szótár vagy hashmap deklarálása.
Step 2) Tolja a generált kombinációt a hashmaphoz, és növelje az értéket eggyel. A kombináció a kulcs, előfordulásuk pedig értékek.
Step 3) Amikor a funkció fut, egyszerűen kinyomtatjuk az összes kulcsot a hashmapból vagy a szótárból.

Íme a megvalósítás pythonban

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

Itt láthatja, hogy a bemenet az „RGYBIB” volt. Általában előfordulhat néhány ismétlődő kombináció. De mivel szótárt használtunk, és minden kombinációt kulcsként kezeltünk, csak az egyedi kombinációt tudjuk kinyomtatni.

Most, ha beírja a „print(unique_combination)” kifejezést, láthatja az egyes kombinációk gyakoriságát. Így fog megjelenni:

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

Tehát láthatjuk, hogy RGB, RYB, GYB 2 alkalommal fordult elő. A kulcs szótárba való beillesztésének időbeli bonyolultsága alapvetően O(1). Tehát, ha szótárt használ, akkor a kód futtatásának teljes időtartama a következő lesz:

O(1) + O(n*n)

O(n*n) egyenértékű.

Az előző módszerrel a duplikáció nyomon követésére O(n*log(n)) szükséges a rendezéshez; az összehasonlításhoz O(n) kell, maga a függvény pedig O(n*n). A teljes idő bonyolultsága a következő lesz:

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