Yhdistelmäalgoritmi: Tulosta kaikki mahdolliset R:n yhdistelmät

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 kolme ja listaa ne kaikki. Esimerkiksi kuvassa valitsimme vain värin "RGBI" ja näytimme neljä 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(n²) 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ä²) + O(nLog(n)). Voimme pitää sitä O(n²), kuten n² 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.

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

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

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 <= 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)

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.

1. Elementti sisältyy nykyiseen yhdistelmään
2. Elementti on suljettu pois nykyisestä yhdistelmästä

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)

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

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 >= 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 track kaksoiskappaletta

Joten jos emme halua lajitella elementtejä trackaksoiskappaleen avulla voimme noudattaa annettuja ohjeita.

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 >= 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ä menetelmää track duplikaattia, lajitteluun tarvitaan O(n*log(n)); vertailuun tarvitaan O(n), ja funktio itsessään saa O(n*n). Kokonaisaikakompleksisuus on:

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

UKK