-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdp_kombinacije_sa_ponavljanjem.html
122 lines (115 loc) · 3.67 KB
/
dp_kombinacije_sa_ponavljanjem.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<!DOCTYPE html>
<html>
<h1> Kombinacije sa ponavljanjem </h1>
<h2> Definicija: </h2>
Kombinacije \(k\)-te klase od \(n\) elemenata kod kojih se jedan element može do \(k\) puta
ponavljati zovu se kombinacije sa ponavljanjem \(k\)-te klase od \(n\) elemenata. Broj
kombinacija sa ponavljanjem je:
<img src="courses/dp/dp_kombinacije_sa_ponavljanjem/slika1.png" class="img-fluid img-sm">
uz uslov:
<img src="courses/dp/dp_kombinacije_sa_ponavljanjem/slika2.png" class="img-fluid img-sm">
<b> Zadatak: </b> Pretpostavimo da imamo niz dužine \(n\) i želimo da generišemo sve
kombinacije u kojima uzimamo \(r\) elemenata niza, a pritom je dozvoljeno neki element
uzeti više puta, odnosno ponoviti ga. <br>
<div class = "napomena">
U kombinatorici postoje četiri osnovna koncepta:
<br> 1) Kombinacije bez ponavljanja/zamena;
<br> 2) Kombinacije sa ponavljanjima/zamenama;
<br> 3) Permutacije bez ponavljanja/zamena;
<br >4) Permutacije sa ponavljanjima/zamenama.
<br> <br>
Ispod je tabela sažetka koja prikazuje osnovne koncepte u teoriji kombinatorike.
<br>
<table class = "tabela">
<tr>
<th> </th>
<th>Zamene/ponavljanja su dozvoljena</th>
<th>Zamene/ponavljanja nisu dozvoljena </th>
</tr>
<tr>
<th>Pemutacije (redosled bitan)</th>
<td>...</td>
<td>...</td>
</tr>
<tr>
<th>Kombinacije (redosled nije bitan)</th>
<td>Ovaj slučaj trenutno obrađujemo!</td>
<td>...</td>
</tr>
</table>
</div>
<br>
Ovaj članak je o trećem slučaju (redosled nije važan i ponavljanja su dozvoljena).
Ideja je da se ponavlja za sve mogućnosti stringa, čak i ako se karakteri ponavljaju.
Osnovni slučaj rekurzije je kada ima ukupno 'r' znakova i kombinacija je spremna za štampanje.
Radi jasnoće, pogledajte stablo rekurzije za string- “ 1 2 3 4” i r=2.
<br>
U kodu koji sledi prikazana je implementacija.
<xmp class = "primer_ta">
// C++ program koji ispisuje sve kombinacije sa ponavljanjem dužine r od elemenata
// dužine r od elemenata niza dužine n
#include <bits/stdc++.h>
using namespace std;
/* arr[] ---> Ulayni niz
chosen[] ---> Pivremeni niz u kojima speštamo indekse
trenutne kombinacije
start & end ---> Početni i krajnji indeksi niza arr[]
r --->Veličina kombinacije koja treba da se ispiše */
void CombinationRepetitionUtil(int chosen[], int arr[],
int index, int r, int start, int end)
{
// Ukoliko je index postao r, trenutno kombinacije je
// spremna za ispis
if (index == r)
{
for (int i = 0; i < r; i++)
cout << " " << arr[chosen[i]];
cout << "\n";
return;
}
// Biramo sve elemente jedan po jedan (ne uzimajući u obzir
// da li je element već odabran ili ne)
// i to radimo rekurzivno
for (int i = start; i <= end; i++)
{
chosen[index] = i;
CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end);
}
return;
}
// Glavna funkcija koja ispisuje sve kombinacije sa ponavljanjem dužine r
// od niza arr[] sa n elemenata. Ova funkcija
// koristi CombinationRepetitionUtil()
void CombinationRepetition(int arr[], int n, int r)
{
// Allocate memory
int chosen[r+1];
// Pozivamo rekurzivnu funkciju
CombinationRepetitionUtil(chosen, arr, 0, r, 0, n-1);
}
// main funkcija u kojoj pozivamo našu funkciju
int main()
{
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
int r = 2;
CombinationRepetition(arr, n, r);
return 0;
}
</xmp>
<b> Izlaz: </b>
<br> 1 1
<br> 1 2
<br> 1 3
<br> 1 4
<br> 2 2
<br> 2 3
<br> 2 4
<br> 3 3
<br> 3 4
<br> 4 4
<br> <br>
<b> Vremenska složenost: </b> Za niz dužine \(n\) i kombinacije sa ponavljanjem
obima odnosno veličine \(r\) , složenost algoritma iznosi
O(C<sup> \(n+r-1\) </sup> <sub> \(r\) </sub>).
</html>