Yhdistelmäalgoritmi: Tulosta kaikki mahdolliset R:n yhdistelmät
Sarah Chen
Mikä on yhdistelmä?
Yhdistelmä on eräänlainen tiettyjen objektien järjestely. Matemaattisesti yhdistelmä on joukko valintoja/kohteiden valintaa ainutlaatuisesta kohteiden/objektien joukosta. Tässä tavaroiden järjestyksellä ei ole väliä. Se tunnetaan myös menetelmänä tapahtuman kokonaistuloksen laskemiseen, jolloin lopputuloksen järjestyksellä ei ole väliä.
Sinulle annetaan esimerkiksi laukku, jossa on 5 eri väriä, ja sinua pyydetään luomaan kuvio, jossa on kolme väriä. Voit myös valita 3 väriä neljästä ja järjestää ne sitten eri järjestyksessä.
Oletetaan, että värit ovat RGYBI(R= punainen, G= vihreä, Y= keltainen, B= sininen, I= indigo). Joten mahdollinen kuvio voi olla RGB, RGY jne.
Katsotaanpa seuraavaa kuvaa:
Selitys:
- Ota mitkä tahansa 4 väriä viidestä ja luettele ne
- Valitse jokaisesta neljän värin lohkosta mitkä tahansa 4 ja luettele ne kaikki. Esimerkiksi valitsimme kuvasta vain "RGBI" ja näytimme 3 yhdistelmää.
- Sen takana on teoria, joka laskee tekemiemme yhdistelmien kokonaismäärän. R-elementin yhdistelmä n:stä voidaan matemaattisesti esittää seuraavasti:
Merkki "!" tarkoittaa kertoma. Esimerkiksi,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Sano, 5! = 5*4*3*2*1 = 120
Joten yllä olevaa ongelmaamme varten meillä on 5 väriä, jotka tarkoittavat n = 5, ja milloin tahansa meidän on valittava mikä tahansa 3. Joten r = 3. Laskemisen jälkeen saamme,
Yllä olevassa skenaariossa on mahdollista yhteensä 10 väriyhdistelmää.
Aikamonimutkaisuusanalyysi yhdistelmälle
Oletetaan nyt, että annettuna n-koon taulukkoon meitä pyydetään ottamaan r elementtiä taulukosta ja suorittamaan r elementin yhdistelmiä.
Jos annetaan taulukko, jonka koko on n, se ottaa O(n2) aikaa suorittaa tehtävä. Lisäksi, jos haluamme poistaa kaksoismerkinnän,
Meidän on suoritettava seuraavat vaiheet:
Vaihe 1) Lajittele syötetaulukon tiedot nousevasti. Lajittelun aika monimutkaisuus on O(n*log(n)).
Vaihe 2) Luo annetuista väliaikaisista taulukoista toinen taulukko, joka sisältää ainutlaatuisen elementin.
Vaihe 3) Suorita sitten yhdistelmätoiminto.
Joten kokonaisajan monimutkaisuudesta tulee = Päällä2) + O(nLog(n)). Voimme pitää sitä O(n2), kuten n2 on paljon suurempi kuin n*log(n).
Menetelmä 1: Kiinteä elementti rekursiolla
Tässä menetelmässä valitsemme elementin ja etsimme sitten r-1-elementtien yhdistelmän. Kun poimimme elementin muusta elementistä, teemme rekursiivisesti, ja siksi sitä kutsutaan kiinteäksi elementiksi ja rekursioksi.
Esitetään algoritmi vaihe vaiheelta kaaviolla:
Vaiheet on annettu alla:
Vaihe 1) Otetaan ensimmäisessä kerroksessa n-r+1 elementtiä. Eli otimme 3 elementtiä.
Vaihe 2) Valitse elementti toisesta kerroksesta ja vie se numeroon nro. Joten jos otamme "R", niin R:n kanssa voimme ottaa G:n, Y:n ja B:n.
Vaihe 3) Valitse elementti 3. tasosta ja vie se n. elementtiin ja muodosta lohkoja, joissa kussakin on 3 elementtiä.
Yllä oleva luku on rekursion palautusarvo. Vain viimeinen kerros tulostetaan.
Pseudokoodi
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
Toteutus 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);
}
lähtö:
Combinations: RGY RGB RGI RYB RYI RBI GYB GYI GBI YBI
Toteutus sisää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)
lähtö:
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
Tapa 2 (sisällytä ja sulje pois jokainen elementti)
Tämä menetelmä perustuu Pascalin identiteettiin. Aikaisemmin käytimme rekursiota nCr:n laskemiseen. Tässä menetelmä on vain jaettu monimutkaisen silmukan sijaan.
Pascalin henkilöllisyyden mukaan
nCr = (n-1)Cr + (n-1)C(r-1)
Rekursiivisella algoritmilla on siis kaksi rekursiivista logiikkaa r elementin yhdistelmän löytämiseksi annetusta taulukosta, jonka koko on n.
- Elementti sisältyy nykyiseen yhdistelmään
- Elementti on suljettu pois nykyisestä yhdistelmästä
Pseudokoodi
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)
Toteutus 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);
}
lähtö:
Combinations: RGY RGB RGI RYB RYI RBI GYB GYI GBI YBI
Toteutus sisää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)
lähtö:
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
Päällekkäisten yhdistelmien käsittely
Joskus syöttötaulukossa voi olla päällekkäisiä elementtejä.
Esimerkiksi
- Syöttötaulukko sisältää n = {5, 2, 3, 1, 5}.
- Tässä voimme nähdä, että 5 on läsnä 2 kertaa.
- Nyt, jos haluamme suorittaa tämän taulukon koodin, jotkin yhdistelmät toistetaan.
- Löydämme, että {5, 2, 5}, {5, 2, 3} jne. tai mikä tahansa yhdistelmä, joka sisältää 5, toistetaan.
Voimme käyttää näitä kahta menetelmää:
- Lajittele syöttötaulukko. Lajittelu vie O(nlog(n)) aikaa.
- Suurenna sitten i:n arvoa, kun taas i-arvo ja i+1-arvo ovat samat. Periaatteessa laita seuraavat kaksi riviä koodia Yhdistelmä-funktioon.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
i++;
}
# for python
while inputArray[i]==inputArray[i+1]:
i+=1
Sanakirjan tai järjestämättömän kartan käyttäminen päällekkäisten yhdistelmien seuraamiseen
Joten jos emme halua lajitella elementtejä kaksoiskappaleen seurantaa varten, voimme noudattaa annettuja vaiheita.
Vaihe 1) Ilmoita globaali sanakirja tai hashmappi.
Vaihe 2) Työnnä luotu yhdistelmä hashmappiin ja lisää arvoa yhdellä. Yhdistelmä on avain, ja niiden esiintyminen on arvoja.
Vaihe 3) kun toiminto on suoritettu loppuun, tulostamme yksinkertaisesti kaikki avaimet hashmapista tai sanakirjasta.
Tässä on toteutus pythonissa
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)
lähtö:
RGY RGB RGI RYB RYI RBI RBB RIB GYB GYI GBI GBB GIB YBI YBB YIB BIB
Tässä näet, että syöte oli "RGYBIB". Yleensä pitäisi esiintyä joitain päällekkäisiä yhdistelmiä. Mutta koska käytimme sanakirjaa ja käsittelimme jokaista yhdistelmää avaimena, voimme tulostaa vain ainutlaatuisen yhdistelmän.
Jos nyt kirjoitat "print(unique_combination)," näet kunkin yhdistelmän taajuuden. Se näkyy näin:
{'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}
Joten voimme nähdä, että RGB, RYB, GYB on esiintynyt 2 kertaa. Avaimen lisäämisen aika monimutkaisuus sanakirjaan on periaatteessa O(1). Joten jos käytät sanakirjaa, koodin suorittamisen kokonaisaika monimutkaisuus on:
O(1) + O(n*n)
Vastaa O(n*n).
Käyttämällä edellistä tapaa jäljittää kaksoiskappaleet, tarvitsemme O(n*log(n)) lajitteluun; vertailua varten tarvitsemme O(n), ja itse funktio ottaa O(n*n). Kokonaisaika monimutkaisuus on:
O(n*log(n)) + O(n) +O(n*n)