Kombinatorika elementlarini dasturlash va algoritmlashtirish Reja

O'zgartirishlar
Tanlovlar, ularning har biri n xildan iborat ma'lum bir tartibda joylashgan elementlar deyiladi
Almashtirishlar. Ning tartibini ta'kidlash kerak.
Almashtirishdagi elementlar muhim va barcha n uni hosil qilishda elementlar (m = n)

Ishtirok etadi. N dan olingan barcha turli almashtirishlar soni turli elementlar Pn bilan

Belgilanadi . Kimdan Pn ni hisoblash formulasi matematikaga ma'lum : Pn=n!

Misol: Olti xonali sonlar nechta bo'lishi mumkin raqamlar bo'yicha tuzilgan: 1, 3, 4, 5, 7 va
9, agar ulardan hech biri bo'lmasa bu raqamlar istalgan sonda takrorlanadi.
Yechish: Juft sonning oxirgi raqami kerak teng bo'ling. Shuning uchun, har bir qidiruvning oxirgi
Raqami mumkin faqat 4 bo'lsin, chunki qolgan barcha raqamlar toq. Har biri qolgan beshta raqam
Qolganlarga qo'yilishi mumkin
Har qanday ketma-ketlikda beshta joy. Shuning uchun, soni mumkin bo'lgan almashtirishlar: P5 = 5! = 120.
Ba'zan biz nafaqat topishga qiziqamiz
Mumkin bo'lgan almashtirishlar soni, balki topishda ham
Ularning har biri.

Hammasini yaratish uchun bir nechta algoritmlar mavjud n xil element uchun mumkin bo'lgan almashtirishlar. Ular asosan almashtirish ketma-ketligi bilan farqlanadi

Qabul qilish (Kormen Tomas, Leiserson Charlz, Rivest Ronald, Stein Klifford, 2009).
Biz qaysi algoritmni muhokama qilamiz leksikografik jihatdan tartiblangan almashtirishlarni olish. Bu Ikki almashtirishni solishtirish uchun biz degan ma'noni anglatadi bir xil indeksli elementlarni chapdan o'ngga solishtiring
Va qanchalik katta bo'lsa, unda katta element mavjud birinchi topildi (masalan, S = (3, 5, 4, 6, 7) va L =(3, 5, 6, 4, 7), keyin S < L, chunki S3 < L3).
Biz n = 5 algoritmini ko'rib chiqamiz keyin n ning istalgan mumkin bo'lgan
qiymati uchun kengaytira oladi. Keyin, uchun qulaylik, biz elementlar bilan
ishlamaymizo'zlari, lekin ularning indekslari bilan (1 dan n gacha). Keyin
indekslarni aniqlash, muammo endi emasga muvofiq tegishli elementlarni
chiqarish masalasi bu indekslar (Mandariya, Pertakhia, Shioshvili, 2000).

Keling, algoritmning ishlash printsipini muhokama qilaylik misol yordamida. Aytaylik, siz hamma narsani topishingiz kerak 1, 2, 3, 4, 5 raqamlarini almashtirish. Chunki ular leksikografik jihatdan saralangan bo'lsa, birinchisi:^1, 2, 3, 4, 5 va oxirgisi: 5, 4, 3, 2, 1.

Faraz qilaylik, ishning bir bosqichida algoritm P ni olamiz, bu erda P = (2, 3, 5, 4, 1) =(p1, p2, p3, p4, p5).Haqiqiyni aniqlash uchun keyingi bosqichni almashtirish, quyidagi bosqichlar talab qilinadi:
1-qadam: Keling, o'ngdan o'ngga o'zgartirishni ko'rib chiqaylik massivdagi birinchi
elementni topmagunimizcha chap o'ngdagi elementdan kamroq bo'ling va to'xtating bu elementni topishimiz bilanoq darhol. Bizning almashtirilganda u element 3 < 5 yoki element bo'ladi 1 indeksidagi massivda (Indekslar 0 dan boshlanadi). Biz ushbu elementning indeksini eslab qoladi (2, 3, 5, 4, 1);

2-qadam: Keling, o'ngdan chapga almashtirishni ko'rib chiqaylik yana, biz kattaroq bo'lgan birinchi elementni topgunimizcha Saqlangan indeksimizdagi elementga qaraganda. Bu bo'ladi 3 indeksli massiv elementi bo'lsin. Biz eslaymiz ushbu elementning indeksi (2, 3, 5, 4, 1);