Методнинг асосий босқичлари ва объектлари

Комбинаториал тўпламларни яратиш алгоритмлари турли хил дастурий таъминот ва аппарат тизимларини қуриш ва тадқиқ қилишда кенг қўлланилади. Масалан, турли хил синов тизимларида. "Дастур генератори" атамаси жуда умумий талқинга ега, масалан, "ҳисобот генератори", "дастур коди генератори", "тасодифий сонлар генератори". Бу ерда generator амалга оширадиган дастур сифатида тушунилади комбинаториал тўпламни яратиш учун бошқа алгоритм. Комбинаториал тўплам елементлари чекланган тўплам баъзи умумий тузилишга ега. Масалан, пермутациялар, бўлимлар, иккилик дарахтлар, махсус турдаги жадваллар ва бошқалар.
Комбинаторикада генерация алгоритимларини 4 та синфга ажратамиз:
барча тўпламнинг навбатдаги авлоди берилган синфнинг комбинаториал объектлари (listing);
ушбу синфнинг барча комбинаториал объектларини рақамлаш (ranking);
рақамлаш жараёнига мувофиқ комбинаториал объектларни яратиш (unranking);
комбинаториал объектни амалга оширишнинг тасодифий авлоди (random selection).

Кетма-кет авлод алгоритмлари енг кўп ўрганилган. Бироқ, генераторлар асосланган объектларни рақамлаш ва ҳосил қилиш алгоритмлари унинг сони бўйича объект тобора оммалашиб бормоқда.

Авлодни қуриш учун кўплаб усуллар мавжуд рақамлаш алгоритмлари ва уларнинг барчаси аниқ кўриб чиқилаётган комбинаториал объект. Нисбатан яқинда, комбинаториал ҳосил қилиш ва рақамлаш алгоритмларини тузишнинг универсал методи обиекти пайдо бўлди, бир дарахт шаклида бир комбинаторел мажмуи вакиллик асосланган И /ИЛИ.
Бунда асосан таклиф яратиш учун алгоритмларни қуриш ва тадқиқ қилиш комбинаториал тўпламлар, қуриш ва тадқиқи қилиш учун universal дастурий восита комбинаторик тўпламлар елементларининг генераторлари.

Методнинг асосий босқичлари ва объектлари
Ҳосил қилиш алгоритмларини тузиш усули ва комбинаториал объектларни рақамлаш асосида комбинаториал тўпламнинг шаклда ифодаланиши дарахтни қуриш учун рекурсив композиция схемаси И /ИЛИ қуйидагича:
Рекурсив композицияни қуриш учун комбинаториал объектлар тўплами текширилади дарахт И /ИЛИ. Рекурсив композиция қуйидаги схема билан тасвирлаш мумкин
R(0)=D₁,
R(n+1)=S_i(2),_{i(2)…….i(k)}(D, D₁, D₂,……,D_k),
D_j=R(n), j=1,k.


бу ерда D₀ ва D -рухсат етилган дарахтлар, {i_m}^k_m=1 -дарахтнинг барглар тўплами D, улар алмаштирилади дарахт томонидан R(n) – n-қадамда олинган.
Рекурсив композициянинг ишлаши кўрсатилган.
Агар комбинаториал кардиналлик бўлса, бу кўрсатилган тўплам функсия f(n) функсияси сифатида берилган {N, +, x, R, S}, бу ерда R- рекурсия оператори, S-суперпозиция оператори, у ҳолда тўплам рекурсив схемани қуриш мумкин дарахтларнинг таркиби И / ИЛИ.
2,Агар рекурсив композиция олинадиган бўлса, унда комбинаториал тўплам объектларини яратиш алгоритмини тузинг, алгоритм дарахтнинг бир variant яратиш учун ишлатилади И/ИЛИ янада, ўрганилаётган тўплам объектлари олинган дарахт вариантларига мувофиқ қурилади. Дарахтнинг бир варианти И/ИЛИ subtree чиқишни кесиш орқали берилган нарсадан олинади умуман ИЛИ тугунлардан ташқарилар.
Объектни рақамлаш алгоритмлари учун, дарахт варианти қурилади И /ИЛИ ундан кейин дарахт вариантларини рақамлаш алгоритмидан фойдаланиб, биз ўрганилаётган тўпламда объект рақамини оламиз.
Шундай қилиб, генераторларни қуриш жараёни комбинаторик объектларни 3 қисмга ажратиш мумкин:
1. Умумлаштирилган дарахт алгоритмларини амалга ошириш И/ИЛИ (рақамлаш ва вариантларни яратиш).
2. Дарахт И /ИЛИ қуриш алгоритмини амалга ошириш.
3. И/ИЛИ Дарахтнинг объект бўйича вариантини олиш алгоритмларни рақамлаш ва объектнинг ўзи учун вариянт рақамини олинг
Биринчи қисми сифатида амалга оширилиши мумкин C++ да синф шаблонлари кутубхонаси. Бу кутубхонадан ҳар хил турдаги комбинаториал объектлар учун фойдаланишга имкон беради. Иккинчисини ҳал қилиш қисман, дарахтлар ва/ёки билан ишлашга йўналтирилган ихтисослашган тилдан фойдаланиш таклиф етилади. Бу генераторларни амалга ошириш учун зарур бўлган код миқдорини камайтиради ва, шунга кўра, ривожланиш вақтини камайтиринг. Агар вазифанинг дастлабки икки қисми автоматлаштирилиши мумкин, кейин учинчиси объектнинг ўзига хос турига боғлиқ ва бутунлай дастурчининг елкасига тушади.