Kombinatorika algoritmlari. O‘rin almashtirish algoritmini loyihalash

Информация о документе

Цена	12000UZS
Размер	267.2KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Информатика и ИТ

Kombinatorika algoritmlari. O‘rin almashtirish algoritmini loyihalash

Купить

KIRISH
Dastlab algoritm tushunchasi haqida batafsil ma’lumotga ega bo’lib olamiz.
IX asrlarda yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy
nomi bilan uzviy bog’liqligini tushuntirish lozim. Algoritm so’zi al-Xorazmiyning
arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki
al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan
so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi,
uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab
o’tiladi.
Algoritm bu asosiy tushuncha sifatida qabul qilinganligidan, uning faqat
tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani
yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli
hamda to’liq tizimi tushuniladi. Eng qadimiy raqamli algoritmlardan biri Yevklid
algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta
umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis
matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy,
izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini
ko'rsatdi. Kombinatsiya – bu kombinatorikaning asosiy tushunchasidir. Bu
tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan
tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning
o‘rin almashtirishlar, o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy
ko‘rinishlari o‘rganiladi.
2

I Bob. Kambinatorika algoritmlari nazariy asoslari.
1.1.Kombinatorika algoritmlari.
Dastlab kombinatorikaning asosiy amallaridan biri hisoblangan, o’rin
almashtirish nima ekanligni tushunib olishimiz kerak bo’ladi. Uning asosiy
mazmunini quyidagi misol orqali tushunib olishimiz mumkin.
4,7,9 raqamlaridan ularni takrorlamasdan nechta 3 xonali son tuzish
mumkin?
Bu kabi masalalarni maktabning matematika darsliklarida ko’plab
ishlaganmiz.
1-o‘rinda berilgan 3 ta sondan ixtiyoriy bittasi turadi, ya’ni imkoniyatlar soni
3 ta. 2- o‘rinda qolgan 2 ta raqamdan ixtiyoriy bittasi bo‘ladi, ya’ni 2- o‘rinni
egallash imkoniyati 2 ta. Nihoyat, 3- o‘rinda qolgan bitta raqam turadi. Demak, shu
3 ta raqamdan tuzilishi mumkin bo‘lgan 3 xonali sonlar soni 3 • 2 • 1 = 3! = 6 ta
ekan. Shu 6 ta sonni yozaylik:
479, 497, 749, 794, 947, 974.
Hosil bo‘lgan 6 ta sonning tarkibi bir xil — ular berilgan 3 ta raqamdan
tuzilgan, ammo ular bir-biridan raqamlarining tartibi bilan farqlanadi: 1, 2, 3 deb
nomerlangan 3 ta o‘ringa 3 ta raqam turli tartibda joylashtirilgan. Bunday tartiblash
(joylashtirish) o‘rin almashtirish deyiladi.
n ta: 1-, 2-, n- o‘ringa n ta a1, a2, ... , an elementlarni bir o‘ringa bittadan
qilib joylashtirish a1, a2, ... , an elementlardan tuzilgan o‘rin almashtirish deyiladi.
n ta elementdan tuzilgan o‘rin almashtirishlar soni Pn bilan belgilanadi.
Yuqoridagi misolda elementlar soni 3 ta edi, n = 3 va P3= 3 • 2 • 1 = 3! ekanini
ko‘rdik. Umuman, Pn = n • (n-1) ... 2 • 1 = n!
Yana bir misol bilan ko’rib chiqamiz. 4 ta a, b, c, d elementdan
(predmetdan) 2 tadan olib tuzilgan har xil guruhlar soni nechta?
2 elementli guruhlarni tuzamiz: {a, b}; {a, c}; {a, d}; {b, c}; {b, d}; {c, d};
— ularning soni 6 ta. Javob: 6 ta.
Umuman, n ta elementdan k tadan olib tuzilgan barcha guruhlar soni de
b belgilanadi va bu son ga teng: . son n
ta elementdan k tadan olib tuzilgan guruhlar soni deb o‘qiladi. Bizning misolda n =
4, k =2 edi. Demak,

ekanini ko‘rsatish oson. Haqiqatan ham,
.
3

Masalan, .
Shu bilan birga, .
belgining yuqori indeksidagi 2 soni kasrning suratida 2ta ko‘paytuvchi
bo‘lishini bildiradi. Bu ko‘paytuvchilar:
belgining quyi indeksidagi 5 va undan bitta kam bo‘lgan son 4
dir. Kasrning maxrajida esa yuqori indeksidagi son 2 gacha bo‘lgan
natural sonlar ko‘paytmasi yoziladi: 2! = 1 • 2.
Endigi navbatda yuqoridagi jarayonlarni algoritmni ifodalash usullari
yordamida sinab ko’ramiz.
1.2 Kombinatsiya tushunchasi.
Kombinatsiya nima? Kombinatsiya - bu berilgan ob'ektlarning bir turi.
Matematik nuqtai nazardan, Kombinatsiya - bu elementlar/ob'ektlarning noyob
to'plamidan elementlarni tanlash/tanlash. Bu yerda elementlarning tartibi muhim
emas. U hodisaning umumiy natijasini hisoblash usuli sifatida ham tanilgan, bunda
natija tartibi muhim emas.
Masalan, sizga 5 xil rangdagi sumka beriladi va istalgan 3 rangdan naqsh
yaratish so'raladi. Shuningdek, siz 4 ta rangdan istalgan 3 ta rangni tanlashingiz
mumkin, keyin ularni turli tartibda joylashtirishingiz mumkin. Faraz qilaylik,
ranglar RGYBI (R= Qizil, G= Yashil, Y= Sariq, B= Moviy, I= Indigo). Shunday
qilib, mumkin bo'lgan naqsh RGB, RGY va boshqalar bo'lishi mumkin. Keling,
quyidagi rasmni ko'rib chiqaylik:
1-rasm. Kombinatsiyaga misol keltirilgan.
4

Tushuntirish: 5 ta rangdan 4 tasini oling va ularni ro'yxatga kiriting 4 ta
rangning har bir blokidan istalgan 3 ta rangni tanlang va barchasini sanab o'ting.
Misol uchun, biz rasmda faqat "RGBI" ni tanladik va 4 ta kombinatsiyani
ko'rsatdik. Buning ortida biz yaratishimiz mumkin bo'lgan kombinatsiyalar sonini
hisoblash uchun nazariya mavjud. n dan r elementning kombinatsiyasi matematik
jihatdan quyidagicha ifodalanishi mumkin:
formula (1)
Kombinatsiya formulasi
“!” belgisi faktorialni bildiradi . Masalan,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Ayting, 5! = 5*4*3*2*1 = 120
Shunday qilib, yuqoridagi muammomiz uchun bizda n = 5 ma'nosini
anglatuvchi 5 ta rang bor va istalgan vaqtda biz istalgan 3 ni tanlashimiz kerak.
Demak, r = 3. Hisoblab bo'lgach, biz quyidagilarni olamiz:
Yuqoridagi stsenariy uchun jami 10 ta rang kombinatsiyasi mumkin.
1.3 Kombinatsiya uchun vaqt murakkabligi.
Kombinatsiya uchun vaqt murakkabligi tahlili. Endi deylik, n o‘lchamli
massiv berilgan bo‘lsa, bizdan massivdan r elementni olib, r elementning
kombinatsiyasini bajarish so‘raladi. Agar n o‘lchamli massiv berilgan bo‘lsa, u
O(n2) ni oladi ) vaqt kerak bo'ladi. Bundan tashqari, agar biz takroriy yozuvni olib
tashlamoqchi bo'lsak, u holda, Biz quyidagi amallarni bajarishimiz kerak:
1-qadam) Kirish massivi ma'lumotlarini o'sish bo'yicha
tartiblang. Saralashning vaqt murakkabligi O(n*log(n)).
2-qadam) Berilgan vaqtinchalik massiv ma'lumotlaridan noyob elementni
o'z ichiga olgan boshqa massiv yarating.
3-qadam) Keyin kombinatsiya funktsiyasini bajaring.
Shunday qilib, umumiy vaqt murakkabligi = O(n 2
) + O(nLog(n)) ga
aylanadi. Biz uni O(n 2
) deb hisoblashimiz mumkin, chunki n 2
n*log(n) dan ancha
katta.
5

1-usul: rekursiya bilan belgilangan element
Ushbu usulda biz elementni tanlaymiz, keyin r-1 elementlarning
kombinatsiyasini topamiz. Elementning qolgan qismidan elementni tanlayotganda,
biz rekursiv bajaramiz va shuning uchun u sobit element va rekursiya deb ataladi.
Keling, algoritmni bosqichma-bosqich diagramma bilan ko'rsatamiz:
3-rasm.Kombinatsiya hosil qilishning qadamlar ketma-ketligi
Qadamlar quyida keltirilgan:
1-qadam) Birinchi qatlamda n-r+1 elementlarni oling. Ya'ni, biz 3 ta
elementni oldik.
2- qadam) 2 -qavatdan elementni tanlang va uni nrgacha olib
boring. Shunday qilib, agar biz "R" ni olsak, u holda R bilan G, Y va B ni
olishimiz mumkin.
3-qadam) -qavatdan elementni tanlang va uni n-elementga olib boring va
har biri 3 ta elementdan iborat bloklarni hosil qiling.
Yuqoridagi rasm rekursiyadan qaytarilgan qiymatdir. Faqat oxirgi qatlam
chop etiladi.
7

$II Bob. O’rin almashtirish algoritmi. 2.1. O’rin almashtirish algoritmini realizatsiya qilish. Endigi navbatda yuqoridagi algoritmni realizatsiya qilamiz: Psevdo kod: 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 C/C++ dasturlash tili yordamida algoritmni realizatsiya qilamiz (Ilova 1 qarang): 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); } } Dastur natijasida sifatida quyidagilarni olishimiz mumkin bo’ladi. Combinations: RGY RGB RGI RYB 8$

RYI
RBI
GYB
GYI
GBI
YBI
Python dasturlash tili yordamida algoritmni quyidagicha realizatsiya qilish
mumkin bo’ladi:
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)
2-usul (har bir elementni qo'shish va chiqarib tashlash):
Bu usul Paskalning identifikatsiyasiga asoslangan. Ilgari biz nCr ni
hisoblash uchun rekursiyadan foydalanganmiz. Bu yerda usul faqat murakkab
pastadir o'rniga bo'linadi.
Paskalning shaxsiga ko'ra,
nCr = (n-1)Cr + (n-1)C(r-1)
Shunday qilib, rekursiv algoritm uchun n o'lchamdagi berilgan massivdan r
elementlarning kombinatsiyasini topish uchun 2 ta rekursiv mantiq bo'ladi.
Element joriy Kombinatsiyaga kiritilgan
Element joriy Kombinatsiyadan chiqarib tashlangan
Endigi navbatda C/C++ dasturlash tilida yuqoridagi 2-usulni realizatsiya
qilib ko’ramiz:
#include<bits/stdc++.h>
9

#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r,
int index, int i) {}
(Dastur kodi Iliva 1da).
Dastur natijasi:
4-rasm.Dastur natijasi.
2.2. Ikki nusxadagi kombinatsiyalar tushunchasi.
Ikki nusxadagi kombinatsiyalar bilan ishlash. Ba'zan kirish massivida
takroriy elementlar bo'lishi mumkin.
Masalan, Kirish massivida n = {5, 2, 3, 1, 5} mavjud. Bu yerda biz 5 ning 2
marta mavjudligini ko'rishimiz mumkin. Endi, agar biz ushbu massiv uchun kodni
ishga tushirmoqchi bo'lsak, ba'zi kombinatsiyalar takrorlanadi. Biz {5, 2, 5}, {5, 2,
3} va hokazolarni topamiz yoki 5 ni o'z ichiga olgan har qanday kombinatsiya
takrorlanadi. Biz ushbu ikkita usuldan foydalanishimiz mumkin: Kirish massivini
tartiblang. Saralash O(nlog(n)) vaqt oladi. Keyin i qiymatini oshiring, i qiymati va
i+1 qiymati bir xil. Kombinatsiya funksiyasiga asosan quyidagi ikkita kod qatorini
qo'ying. Takroriy kombinatsiyalarni kuzatish uchun lug'at yoki tartibsiz xaritadan
foydalanish Shunday qilib, agar biz dublikatni kuzatish uchun elementlarni
saralashni istamasak, biz berilgan qadamlarni bajarishimiz mumkin.
1-qadam. Global lug'at yoki xashmapni e'lon qiling.
2-qadam, Yaratilgan kombinatsiyani xashmapga suring va qiymatni bittaga
oshiring. Kombinatsiya kalit bo'lib, ularning paydo bo'lishi qiymatdir.
3-qadam) funktsiya ishga tushirilgandan so'ng, biz hashmap yoki lug'atdagi
barcha kalitlarni chop etamiz.
10

Python dasturlash tilida:
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)
Bu yerda siz kiritish "RGYBIB" ekanligini ko'rishingiz mumkin. Odatda, bir
nechta takroriy kombinatsiyalar bo'lishi kerak. Ammo biz lug'atdan
foydalanganimiz va har bir Kombinatsiyani kalit sifatida ko'rib chiqqanimiz
sababli, biz faqat noyob Kombinatsiyani chop etishimiz mumkin. Endi, agar siz "
print (unique_combination) " deb yozsangiz, har bir kombinatsiyaning chastotasini
ko'rishingiz mumkin. Bu shunday ko'rsatiladi:
5-rasm. Kombinatsiyaning chastotasi.
Dastur natijasi.
Shunday qilib, biz RGB, RYB, GYB 2 marta sodir bo'lganligini ko'rishimiz
mumkin. Lug'atga kalitni kiritishning vaqt murakkabligi asosan O (1) dir. Shunday
qilib, agar siz lug'atdan foydalansangiz, kodni ishlatish uchun umumiy vaqt
murakkabligi quyidagicha bo'ladi:
O(1) + O(n*n) O(n*n) ga ekvivalent.
Dublikatni kuzatish uchun oldingi usuldan foydalanib, tartiblash uchun bizga
O(n*log(n)) kerak; solishtirish uchun bizga O(n) kerak va funksiyaning o ziʻ
O(n*n) ni oladi. Umumiy vaqt murakkabligi:
11

O(n*log(n)) + O(n) +O(n*n)
Kombinatorikaning o’rin almashtirish amalini to’liqroq tushunib yetish
uchun yana bir misol yordamida ko’rib chiqamiz:
n o‘lchamli massiv berilgan bo‘lsa, massivdagi r elementning barcha
mumkin bo‘lgan kombinatsiyalarini yarating va chop eting. Masalan, agar kirish
massivi {1, 2, 3, 4} va r 2 bo lsa, chiqish {1, 2}, {1, 3}, {1, 4}, {2, 3}, { bo lishiʻ ʻ
kerak. 2, 4} va {3, 4}. Quyida buni amalga oshirishning ikkita usuli mavjud.
1-usul (Elementlarni tuzatish va takrorlash)
Biz barcha chiqishlarni birma-bir saqlaydigan vaqtinchalik "ma'lumotlar[]"
massivini yaratamiz. G'oya ma'lumotlardagi [] birinchi indeksdan (indeks = 0)
boshlash, ushbu indeksdagi elementlarni birma-bir tuzatish va qolgan indekslar
uchun takrorlash. Kiritilgan massiv {1, 2, 3, 4, 5} va r 3 bo lsin. Biz avval
ʻ
ma lumotlarda[] 0 indeksida 1 ni tuzatamiz, keyin qolgan indekslar uchun
ʼ
takrorlaymiz, keyin 0 indeksida 2 ni tuzamiz va takrorlaymiz. Nihoyat, biz 3 ni
tuzatamiz va qolgan indekslar uchun takrorlaymiz. Ma lumotlardagi[] elementlar
ʼ
soni r (kombinatsiya o lchami) ga teng bo lganda, biz ma lumotlarni [] chop
ʻ ʻ ʼ
qilamiz.
Quyidagi diagrammada bir xil kirish uchun rekursiya daraxti ko'rsatilgan.
6-rasm. Quyida yuqoridagi yondashuvni amalga oshirish ko'rsatilgan.
#include<bits/stdc++.h>
using namespace std;
void combinationUtil(int arr[], int data[],
int start, int end,
int index, int r);
void printCombination(int arr[], int n, int r)
{
int data[r];
12

combinationUtil(arr, data, 0, n-1, 0, r);
}
void combinationUtil(int arr[], int data[],
int start, int end,
int index, int r)
{
if (index == r)
{
for (int j = 0; j < r; j++)
cout << data[j] << " ";
cout << endl;
return;
}
for (int i = start; i <= end &&
end - i + 1 >= r - index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1,
end, index+1, r);
}
}
// asosiy qism
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
}
O(r). Joriy kombinatsiyani saqlash uchun r
o'lchamdagi vaqtinchalik massiv ma'lumotlaridan
foydalanamiz.
Dublikatlarni qanday boshqarish kerak?
E'tibor bering, yuqoridagi usul dublikatlarni ishlatmaydi. Masalan, agar
kirish massivi {1, 2, 1} va r 2 bo'lsa, u holda dastur {1, 2} va {2, 1} ni ikki xil
13

kombinatsiya sifatida chop etadi. Yuqoridagi kodga quyidagi ikkita qo'shimcha
narsani qo'shish orqali takrorlanishdan qochishimiz mumkin.
1) printCombination() da combinationUtil() ni chaqirishdan oldin massivni
saralash uchun kod qo‘shing
2) KombinasyonUtil() da for tsiklining oxiriga quyidagi qatorlarni qo‘shing.
2-usul (Har bir elementni qo'shish va istisno qilish)
Yuqoridagi usul kabi biz vaqtinchalik ma'lumotlar massivini yaratamiz[]. Bu
erdagi g'oya Subset Sum muammosiga o'xshaydi . Biz kirish massivining har bir
elementini birma-bir ko'rib chiqamiz va ikkita holatda takrorlaymiz:
1) element joriy kombinatsiyaga kiritilgan (biz elementni data[] ga qo'yamiz
va ma'lumotlardagi keyingi mavjud indeksni oshiramiz[])
2) element joriy kombinatsiyada chiqarib tashlangan (Biz elementni
qo'ymaymiz va indeksni o'zgartirmaymiz)
Ma'lumotlardagi[] elementlar soni r ga teng bo'lganda (kombinatsiya
o'lchami), biz uni chop qilamiz.
Bu usul asosan Paskalning identifikatoriga asoslanadi , ya'ni n cr= n-1 cr +
n-1 cr-1
Quyida 2-usulning amalga oshirilishi keltirilgan.
#include <bits/stdc++.h>
using namespace std;
void combinationUtil(int arr[], int n, int r,
int index, int data[], int i);
(Dastur kodi ilova 2da).
// dastur yakuni
Vaqt murakkabligi: O(n^r)
Yordamchi fazo: O(r)
2.3. Dublikat tushunchasi.
2-usulda dublikatlarni qanday ishlatish kerak?
1-usul singari, biz dublikatlarni qayta ishlash uchun ikkita narsaga amal
qilishimiz mumkin.
1) printCombination() da combinationUtil() ni chaqirishdan oldin massivni
tartiblash uchun kod qo‘shing
2) KombinasyonUtil() da combinationUtil() ning ikkita rekursiv chaqiruvlari
orasiga quyidagi qatorlarni qo‘shing
Avval massivning birinchi elementini oching va uni istalgan o'zgaruvchiga
saqlang. Massivning qolgan qismining birikmalarini ikki marta (birinchi r - 1 va
ikkinchi marta r bilan) rekursiv tarzda toping va uni saqlang. Nima uchun
kombinatsiyani ikki marta yaratishimiz kerak, keyinroq tushuntiriladi.
Keyin r - 1 yordamida yaratgan barcha kombinatsiyalarning old qismidagi
birinchi elementni suring.
14

Ishingiz tugadi! Ammo rekursiyani buzish uchun asosiy mezonlarni amalga
oshirishni unutmang.
Bu juda oddiy. Hali ham chalkashmisiz? Xavotir olmang! Keling, chuqurroq
ko'rib chiqaylik.
Faraz qilaylik, bizda [ 1, 2, 3, 4 ] massiv bor. Ushbu massivdan biz 3 ta
element birikmasini yaratishimiz kerak (r = 3). Bizda " kombinatsiya " deb
nomlangan kombinatsiya funksiyamiz mavjud. Algoritmga ko'ra, siz massivning
birinchi elementini chiqarasiz va uni o'zgaruvchida saqlaysiz. Bizda shunday
qilish,
bosh = 1, massiv = [ 2, 3, 4 ]
Keyin kombinatsiya funksiyamizni r - 1 bilan rekursiv deb ataymiz. Bizning
holatimizda r 3 ga teng, shuning uchun 2 bo'ladi.
natija = kombinatsiya (massiv, 2)
Natija shunday bo'lishi kerak,
natija = [ [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
Ajoyib! Endi bizning keyingi qadamimiz birinchi elementni surishdir. Biz
ochilgan birinchi elementimizni head o'zgaruvchisiga saqladik. Biz uni yaratilgan
kombinatsiyalar oldida qo'shamiz. Qo'shilgandan so'ng natija bo'ladi,
natija = [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4
] ]
Endi bu barcha kombinatsiyalarni yaratishi kerak. Yaxshi, turing! Bizning
massiv uzunligi 4 va r 3. Unda 4C3 4 to'g'rimi? Keyin bizda 3 ta element o'rniga 4
ta element bo'lishi kerak. Boshqasi qayerda? Bu erda ikkinchi marta kombinatsiya
avlodi keladi. Agar kombinatsiya funksiyasini r = 3 bilan qayta rekursiv chaqirsak,
yo'qolgan elementni topishimiz mumkin.
natijalar_again = kombinatsiya (arr, 3)
Buning natijasi bo'lishi kerak,
natijalar_again = [ [ 2, 3, 4 ] ]
Shubhasiz, agar massiv uzunligi r ga teng bo'lsa, natijada bir xil
massivni qaytaradi. Ammo natijani umumlashtirsak, biz shunday
bo'lamiz:
yakuniy_natija = natija + natija_yana
Qaysi natijalar,
yakuniy_natija = [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3,
4 ], [ 2, 3, 4 ] ]
Biz barcha mumkin bo'lgan kombinatsiyalarni oldik. Agar siz haligacha
chalkashib ketgan bo'lsangiz, tarkibni yana bir bor o'qib chiqing va eng muhimi, bu
rekursion yondashuv ekanligini va uning asosiy mezonlari yoki rekursiyani
tugatish nuqtasi borligini yodda tuting.
Amalga oshirish
15

$Bu erda men JavaScript-da kombinatsiya funktsiyasini amalga oshirmoqchiman. Siz uni C++, Java yoki Python kabi boshqa dasturlash tillarida amalga oshirishga harakat qilishingiz mumkin. function Combinations( arr, r ) { arr = arr && arr.slice() || []; var len = arr.length; if( !len || r > len || !r ) // Base criteria 1. return [ [] ]; else if( r === len ) // Base criteria 2. return [ arr ]; if( r === 1 ) return arr.reduce( ( x, v ) => { x.push( [ v ] ); return x; }, [] ); var head = arr.shift(); // Popping the first element. return Combinations( arr, r - 1 ).map( x => { x.unshift( head ); return x; } ).concat( Combinations( arr, r ) ); // The missing combinations. } console.log( Combinations( [ 1, 2, 3, 4, 5 ], 3 ) ); Binom daraxtlari - kombinatsiyalangan avlodda ishlatiladigan daraxtlar oilasi. Ular T_n for bilan belgilanadi n \geq 0, shunday qilib: Agar n=0 bo'lsa, daraxt T_0bitta tugundan iborat Agar n>0, tartibli binomial daraxt n ildiz va n binomial pastki daraxtlarni o'z ichiga oladiT_{n-1},...,T_1,T_0. 7-rasm. Binom daraxtlari. Masalan, T_4ildiz va pastki daraxtlarni o'z ichiga oladi T_{3}, T_2, T_1, T_0: 16$ $8-rasm.Daraxt. Yuqoridagilarning boshqa nusxasini kiritish orqali T_nuni iterativ tarzda qurish mumkinligini ko'rish oson . Shunday qilib, tugunlarni o'z ichiga oladi . Bundan tashqari, har bir darajadagi tugunlar soni in {0,…, -1} ga teng . Shu ma'noda, Leksikografik avlod algoritmining o'zgarishlari on level ning tugunlarini kesib o'tadi .T_{n-1}T_{n-1}T_n2^nk\binom{n}{k}T_nknT_nk. 17$

XULOSA:
Men quyidagi kurs ishi davomida xulosa qilib quyidagilarni aytishim
mumkinki. Kombinatsiya – bu kombinatorikaning asosiy tushunchasidir. Bu
tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan
tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning
o‘rin almashtirishlar, o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy
ko‘rinishlari o‘rganiladi. Kombinatorika amallarini real hayotda qo’llay olish biz
uchun juda muhimdir. Men bu kurs ishi davomida o’rin almashtirish amalini turli
xil usullar yordamida algoritmni realizatsiya qilish va algoritmlar tuzishga harakat
qildim. Demak o’rin almashtirish o’zi nima degan savolga quyidagicha javob
bersam maqsadga muvofiq bo’lar ekan. Aslida «o'rin almashtirish» iborasi to'plam
elementlarining o'rinlarini o'zgartirish harakatini anglatsa-da, bu yerda uni shu
harakat natijasidagi hosil bo'lgan tuzilma sifatida qo'llaymiz. Bu iboradan uning asl
ma'nosida ham foydalanamiz. O'rin almashtirishni ifodalashda uning elementlarini
ajratuvchi belgi sifatida yuqorida «<,>> (ver gul) belgisidan foydalanildi. Ammo
bu muhim emas, bu yerda boshqa belgidan ham foydalanish, hattoki, yozuvning
ixchamligi maqsadida, elementlar orasidagi ajratuvchi belgilarni tushirib qoldirish
ham mumkin. Bu eslatma bundan keyin bayon etiladigan boshqa kombinatorik
tuzilmalar uchun ham o'rinlidir. Unchasiga asoslanib, bu yerda qaralayong To'plam
tushunchasiga a qaralayotgan o'rin almashtirishlar tarkibida elementlaming
takrorlanmasligini eslatib o'tamiz. Shu sababli bunday o'rin almashtirishlarni
betakror (takrorli emas) o'rin almashtirishlar, deb ham atash mumkin.
Qisqacha qilib aytganda bu kurs ishi davomida kompinatorika amallari
uchun algoritm yozish va ularni realizatsiya qilish ustida ishlandi.
18

ADABIYOTLAR RO’YXATI.
1. X.To’rayev Matematik mantiq va diskeret matematika Toshkent
o’qituvchi 2003 yil .
2. Yu.Abdiraxmonova Diskeret matematika o’quv qo’llanma Toshkent
2014.
3. V.Y.Gumarman Ehtimollar nazariyasi va matematik statiska .
4.Yo.Soatov Oliy matematika kursi 2-qism Toshkent o’qituvchi 1994-yil.
5. http://refleader.ru/jgeqasmerpolaty.html
6. https :// intuit . ru / studies / courses /1146/238/ lecture /6153
7. https :// www . sanfoundry . com / cpp - program - generate - combinations /
8. https :// medium . com / codex / generating - combinations - efficiently - with -
asifs - algorithm - d 453 e 803893
19

$ILOVALAR 1-ILOVA. 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); } 2-ILOVA // Hammasini chop etadigan asosiy funksiya // arrdagi r o'lchamdagi kombinatsiyalar[] // o'lchamdagi n. Bu funktsiya asosan // combineUtil() dan foydalanadi void printCombination(int arr[], int n, int r) { // Saqlash uchun vaqtinchalik massiv // barcha kombinatsiyalar birma-bir int data[r]; // Barcha kombinatsiyani chop etish // vaqtinchalik massiv data[]' combinationUtil(arr, n, r, 0, data, 0); } /* arr[] ---> Kirish massivi n ---> Kirish massivining o'lchami r ---> Chop etiladigan kombinatsiya hajmi indeks ---> Ma'lumotlardagi joriy indeks[] 20$

data[] ---> Joriy kombinatsiyani saqlash uchun vaqtinchalik massiv
i ---> arr[] dagi joriy element indeksi */
void combinationUtil(int arr[], int n, int r,
int index, int data[], int i)
{
if (index == r)
{
for (int j = 0; j < r; j++)
cout << data[j] << " ";
cout << endl;
return;
}
if (i >= n)
return;
data[index] = arr[i];
combinationUtil(arr, n, r, index + 1, data, i + 1);
combinationUtil(arr, n, r, index, data, i+1);
}
// asosiy funksiya
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
return 0;
}
21

Kombinatorika algoritmlari. O‘rin almashtirish algoritmini loyihalash

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Kombinatorika algoritmlari. O‘rin almashtirish algoritmini loyihalash

Похожие документы