Генерисање комбинаторних објеката или набрајање је скуп алгоритама којима се могу креирати сви објекти који имају неку задату комбинаторну структуру. Сви алгоритми овог типа се могу поделити у две категорије:
У оквиру ове теме позабавићемо се генерисањем варијација, комбинација и пермутација скупова, као и генерисањем комбинаторних објеката са унапред задатом структуром. У већини задатака прво ћемо објаснити итеративни алгоритам којим се добија наредни комбинаторни објекат, а затим и рекурзивни поступак којим се могу генерисати сви комбинаторни објекти са задатим својствима.
Алгоритми су једноставни, али се често разликују само у детаљима, па је потребно учити их са разумевањем.
Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.
Корисник уноси природне бројеве и . Написати програм који одређује све варијације дужине скупа .
Улаз: У првој линији стандардног улаза налази се природан број (), а у другој је природан број .
Излаз: На стандардни излаз исписати све варијације дужине скупа , сваку у свом реду.
Задатак можемо да урадимо на два начина:
Прво ћемо развити алгоритам који се заснива на одређивању лексикографски следеће варијације. Следећа варијација у лексикографском поретку се може генерисати на следећи начин:
Позиција на којој се број увећава назива се преломна тачка (енгл. turning point). На пример, ако набрајамо варијације скупа дужине наредна варијација за варијацију је , јер је преломна тачка на позицији , што је последња позиција у низу. Ако сада посматрамо варијацију , њена наредна варијација ће бити , јер је преломна тачка позиција на којој се налазио елемент . Низ нема преломну тачку, па самим тим ни лексикографски следећу варијацију.
Један начин имплементације је да преломну тачку нађемо линеарном претрагом од краја низа, ако преломна тачка постоји да увећамо елемент и да од следеће позиције до краја низ попунимо јединицама. Међутим, те две фазе можемо објединити. Варијацију обилазимо од краја постављајући на сваки елемент у варијацији који је једнак броју . Ако се зауставимо пре него што смо стигли до почетка низа, значи да смо пронашли елемент који се може увећати и увећавамо га. У супротном, варијација има све елементе једнаке и максимална је у лексикографском редоследу. Да бисмо генерисали све варијације, потребно је само да овај поступак понављам све док можемо.
static bool sledeca_varijacija(int n, int[] varijacija)
{
int i;
int k = varijacija.Length;
// тражимо преломну тачку, тј. елемент који можемо увећати
for (i = k - 1; i >= 0 && varijacija[i] == n; i==)
varijacija[i] = 1;
// ако такав елемент не постији, стигли смо до лексикографски последње
// варијације
if (i < 0)
return false;
// ако преломна тачка постоји, увећавамо елемент
varijacija[i]++;
return true;
}
static void sve_varijacije(int n, int k)
{
// креирамо прву варијацију
int[] varijacija = new int[k];
for (int i = 0; i < k; i++)
varijacija[i] = 1;
// у петљи
do {
// штампамо текућу варијацију
for (int i = 0; i < k; i++)
Console.Write("{0} ", varijacija[i]);
Console.WriteLine();
// све док постоји следећа варијација
} while (sledeca_varijacija(n, varijacija);)
}Варијације се могу набројати и индуктивно-рекурзивном конструкцијом. Једина варијација дужине нула је празна. Све варијације дужине се могу добити тако што се на прво место упише било који од бројева од до , а затим се преостала места допуне свим варијацијама дужине . Имплементацију ћемо организовати тако да уместо да враћа колекцију варијација, рекурзивна функција прима делимично попуњен низ који ће на све могуће начине допуњавати варијацијама текуће дужине (која ће се смањивати кроз рекурзивне позиве). Дакле, на текућу позицију у низу постављамо једну по једну вредност од до и затим рекурзивно позивамо функцију да попуни остатак низа (тако што увећавамо бројач и тиме прелазимо на наредну позицију).
static void sve_varijacije(int[] varijacija, int n, int i)
{
// ако смо попунили читаву варијацију
if (i == varijacija.Length)
{
// штампамо је
for (int j = 0; j < k; j++)
Console.Write("{0} ", varijacija[j]);
Console.WriteLine();
}
// ако нисмо попунили читаву варијацију
else
{
// пролазимо кроз све елементе скупа
for (int j = 1; j <= n; j++)
{
// и упусујемо их један по један на текућу позицију
varijacija[i] = j;
// рекурзивно попуњавамо суфикс варијације
sve_varijacije(varijacija, n, i + 1);
}
}
}
static void sve_varijacije(int n, int k)
{
// креирамо низ у којем ћемо чувати варијације
int[] varijacija = new int[k];
// рекурзивно креирамо све варијације лексикографски
sve_varijacije(varijacija, n, 0);
}Варијације је могуће попуњавати и уназад, тј. на последње место постављати један по један број од до , а затим рекурзивно попуњавати префикс, но тиме би редослед варијација био другачији од траженог, тј. не би био лексикографски.
Корисник уноси природан број и затим природних бројева. Написати програм који одређује све подскупове датог скупа.
Улаз: У првој линији стандардног улаза налази се природан број , затим се у следећих линија уносе елементи скупа.
Излаз: На стандардном излазу исписати све подскупове датог скупа, сваки у свом реду.
Генерисање свих подскупова можемо да извршимо свођењем на већ познати проблем. Наиме, подскуп скупа од елемената можемо да кодирамо са варијацијом скупа дужине . Да бисмо добили све подскупове, потребно је да генеришемо све варијације. Применићемо познати алгоритам за генерисање свих варијација са понављањем дужине :
static void svi_podskupovi(int[] skup, int[] varijacija, int i)
{
// ако смо попунили читаву варијацију
if (i == varijacija.Length)
{
// штампамо подскуп
for (int j = 0; j < varijacija.Length; j++)
{
if (varijacija[j] == 1)
Console.Write("{0} ", skup[j]);
}
Console.WriteLine();
}
// ако нисмо попунили читаву варијацију
else
{
// прво на текуће место уписујемо нулу, тј. искључујемо елемент из подскупа
varijacija[i] = 0;
// рекурзивно попуњавамо суфикс варијације
svi_podskupovi(varijacija, n, i + 1);
// затим на текуће место уписујемо јединицу, тј. укључујемо елемент у подскуп
varijacija[i] = 1;
// рекурзивно попуњавамо суфикс варијације
svi_podskupovi(varijacija, n, i + 1);
}
}
static void svi_podskupovi(int[] skup)
{
// креирамо низ у којем ћемо чувати варијације
int[] varijacija = new int[skup.Length];
// рекурзивно креирамо све варијације лексикографски
svi_podskupovi(skup, varijacije, 0);
}Задатак можемо да решимо и без експлицитног генерисања варијација, тј. можемо директно да конструишемо подскупове. Проблем који је очигледан јесте то што су подскупови променљиве дужине. На овом месту, можемо да се послужимо једноставним триком. Уместо да користимо динамичку структуру података за представљање подскупа који ћемо током генерисања проширивати додавањем нових елемената и скраћивати брисањем старих елемената, много је економичније да користимо низ. Трик се огледа у томе да ћемо унапред да алоцирамо довољно простора у низу за цео скуп, тј. највећи подскуп, и уместо да му непрестано додајемо и одузимамо елементе, увешћемо додатни бројач у којем ћемо чувати текућу величину подскупа.
Конструкција алгоритма је врло једноставна и прати принцип који ћемо наивно звати укључи-искључи. Нека је дат скуп са елемената. Да бисмо генерисали све подскупове можемо да применимо следећу индуктивно-рекурзивну конструкцију која се ослања на принцип смањи за један:
Одавде лако можемо да закључимо како да имплементирамо описани поступак. Дефинисаћемо рекурзивну функцију која на сваком наредном нивоу рекурзије обрађује наредни елемент полазног скупа који је представљен низом. У првом случају га не додајемо у резултујући подскуп и прелазимо на наредни ниво рекурзије, а у другом га додајемо на крај тренутног резултујућег подскупа и прелазимо на наредни ниво рекурзије. Да бисмо постигли описано, потребно је и да резултујући подскуп представимо низом и да рекурзивној функцији као додатне параметре прослеђујемо тренутну дужину подскупа и индекс елемента скупа који се тренутно разматра. Када се цео полазни низ исцрпи, односно када је бројач елемената скупа, тј. дубина рекурзије, једнака дужини полазног низа, тада се тренутно акумулирани подскуп исписује.
Описани поступак је имплементиран у наставку:
// параметар i представља индекс елемента скупа који се разматра
// параметар j представља индекс првог слободног места у подскупу, тј. дужину подскупа
static void svi_podskupovi(int[] skup, int i, int[] podskup, int j)
{
// ако смо потрошили све елементе скупа, завршили смо генерисање подскупа
if (i == skup.Length)
{
// штампамо подскуп
for (int k = 0; k < ј; k++)
{
Console.Write("{0} ", podskup[k]);
}
Console.WriteLine();
}
// ако нисмо потрошили све елементе скупа
else
{
// разматрамо подскуп без текућег елемента - "искључи"
svi_podskupovi(skup, i+1, podskup, j);
// додајемо елемент у подскуп
podskup[j] = skup[i];
// разматрамо подскуп са текућим елементом - "укључи"
svi_svi_podskupovi(skup, i + 1, podskup, j + 1);
}
}
static void svi_podskupovi(int[] skup)
{
// креирамо низ који представља подскуп
int[] podskup = new int[skup.Length];
// рекурзивно креирамо све подскупове
svi_podskupovi(skup, 0, podskup, 0);
}Приметимо да се у оба приказана решења нисмо посебно бавили међусобним уређењем комбинаторних објеката, тј. подскупова. Описани поступак ће генерисати подскупове, али не у лексикографском поретку. Да бисмо подскупове генерисали у лексикографском поретку потребно је прво да осмислимо поступак којим ћемо од постојећег подскупа добити лексикографски наредни. Све подскупове генерисаћемо лексикографски сукцесивном применом поступка који следи.
Нека је дат скуп , тада ће лексикографски поредак свих подскупова бити:
Да бисмо лакше уочили правило, преписаћемо подскупове груписане на основу броја елемената:
Из овог записа се лако види да постоје два начина да се дође до наредног подскупа:
С обзиром да у овом алгоритму додајемо на крај и бришемо само са краја, не морамо да користимо низове и бројимо елементе, већ је згодније да користимо динамичку структуру података List<>. Додавање на крај и брисање са краја листе су константне операције. Описани итеративни поступак је у наставку:
static bool sledeci_podskup(List<int> podskup, int n)
{
// ако је подскуп празан, додајемо јединицу и прекидамо поступак
if (podskup.Count == 0)
{
podskup.Add(1);
return true;
}
// ако последњи елемент није највећи, онда проширујемо
if (podskup[podskup.Count - 1] < n)
{
// у подскуп додајемо елемент за један већи од последњег
podskup.Add(podskup[podskup.Count - 1] + 1);
// прекидамо поступак
return true;
}
// у супротном, скраћујемо подскуп
podskup.RemoveAt(podskup.Count - 1);
// ако након скраћивања остане празан скуп, онда смо
// генерисали све подскупове
if (podskup.Count == 0)
return false;
// ако подскуп није празан, увећавамо последњи елемент
podskup[podskup.Count - 1]++;
return true;
}Лексикографски све подскупове ћемо лако добити сукцесивном применом претходне функције. Имплементација је у наставку:
static void svi_podskupovi(int n)
{
// на старту, подскуп је празан
List<int> podskup = new List<int>();
// у петљи
do {
// штампамо текући подскуп
for (int i = 0; i < podskup.Count; i++)
Console.Write("{0} ", podskup[i]);
Console.WriteLine();
// и прелазимо на следећи подскуп
} while(sledeci_podskup(podskup, n);)
}Написати програм којим се приказују декадни записи свих природних бројева који у бинарном систему имају највише бинарних цифара и немају две узастопне нуле.
Улаз: Прва линија стандардног улаза садржи природан број ().
Излаз: На стандардном излазу приказати тражене бројеве у растућем поретку, сваки број у посебној линији.
Задатак од нас захтева да креирамо све бинарне бројеве са највише цифара који немају две узастопне нуле. Проблем ћемо да упростимо и описаћемо метод којим можемо да креирамо све бинарне бројеве са тачно цифара који немају две нуле. Јасно је да ћемо полазни проблем решити тако што ћемо позвати описани метод за све вредности .
Прво креирамо све једноцифрене бинарне бројеве који задовољавају услов, па затим двоцифрене, па троцифрене итд. Одавде можемо да закључимо да наши бројеви могу почињати само цифром 1, тј. водеће нуле нећемо разматрати, јер бисмо тиме добили дупликате у генерисаном низу.
Слично претходним алгоритмима и овде ћемо направити помоћни низ који ће представљати бинарни запис броја. У тај низ ћемо додавати једну по једну цифру, све док цео низ не попунимо. Приликом додавања цифара имамо два случаја:
Након додавања цифре у низ, рекурзивно ћемо обрадити суфикс низа. Алгоритам ћемо комплетирати увођењем бројача позиција. Крећемо од позиције и описани поступак додавања цифара спроводимо све док не дођемо до позиције која је једнака дужини помоћног низа. Тада треба да прикажемо креирамо број, али у основи . У томе ће нам помоћи Хорнерова шема. Имплементација је у наставку:
static int bin_to_dec(int[] bin_zapis)
{
// стандардна хорнерова шема, којом пребацујемо број у декадни
int v = 0;
for (int i = 0; i < bin_zapis.Length; i++)
v = v*2 + bin_zapis[i];
return v;
}
static void generisi_sve_brojeve(int[] bin_zapis, int i)
{
// ако смо генерисали цео комбинаторни објекат
if (i == bin_zapis.Length)
{
// приказујемо га у декадном облику
Console.WriteLine(bin_to_dec(bin_zapis));
}
// ако нисмо завршили са креирањем објекта
else
{
// нулу постављамо само ако претходна цифра није 0
if ((i > 0 && bin_zapis[i-1] != 0))
{
bin_zapis[i] = 0;
// рекурзивно попуњавамо суфикс
generisi_sve_brojeve(bin_zapis, i + 1);
}
// јединицу можемо увек да поставимо
bin_zapis[i] = 1;
// рекурзивно попуњавамо суфикс
generisi_sve_brojeve(bin_zapis, i + 1);
}
}
static void generisi_sve_brojeve(int n)
{
// у петљи генеришемо све бринарне бројеве
// са задатим бројем цифара
for (int i = 1; i <= n; i++)
{
// помоћни низ у којем чувамо бинарни запис броја
int[] bin_zapis = new int[i];
// помоћна функција која генерише бројеве са траженим особинама
generisi_sve_brojeve(bin_zapis, 0);
}
}Неочигледан детаљ је израчунавање декадне вредности на основу бинарног записа броја. Декадну вредност можемо лако да израчунамо применом Хорнерове шеме. Треба само обратити пажњу да је цифра највише тежине на првом месту, па Хорнерову шему морамо да применимо од првог ка последњем месту, а не уобичајено како смо навикли са полиномима чији се коефицијенти најчешће представљају у супротном редоследу од онога који ми овде имамо.
Корисник уноси природне бројеве и . Написати програм који одређује све комбинације без понављања дужине скупа .
Улаз: У првој линији стандардног улаза налази се природан број (), а у другој је природан број .
Излаз: На стандардном излазу исписати све комбинације без понављања дужине скупа у лексикографском поретку сваку у свом реду.
Уобичајени поступак који смо до сада примењивали је био да поступак раздвојимо на две методе. Једну којом ћемо од постојећег комбинаторног објекта да генеришемо лексикографски следећи и другу којом ћемо рекурзивним поступком да генеришемо све комбинаторне објекте са траженим својством.
Размотримо скуп , тј. и комбинације дужине три, тј. . Размотрићемо неколико примера:
Одавде треба да уочимо да смо увек прво тражили онај елемент комбинације који можемо да увећамо, тј. тражили смо преломну тачку. Да бисмо одредили да ли се елемент може увећати или не, треба да имамо на уму да су елементи у комбинацији лексикографски сортирани и да нема дупликата. Ако позиције у комбинацији обележимо бројевима до , тада на последњем месту у комбинацији може бити највише вредност , на претпоследњем итд. Дакле, преломна тачка ће бити онај елемент комбинације који је мањи од максимума који се на тој позицији може наћи. Максималну дозвољену вредност на позицији можемо одредити помоћу израза . Јасно је да ако преломна тачка не постоји, да не постоји ни наредна комбинација. Након што одредимо преломну тачку, увећевамо елемент на тој позицији за и све елементе иза те позиције постављамо на најмање могуће вредности чиме добијамо лексикографски следећу комбинацију. С обзиром да комбинација мора бити сортирана строго растуће, након увећања преломне вредности све елементе иза ње постављамо на вредност која је за један већа од њој претходне вредности у низу.
Имплементација алгоритма који одређује лексикографски следећу комбинацију је у наставку:
static bool sledeca_kombinacija(int n, int[] kombinacija)
{
// одређујемо дужину комбинације
int k = kombinacija.Length;
// тражимо преломну тачку
int i;
for (i = k - 1; i >= 0 && kombinacija[i] == n; i--, n--)
;
// ако преломна тачка не постоји, прекидамо извршавање
if (i < 0)
return false;
// увећавамо преломну тачку
kombinacija[i]++;
// ажурирамо вредности иза преломне тачке
for (i++; i < k; i++)
kombinacija[i] = kombinacija[i-1] + 1;
return true;
}Описани поступак можемо да искористмо за креирање свих комбинација дужине у лексикографском поретку. Довољно је да кренемо од прве комбинације и да у петљи редом генеришемо следећу комбинацију све док следећа постоји. Имплементација је у наставку:
static void sve_kombinacije(int n, int k)
{
// креирамо прву комбинацију
int[] kombinacija = new int[k];
for (int i = 0; i < k; i++)
kombinacija[i] = i + 1;
// у петљи
do {
// штампамо текућу комбинацију
for (int i = 0; i < k; i++)
Console.Write("{0} ", kombinacija[i]);
Console.WriteLine();
// креирамо следећу све док можемо
} while (sledeca_kombinacija(n, kombinacija));
}Све комбинације можемо креирати и рекурзивним поступком. Једно могуће решење прати до сада уведени оквир. Направићемо помоћни низ у којем ћемо чувати комбинацију. Низ попуњавамо један по један елемент и рекурзивно примењујемо исти поступак на суфикс низа. У сваком тренутку потребно је да знамо која је текућа позиција коју разматрамо и колика је величина скупа. Описани поступак се назива рекурзија по позицијама
static void sve_kombinacije(int[] kombinacija, int i, int n)
{
// ако смо креирали целу комбинацију
if (i == kombinacija.Length)
{
// приказујемо је
for (int k = 0; k < i; k++)
Console.Write("{0} ", kombinacija[k]);
Console.WriteLine();
}
// ако нисмо
else
{
// прво дефинишемо опсег допустивих вредности за текућу позицију
int min = i == 0 ? 1 : kombinacija[i-1] + 1;
int max = n - k + 1 + i;
// у петљи пролазимо кроз све вредности
for (int j = min; j <= max; j++)
{
// уписујемо вредност на текући позицију
kombinacija[i] = x;
// рекурзивно попуњавамо суфикс
sve_kombinacije(kombinacija, i + 1, n);
}
}
}
static void sve_kombinacije(int n, int k)
{
// креирамо помоћни низ који представља комбинацију
int[] kombinacija = new int[k];
// рекурзивно креирамо све комбинације
sve_kombinacije(kombinacija, 0, n);
}Све комбинације лексикографски можемо креирати и мало другачијим поступком. Уместо да се фокусирамо на позиције, можемо да се фокусирамо на дозвољене вредности на позицијама. У пракси, желимо да избацимо петљу у else грани претходно приказаног рекурзивног алгоритма.
Током рекурзије можемо да чувамо информацију о томе који је распон елемената којима се проширује низ. Знамо да су то елементи скупа , међутим, пошто су комбинације сортиране растуће скуп кандидата је ужи. У претходном програму смо најмању вредност за позицију одређивали на основу вредности са позиције , међутим, алтернативно можемо и експлицитно да одржавамо променљиве и које одређују скуп чији се елементи распоређују у комбинацији на позицијама из интервала . Ако је тај интервал празан, комбинација је попуњена и може се приказати. У супротном, ако је , тада не постоји вредност коју је могуће ставити на позицију , па можемо изаћи из рекурзије, јер се тренутна комбинација не може попунити до краја. У супротном можемо размотрити две могућности. Прво на позицију можемо поставити елемент и рекурзивно извршити попуњавање низа од позиције , а друга могућност je да тај елемент прескочимо и у рекурзивном позиву поново захтевамо да се попуни позиција . У оба случаја се скуп елемената сужава на .
Претрагу можемо сасећи и мало раније. Наиме, пошто су понављања забрањена када је број елемената тог скупа , тј. мањи од броја преосталих позиција које треба попунити, тј. , већ тада можемо сасећи претрагу, јер не постоји могућност да се комбинација успешно допуни до краја.
static void sve_kombinacije(int[] kombinacija, int i, int min, int max)
{
// ако смо креирали целу комбинацију
if (i == kombinacija.Length)
{
// приказујемо је
for (int k = 0; k < i; k++)
Console.Write("{0} ", kombinacija[k]);
Console.WriteLine();
}
// ако нисмо
else
{
// проверавамо да ли постоји нека дозвољена вредност
if (max - min + 1 < k - i)
return;
// уписујемо минималну вредност у нашу комбинацију
kombinacija[i] = min;
// укључујемо минимални елемент у комбинацију и рекурзивно обрађујемо суфикс
sve_kombinacije(kombinacija, i+1, min+1, max);
// искључујемо минимални елемент из комбинације и рекурзивно обрађујемо суфикс
sve_kombinacije(kombinacija, i, n_min+1, max);
}
}
static void sve_kombinacije(int n, int k)
{
// креирамо помоћни низ који представља комбинацију
int[] kombinacija = new int[k];
// рекурзивно креирамо све комбинације
sve_kombinacije(kombinacija, 0, 1, n);
}Описани поступак се назива рекурзија по вредностима и припада класи укључи-искључи алгоритама које смо раније увели. Такође, ово је први алгоритам у којем смо користили одсецање, да бисмо из разматрања избацили оне гране које не могу да доведу до комплетне комбинације.
Корисник уноси природне бројеве и . Написати програм који одређује све комбинације са понављањем дужине скупа .
Улаз: У првој линији стандардног улаза налази се природан број (), а у другој је природан број .
Излаз: На стандардном излазу исписати све комбинације са понављањем дужине скупа сваку у свом реду.
Лексикографско генерисање свих кобинација са понављањем је минимална модификација претходно приказаног алгоритма за генерисање свих комбинација рекурзијом по вредности. Уместо да генеришемо растуће низове комбинација, треба да генеришемо неопадајуће низове. Прецизније, приликом укључивања елемента у скуп, у следећем рекурзивном позиву треба да допустимо да се тај исти елемент поново укључи у комбинацију.
static void sve_kombinacije_sa_ponavljanjem(int[] kombinacija, int i, int min, int max)
{
// ако смо креирали целу комбинацију
if (i == kombinacija.Length)
{
// приказујемо је
for (int k = 0; k < i; k++)
Console.Write("{0} ", kombinacija[k]);
Console.WriteLine();
}
// ако нисмо
else
{
// проверавамо да ли постоји нека дозвољена вредност
if (min > max)
return;
// уписујемо минималну вредност у нашу комбинацију
kombinacija[i] = min;
// укључујемо минимални елемент у комбинацију и рекурзивно обрађујемо суфикс
// при чему, остављамо могућност да се елемент понови јер не увећавамо трећи аргумент позива
sve_kombinacije_sa_ponavljanjem(kombinacija, i+1, min, max);
// искључујемо минимални елемент из комбинације и рекурзивно обрађујемо суфикс
sve_kombinacije_sa_ponavljanjem(kombinacija, i, n_min+1, max);
}
}
static void sve_kombinacije_sa_ponavljanjem(int n, int k)
{
// креирамо помоћни низ који представља комбинацију
int[] kombinacija = new int[k];
// рекурзивно креирамо све комбинације
sve_kombinacije_sa_ponavljanjem(kombinacija, 0, 1, n);
}Пажљиво погледајте услов у линији 15 и рекурзивни позив у линији 21. То су кључне измене у односу на претходно уведени алгоритам, које омогућавају креирање комбинација са понављањем.
Итеративне верзије решења и решење рекурзијом по позицијама се препуштају читаоцу за вежбу.
Корисник уноси природан број . Написати програм који одређује све пермурације скупа .
Улаз: У првој линији стандардног улаза налази се природан број .
Излаз: На стандардном излазу исписати све пермутације скупа сваку у свом реду.
Као и до сада размотрићемо два приступа решавању задатка. Први приступ је итеративни и заснован је на могућности одређивања лексикографски следеће пермутације, а други поступак је рекурзивни који ће креирати све пермутације датог скупа, али нажалост не лексикографски.
Размотримо пермутацију . Заменом елемента и би се добила пермутација која је лексикографски мања од полазне и то нам не одговара. Слично би се десило и да се замене елементи и . Чињеница да је подниз строго опадајући нам говори да није могуће ни на који начин разменити та три елемента да се добије лексикографски већа пермутација, тј. да је ово највећа пермутација која почиње са . Дакле, наредна пермутација ће бити лексикографски најмања пермутација која почиње са , а то је .
Дакле, у првом кораку алгоритма проналазимо прву позицију сдесна, такву да је (за све важи да је ). Ово радимо најобичнијом линеарном претрагом. У нашем примеру . Ако таква позиција не постоји, наша пермутација је скроз опадајућа и самим тим лексикографски највећа. Након тога, проналазимо прву позицију сдесна такву да је , опет линеарном претрагом и размењујемо елементе на позицијама и . У нашем примеру и након размене добијамо пермутацију . Пошто је овом разменом реп иза позиције и даље стрogo опадајући, да бисмо добили жељену лексикографски најмању пермутацију која почиње са , потребно је обрнути редослед елемената репа што можемо учинити познатим алгоритмом заснованим на техници два показивача.
Имплементација описаног поступка је у наставку:
static void razmeni(int[] niz, int i, int j)
{
int tmp = niz[i];
niz[i] = niz[j];
niz[j] = tmp;
}
static bool sledeca_permutacija(int[] permutacija)
{
int n = permutacija.Length;
// одређујемо преломну тачку, тј. прво индекс i са десне стране
// такав да важи a[i] < a[i-1]
int i = n - 2;
while (i >= 0 && permutacija[i] > permutacija[i+1])
i--;
// ако преломна тачка не постоји, не постоји ни наредна пермутација
if (i < 0)
return;
// проналазимо први индекс j са десне стране такав
// је a[j] > a[i]
int j = n-1;
while (permutacija[j] < permutacija[i])
j--;
// размењујемо елементе на позицијама i и j
razmeni(niz, i, j);
// обрћемо суфикс низа почевши од позције (i-1)
for (j = n - 1, i++; i < j; i++, j--)
razmeni(niz, i, j);
return true;
}Описани поступак можемо да искористимо да на једноставан начин генеришемо све пермутације лексикографски. Кренућемо од лексикографски прве пермутације и понављаћемо поступак све док постоји следећа пермутација. Имплементација је у наставку:
static void sve_permutacije(int n)
{
// креирамо прву пермутацију
int[] permutacija = new int[n];
for (int i = 0 ; i < n; i++)
permutacija[i] = i + 1;
// у петљи
do {
// штампамо текућу пермутацију
for (int i = 0; i < n; i++)
Console.Write("{0} ", permutacija[i]);
Console.WriteLine();
// све док постоји наредна пермутација
} while (sledeca_permutacija(permutacija));
}Све пермутације скупа можемо генерисати и рекурзивним поступком. У том случају, не можемо их генерисати у лексикографском поретку. Алгоритам можемо конструисати на следећи начин:
static void razmeni(int[] niz, int i, int j)
{
int tmp = niz[i];
niz[i] = niz[j];
niz[j] = tmp;
}
static void sve_permutacije(int[] permutacija, int i)
{
// ако је остао једноелементни скуп, креирали смо пермутацију
if (i == 1)
{
// штампамо текућу пермутацију
for (int j = 0; j < permutacija.Length; j++)
Console.Write("{0} ", permutacija[j]);
Console.WriteLine();
}
// ако нисмо
else
{
// пролазимо кроз све елементе префикса
for (int j = 0; j < i; j++)
{
// доводимо елемент из префикса на крај пермутације
razmeni(permutacija, j, i - 1);
// генеришемо све пермутације префикса
sve_permutacije(permutacija, i - 1);
// рестауирарамо почетно стање
razmeni(permutacija, j, i - 1);
}
}
}
static void sve_permutacija(int n) {
int[] permutacija = new int[n];
for (int i = 0; i < n; i++)
permutacija[i] = i + 1;
sve_permutacije(permutacija, n);
}На крају, морамо још једном да нагласимо да ће описани рекурзивни поступак генерисати све пермутације датог скупа, али не лексикографски. Рекурзивно генерисање свих пермутација у лексикографском поретку је алгоритам којим се нећемо бавити.
Варијација класе без понављања елемената скупа je сваки уређена -торка од различитих елемената скупа . Написати програм који за дато и приказује све варијације без понављања класе скупа бројева , у лексикографском поретку.
Улаз: Прва линија стандардног улаза садржи природан број (), у другој линији налази се природан број ().
Излаз: На стандрадном излазу приказати у лексикографском поретку све варијације без понављања класе бројева од до (сваку у посебном реду).
Један начин да се задатак реши је да се дефинише функција која за дату варијацију проналази следећу варијацију у лексикографском поретку. Алгоритам представља модификацију алгоритма за генерисање следеће варијације са понављањем. Полазимо од краја варијације тражећи позицију на којој се налази неки елемент који се може увећати. Да би увећавање елемента било могуће, мора постојати неки елемент који је строго већи од , а мањи или једнак , који се не јавља пре позиције , јер дупликати нису дозвољени. Ако таква позиција не постоји, тада је варијација лексикографски највећа. У супротном увећавамо елемент на позицији на најмању могућу вредност, а елементе иза њега попуњавамо редом што мањим елементима скупа , који се нису појављивали у дотадашњем делу низа. Да бисмо ефикасније одређивали елементе који су већ употребљени у првом делу варијације, посебно ћемо одржавати скуп тих елемената, што можемо извести помоћу низа логичких вредности тако да вредност на месту говори да ли је елемент већ употребљен. Имплементација описаног алгоритма је у наставку:
// помоћна функција која открива први већи неупотребљен елемент
// скупа, ако такав постоји
static int veci_neupotrebljen(int n, int x, bool[] upotrebljen)
{
// у петљи пролазимо само кроз веће елементе
for (int i = x + 1; i <= n; i++)
{
// ако постоји неупотребљен, враћамо његову вредност
if (!upotrebljen[i])
return i;
}
// ако не постоји, враћамо -1
return -1;
}
static bool sledeca_varijacija_bez_ponavljanja(int n, int[] varijacija, bool[] upotrebljen)
{
// памтимо величину варијације
int k = varijacija.Length;
int i = 0, novi = 0;
// са десне стране тражимо прву позицију на којој можемо да увећамо
// елемент
for (i = k - 1; i >= 0; i--)
{
// проверавамо у скупу индикатора да ли постоји већи број од текућег
novi = veci_neupotrebljen(n, varijacija[i], upotrebljen);
// све док не постоји, ресетујемо већ употребљене
if (novi == -1)
upotrebljen[varijacija[i]] = false;
else
break;
}
// ако нисмо нашли позицију на којој се може увећати елемент,
// прекидамо извршавање
if (i < 0)
return false;
// ако смо нашли, ресетујемо индикатор старе вредности
upotrebljen[varijacija[i]] = false;
// постављамо индикатор нове вредности
upotrebljen[novi] = true;
// и додајемо је у варијацију
varijacija[i++] = novi;
// суфикс низа редом попуњавамо неупотребљеним вредностима
// од мање ка већој
for (int x = 1; x < k; x++)
{
if (!upotrebljen[x])
{
a[i++] = x;
upotrebljen[x] = true;
}
}
return true;
}
static void sve_varijacije_bez_ponavljanja(int n, int k)
{
// креирамо низ индикатора
bool[] upotrebljen = new int[n+1];
// креирамо лексикографски прву варијацију без понављања
int[] varijacija = new int[k];
for (int i = 0; i < k; i++)
{
varijacija[i] = i + 1;
upotrebljen[i+1] = true;
}
// у петљи
do {
// штампамо текућу варијацију
for (int i = 0; i < k; i++)
Console.Write("{0} ", varijacija[i]);
Console.WriteLine();
// све док постоји следећа
} while (sledeca_varijacija_bez_ponavljanja(n, varijacija, upotrebljen));
}Као и до сада можемо дефинисати и рекурзивну функцију која генерише све варијације без понављања. Поступак је сличан као раније уведени поступак за рекурзивно генерисање свих варијација са понављањем. Функција прима до сада попуњени део варијације и покушава да постави елемент на позицију . Ако је , тада је цела варијација попуњена и исписујемо је. У супротном на место редом постављамо један по један елемент скупа који није раније употребљен у варијацији и рекурзивно прелазимо на попуњавање варијације од позиције .
// помоћна функција која открива први већи неупотребљен елемент
// скупа, ако такав постоји
static int veci_neupotrebljen(int n, int x, bool[] upotrebljen)
{
// у петљи пролазимо само кроз веће елементе
for (int i = x + 1; i <= n; i++)
{
// ако постоји неупотребљен, враћамо његову вредност
if (!upotrebljen[i])
return i;
}
// ако не постоји, враћамо -1
return -1;
}
static bool sledeca_varijacija_bez_ponavljanja(int n, int[] varijacija, bool[] upotrebljen, int i)
{
// ако смо поунили велу варијацију
if (i == varijacija.Length)
{
// штампамо текућу варијацију
for (int j = 0; j < k; j++)
Console.Write("{0} ", varijacija[j]);
Console.WriteLine();
}
// ако нисмо
else
{
// у петљи
for (int x = 1; x <= n; x++)
{
// ако текући елемент није употребљен
if (!upotrebljen[x])
{
// додајемо га у варијацију
a[i] = x;
// обележавамо га као употребљеног (укључи)
upotrebljen[x] = true;
// рекурзивно креирамо све могуће суфиксе
sve_varijacije_bez_ponavljanja(n, varijacija, upotrebljen, i + 1);
// обележавамо га као неупотребљеног (искључи)
upotrebljen[x] = false;
}
}
}
}
static void sve_varijacije_bez_ponavljanja(int n, int k)
{
// креирамо низ индикатора
bool[] upotrebljen = new int[n+1];
// креирамо помоћни низ у којем чувамо текућу варијацију
int[] varijacija = new int[k];
// рекурзивно креирамо све варијације вез понављања
sve_varijacije_bez_ponavljanja(n, varijacija, upotrebljen, 0);
}Датa је реч написана малим словима енглеске абецеде. Написати програм којим се приказују у лексикографском поретку сви палиндроми који се могу добити размештањем слова дате речи.
Улаз: Прва и једина линија стандардног улаза садржи реч са највише малих слова енглеске абецеде.
Излаз: На стандардном излазу приказати тражене палиндроме. Ако се не може формирати ни један палиндром приказати цртицу -.
Задатак можемо решити тако што прво приметимо да се од датих слова може формирати палиндром ако и само се сва слова у речи јављају паран број пута, осим у случају речи непарне дужине у којој се средишње слово јавља непаран број пута. Дакле, пребројаћемо појављивања свих слова у речи помоћу низа бројача или мапе, тј. речника, а затим ћемо пронаћи слова која се јављају непаран број пута. Палиндром ће бити могуће направити ако и само ако је реч парне дужине и нема слова која се појављују непаран број пута или је реч непарне дужине и постоји тачно једно слово које се појављује непаран број пута.
Ако се од речи може направити палиндром, тада њена слова можемо поделити на две половине, када се евен- туално изузме средишње слово, сва се слова јављају паран број пута и једну половину њихових појављивања ћемо поставити у леви, а другу у десни део палиндрома. Било која пермутација слова леве половине речи даје неки палиндром - само је потребно да слова у десној половини речи буду распоређена у обрнутом редоследу. Стога крећемо од најмање пермутације у лексикографском редоследу (то је она у којој су слова сортирана) у левој половини речи и затим формирамо један по један палиндром одређујући следећу пермутацију, све док оне постоје. Да бисмо решили задатак довољно је да применимо алгоритам за генерисање следеће пермутације.
static void razmeni(char[] niz, int i, int j)
{
int tmp = niz[i];
niz[i] = niz[j];
niz[j] = tmp;
}
static SortedDictionary<char,int> prebrojSlova(string s)
{
// конструишемо сортирани речник слова и њихових појављивања
SortedDictionary<char,int> slova = new SortedDictionary<char,int>();
for (int i = 0; i < s.Length; i++)
{
int br = 0;
slova.TryGetValue(s[i]. out br);
slova[s[i]] = br + 1;
}
return slova;
}
static List<char> neparnaSlova(SortedDictionary<char,int> slova)
{
// из речника издвајамо слова која се јављају непаран број пута
List<char> neparni = new List<char>();
foreach (KeyValuePair<char,int> kvp in slova)
{
if (kvp.Value % 2 == 1)
neparni.Add(kvp.Key);
}
return neparni;
}
static bool sledeca_permutacija(char[] permutacija, int n)
{
int i, j;
// тражимо преломну тачку
int i = permutacija.Length - 2;
while (i >= 0 && permutacija[i] > permutacija[i+1])
i--;
// ако преломна тачка не постоји, стигли смо до краја
if (i < 0)
return slova;
// ако постоји, тражимо у суфиксу први већи елемент
j = n - 1;
while (permutacija[i] > permutacija[j])
j--;
// размењујемо их
razmeni(permutacija, i, j);
// обрћемо суфикс као у огледалу
for (j = n - 1, i++; i < j; i++, j--)
razmeni(permutacija, i, j);
return true;
}
static void svi_palindromi(string s) {
// из полазне речи извлачимо слова
SortedDictionary<char, int> recnik = prebrojSlova(s);
List<int> neparni = neparnaSlova(recnik);
// испитујемо да ли можемо да генеришемо палиндроме
bool postojiResenje =
(recnik.Count % 2 == 0 && neparni.Count == 0) ||
(recnik.Count % 2 == 1 && neparni.Console == 1);
// ако решење не постоји, прекидамо извршавање
if (!postojiResenje)
{
Console.WriteLine("-");
return;
}
// прву половину резултата, попуњавамо словима из речника
char[] palindrom = new char[s.Length];
int i = 0;
foreach (KeyValuePair<char,int> kvp in recnik)
{
for (int j = 0; j < kvp.Value/2; j++)
{
palindrom[i++] = kvp.Key;
}
}
// памтимо колико слова има у префиксу
int d = i;
// додајемо непарно слово ако треба
if (neparni.Count > 0)
palindrom[i++] = neparni[0];
// памтимо где почиње суфикс
int p = i;
// у петљи
do {
// копирамо префикс у суфикс
Array.Copy(palindrom, 0, palindrom, p, d);
// окрећемо суфикс као у огледалу
Array.Reverse(palindrom, p, d);
// приказујемо текући палиндомр
Console.WriteLine(new string(palindrom));
// све док постоји следећа пермутација
} while (sledeca_permutacija(palindrom, d));
}Палиндроме можемо генерисати и посебно дизајнираном рекурзивном функцијом. Ако знамо скуп слова која треба распоредити ван евентуалне средишње позиције, можемо редом анализирати могућности за прво (а уједно и последње слово). Пошто палиндроми треба да буду генерисани у лексикографском редоследу, на прво место ћемо стављати слова из тог скупа, редом, у абецедном редоследу. Након постављања неког слова на прво и последње место, изузећемо га из скупа и рекурзивно ћемо наставити попуњавање унутрашњости палиндрома. Излаз из рекурзије је када се скуп слова испразни (тада је реч попуњена и можемо је исписати).
static bool svi_palindromi(char[] permutacija, int i, SortedDictionary<char, int> recnik)
{
// ако смо генерисали целу пермутацију
if (i == permutacija.Length/2)
{
// приказујемо је
Console.WriteLine(new string(permutacija));
}
// ако нисмо
else
{
// издвајамо сва слова
List<char> slova = recnik.Keys.ToList();
// пролазимо кроз листу слово по слово
foreach (slovo in slova)
{
// ако у речнику постоје бар две копије слова
if (recnik[slovo] >= 2)
{
// уписујемо слово на почетак и на крај палиндрома
permutacija[i] = permutacija[permutacija.Length - 1 - i] = slovo;
// умањујемо број доступних копија датог слова у речнику
recnik[slovo] -= 2;
// рекурзивно генеришемо палиндром почевши од наредне позиције
svi_palindromi(permutacija, i + 1, recnik);
// враћамо назад број појављивања слова, јер их више не користимо
recnik[slovo] += 2;
}
}
}
}
static void svi_palindromi(string s) {
// из полазне речи извлачимо слова
SortedDictionary<char, int> recnik = prebrojSlova(s);
List<int> neparni = neparnaSlova(recnik);
// испитујемо да ли можемо да генеришемо палиндроме
bool postojiResenje =
(recnik.Count % 2 == 0 && neparni.Count == 0) ||
(recnik.Count % 2 == 1 && neparni.Console == 1);
// ако решење не постоји, прекидамо извршавање
if (!postojiResenje)
{
Console.WriteLine("-");
return;
}
// прву половину резултата, попуњавамо словима из речника
char[] palindrom = new char[s.Length];
// додајемо непарно слово ако треба
if (neparni.Count > 0)
palindrom[palindrom.Length/2] = neparni[0];
// генеришемо све палиндроме
svi_palindromi(palindrom, 0, recnik);
}Партиције броја представљају разлагање тог броја на сабирке чија је вредност између и . На пример, број се може партиционисати као . Свака партиција се може нормализовати тако што се претпостави, на пример, да су сабирци сортирани нерастуће. Написати програм који исписује све партиције датог броја.
Улаз: Са стандардног улаза се учитава број ().
Излаз: На стандардни излаз исписати све нормализоване партиције броја , сортиране лексикографски растуће.
С обзиром да се ради о лексикографском уређењу и овде можемо да применимо до сада уведени модел. Прво ћемо описати алгоритам којим можемо добити следећу партицију, а затим и рекурзивни поступак којим добијамо све партиције датог броја. Ради једноставности, подразумеваћемо да су елементи партиције сортирани нерастуће, тј да је партиција дата у нормализованом облику.
Прво ћемо размотрити алгоритам за креирање лексикографски следеће партиције за дату партицију. Нека је задати број и нека је партиција . Тада ће лексикографски следећа партиција бити . Одавде видимо да је потребно да неки елемент партиције, који је што је могуће више ближи крају, увећамо за један, док префикс остаје непромењен. Након увећавања изабраног броја, треба да ажурирамо суфикс партиције тако да збир остане једнак полазном броју.
Ако је партиција једночлана, тада је она лексикографски највећа. Последњи елемент низа није могуће повећати за један, јер би због очувања збира елемената партиције неки елемент пре њега морао бити смањен. чиме бисмо нарушили нормализованост елемената партиције. Наредни кандидат за повећање је претпоследњи елемент, а он се може увећати за један само ако се на месту испред њега не налази елемент који му је једнак, јер би се тада повећањем претпоследњег елемента добила партиција која није нормализована, тј. није уређена нерастуће. У супротном разматрамо елемент пре претпоследњег и тако редом, све док не наиђемо на елемент испред којег не стоји елемент који му је једнак. Тај елемент повећавамо за 1. Након тога потребно је поправити елементе иза тог увећаног елемента, тако да партиција буде лексикографски што мања. То ће се десити ако се иза увећаног елемента поставе само јединице. Да се збир не би променио, број постављених јединица треба да буде за један мањи од збира свих елемената иза елемента који смо увећали за један. Овај збир можемо израчунавати док обилазимо низ уназад тражећи најдешњи елемент који се може увећати за 1.
Пошто се дужина партиције може променити приликом преласка на следећу партицију, уместо класичног низа, партицију можемо представити неким обликом низа који допушта додавање елемената на крај. У је- зику C# то може бити листа List<>. Брисање елемената иза дате позиције можемо остварити методом RemoveRange(), а додавање елемената на крај методом Add(). Имплементација је у наставку:
static bool sledeca_particija(List<int> particija)
{
// одрећујемо дужину партиције
int n = particija.Count;
// ако је једночлана, онда је лексикографски највећа,
// па прекидамо извршавање
if (n == 1)
return false;
// у петљи одређујемо први елемент који се меже увећати
int i = 0;
// и рачунамо збир елемената у суфиксу
int zbir = particija[n-1];
for (i = n - 2; i > 0 && particija[i] == particija[i-1]; i--)
zbir += particija[i];
// уклањамо све елементе у суфиксу
particija.RemoveRange(i + 1, particija.Count - i - 1);
// увећавамо изабрани елемент за 1
particija[i]++;
// попуњавамо суфикс јединицама
for (int j = 0; j < zbir - 1; j++)
particija.Add(1);
return true;
}Описани поступак можемо искористити да генеришемо све партиције лексикографски. Довољно је да кренемо од лексикографски најмање партиције и да понављамо поступак све док постоји наредна партиција. Имплементација је у наставку:
static void sve_particije(int n)
{
// генеришемо прву партицију
List[] particija = new List<int>();
for (int i = 0; i < n; i++)
particija.Add(1);
// у петљи
do {
// приказујемо текућу партицију
for (int i = 0; i < particija.Count; i++)
Console.Write("{0} ", particija[i]);
Console.WriteLine();
// све док постоји наредна партиција
} while (sledeca_particija(particija));
}Све партиције можемо генерисати и рекурзивним поступком. Свака партиција има свој први сабирак. Свакој партицији броја којој је први сабирак () једнозначно одговара нека партиција броја , што указује да се проблем може решавати индуктивно-рекурзивном конструкцијом. Пошто је сабирање комутативно, да не бисмо суштински исте партиције понављали више пута наметнућемо услов да сабирци у свакој партицији буду сортирани нерастуће.
Дакле, ако је први сабирак , сви сабирци иза њега морају да буду мањи или једнаки од . Зато нам није довољно само да умемо да генеришемо све партиције броја , већ је потребно да ојачамо индуктивну хипотезу. Претпоставићемо да се у датом вектору на позицијама налазе раније постављени елементи партиције и да је задатак процедуре да тај низ допуни на све могуће начине партицијама броја у којима су сви сабирци мањи или једнаки . Излаз из рекурзије представљаће случај у ком је једина могућа партиција броја празан скуп, у коме нема сабирака. Тада сматрамо да је партиција успешно формирана и обрађујемо садржај комбинаторног објекта.
Као и у претходним задацима, све партиције можемо генерисати рекурзијом по позицијама или рекурзијом по вредностима.
Рекурзија по позицијама је стандардни поступак у којем је циљ размотрити све могуће дозвољене вредности сабирка на позицији . На основу услова задатка и индуктивне хипотезе, дозвољене вредности морају бити веће од и мање или једнаке , уз природан услов да морају бити и мањи или једнаки од . Ако са обележимо , тада ће могући први сабирци бити вредности у опсегу . Када фиксирамо сабирак , низ рекурзивно допуњавамо свим партицијама у којима су сви сабирци мањи или једнаки , јер је због нормализованости партиције потребно да преостали део збира буде представљен као партиција бројева који нису већи од .
У главној функцији ћемо алоцирати низ дужине , јер најдужа партиција има сабирака који су сви једнаки и захтеваћемо да се тај низ попуни почевши од позиције партицијама броја у којима су сви сабирци мањи или једнаки . Имплементација је у наставку:
static void sve_particije(int n, int[] particija, int i, int smax)
{
// ако смо стигли до краја, тј. постигли смо тражени збир
if (n == 0)
{
// приказујемо партицију
for (int j = 0; j < i; j++)
Console.Write("{0} ", particija[j]);
Console.WriteLine();
}
else
{
// ако немамо преосталих бројева које можемо да додамо
// прекидамо извршавање
if (smax == 0)
return;
// у петљи проверавамо све кандидате за вредности на позицији
for (int s = 1; s <= Math.Max(n, smax); s++)
{
// уписујемо број у партицију
particija[i] = s;
// рекурзивно генеришемо остатак партиције
sve_particije(n - s, particija, i + 1, s);
}
}
}
static void sve_particije(int n)
{
// креирамо помоћни низ у којем чувамо текућу партицију
int[] particija = new int[n];
// рекурзивно генеришемо све партиције
sve_particije(n, particija, 0, n);
}Други поступак којим можемо генерисати све партиције броја јесте рекурзија по вредностима. Уместо да се анализирају све могуће вредности сабирка на позицији , могуће је разматрати само две могућности: прву да се на позицији јавља сабирак , а другу да се на позицији јавља неки сабирак строго мањи од . Први случај је могућ само ако је и када се на позицију постави низ допуњујемо од позиције партицијама броја у којима су сви сабирци мањи или једнаки . Други случај је увек могућ и тада партицију допуњујемо партицијама броја у којима је највећи сабирак . У зависности од редоследа ова два рекурзивна позива одређује се да ли ће пермутације бити сортиране лексикографски растуће или опадајуће.
static void sve_particije(int n, int[] particija, int i, int smax)
{
// ако смо стигли до краја, тј. постигли смо тражени збир
if (n == 0)
{
// приказујемо партицију
for (int j = 0; j < i; j++)
Console.Write("{0} ", particija[j]);
Console.WriteLine();
}
else
{
// ако немамо преосталих бројева које можемо да додамо
// прекидамо извршавање
if (smax == 0)
return;
// искључујемо текући број из партиције
sve_particije(n, particija, i, smax-1);
// ако се текући број може укључити у партицију
if (smax <= n)
{
// укључујемо га
particija[i] = smax;
// и генеришемо све партиције суфикса
sve_particije(n - smax, particija, i + 1, smax);
}
}
}
static void sve_particije(int n)
{
// креирамо помоћни низ у којем чувамо текућу партицију
int[] particija = new int[n];
// рекурзивно генеришемо све партиције
sve_particije(n, particija, 0, n);
}Приметимо кључну разлику између два приказана рекурзивна поступка:
Написати програм који исписује све -тоцифрене бројеве који имају дати збир цифара.
Улаз: Прва линија садржи збир (), а друга број цифара ().
Излаз: На стандардни излаз исписати све тражене бројеве, уређене по величини.
Наивно решење у ком би се генерисали сви -тоцифрени бројеви, а затим филтрирали они чији је збир цифара једнак датом броју је прилично неефикасно. Овакво решење се своди на генерисање свих варијација са понављањем дужине скупа цифара .
Можемо да применимо идеју из претходног задатка, само што овде наша партиција мора бити фиксне дужине, јер се ради о -тоцифреним бројевима. Други услов који морамо да проверавамо јесте да је збир елемената партиције тачно . Уколико партицију нисмо попунили, тада на текућу позицију можемо да постовимо било коју цифру која је мања или једнака од минимума бројева и . Такође, морамо да водимо рачуна да на првом месту не сме бити цифра . Из описаног поступка, очигледно је да се ради о рекурзију по позицијама.
static void svi_n_cfireni_datog_zbira(int n, int[] broj, int i)
{
// проверавамо да ли смо генерисали тражени број са траженим бројем цифара
if (n == 0 && i == broj.Length)
{
// ако јесмо, приказујемо га
for (int j = 0; j < i; j++)
Console.Write("{0}", broj[j]);
Console.WriteLine();
}
else
{
// ако нисмо, у петљи
for (int c = (i == 0 ? 0 : 1); c <= Math.Max(n, 9); c++)
{
// постављамо сваку допуштену цифру на текућу позицију
broj[i] = c;
// рекурзивно генеришемо остатак броја
svi_n_cfireni_datog_zbira(n - c, broj, i + 1);
}
}
}
static void svi_n_cfireni_datog_zbira(int n, int k)
{
// креирамо помоћни низ у којем чувамо текући број
int[] broj = new int[n];
// рекурзивно генеришемо све n-тоцифрене бројеве са датим збиром
svi_n_cfireni_datog_zbira(n, broj, 0);
}У претходном решењу се на сваку позицију постављају све цифре од нуле или евентуално , на почетној позицији, па до уз евентуално одсецање када је број мањи од . Тако, на пример, може да се деси да приликом покушаја генерисања троцифрених бројева са збиром цифара на месту прве цифре испробавамо вредности од до , а да заправо ни са једном од њих не можемо да попунимо партицију до краја, јер је једино решење . Много ефикасније решење добијамо ако применимо још једно одсецање и одредимо доњу границу вредности текуће цифре. Наиме, максимални могући збир цифара иза текуће се лако добије као , где је број тренутно непопуњених цифара у партицији. Ако је текућа цифра једнака , тада мора да важи да је преостали збир цифара мањи или једнак , одакле се добија граница да је . Дакле, у петљи која поставља текућу цифру крећемо од веће од вредности и вредности , тј. на почетној позицији и завршавамо са мањом од вредности и . С обзиром на овако одређене границе, имамо гаранцију да ће свака партиција моћи успешно да се попуни и при изласку из рекурзије само треба да контролишемо да ли су све цифре партиције потпуно попуњене. Aко јесу, тада ће вредност преосталог збира сигурно бити једнака нули.
static void svi_n_cfireni_datog_zbira(int n, int[] broj, int i)
{
// проверавамо да ли смо генерисали број са траженим бројем цифара
if (i == broj.Length)
{
// ако јесмо, приказујемо га
for (int j = 0; j < i; j++)
Console.Write("{0}", broj[j]);
Console.WriteLine();
}
// ако нисмо
else
{
// одређујемо потребне вредности из описа алгоритма
int preostalOCifara = broj.Length - i;
int maksZbirIza = 9 * (preostalOCifara - 1);
int minC = Math.Max(и == 0 ? 1 : 0, n - maksZbirIza);
int maxC = Math.Min(9, n);
// у петљи
for (int c = minC; c <= maxC; c++)
{
// постављамо сваку допуштену цифру на текућу позицију
broj[i] = c;
// рекурзивно генеришемо остатак броја
svi_n_cfireni_datog_zbira(n - c, broj, i + 1);
}
}
}
static void svi_n_cfireni_datog_zbira(int n, int k)
{
// креирамо помоћни низ у којем чувамо текући број
int[] broj = new int[n];
// рекурзивно генеришемо све n-тоцифрене бројеве са датим збиром
svi_n_cfireni_datog_zbira(n, broj, 0);
}Написати програм којим се за дато и , приказују сви природни -тоцифрени бројеви такви да им је разлика две суседне цифре једнака датом броју (). На пример у броју разлика сваке две суседне цифре једнака је .
Улаз: Прва линија стандардног улаза садржи природан број (), друга линија садржи природан број ().
Излаз: Приказати тражене бројеве у растућем поретку, сваки број у посебној линија.
Задатак је могуће решити дефинисањем рекурзивне функције која генерише све тражене бројеве. Функција прима низ цифара, чијих је првих елемената већ попуњено и попуњава остатак низа. Ако је једнако дужини низа, цео низ је попуњен, па се тренутни низ само исписује. У супротном се анализирају могућности за цифру на позицији . Претпоставићемо да је , тј. да знамо вредност претходне цифре . Тада се на текућу позицију може ставити или вредност (ако је већа или једнака од ) или вредност (ако је мања или једнака од ). У случају када је , цифре и се поклапају (обе су једнаке ) па је довољно анализирати само једну од њих. Након постављања цифре на позицију , рекурзивно попуњавамо остатак низа (прослеђујући вредност ). Прва цифра је специфична и њу ћемо попунити пре првог рекурзивног позива. На прво место можемо ставити било коју цифру осим нуле и за сваки избор те прве цифре вршимо посебан рекурзивни позив за .
static void svi_n_cfireni_sa_razlikom_k(int[] broj, int n, int k, int i)
{
// проверавамо да ли смо генерисали број са траженим бројем цифара
if (i == broj.Length)
{
// ако јесмо, приказујемо га
for (int j = 0; j < i; j++)
Console.Write("{0}", broj[j]);
Console.WriteLine();
}
// ако нисмо
else
{
// проверавамо да ли постоји мања цифра коју можемо додати броју
if (a[i-1] - k >= 0)
{
// додајемо је
a[i] = a[i-1] - k;
// рекурзивно попуњавамо суфикс
svi_n_cfireni_sa_razlikom_k(broj, n, k, i + 1);
}
// проверавамо да ли постоји већа цифра коју можемо додати броју
if (k > 0 && a[i-1] + k < 10)
{
// додајемо је
a[i] = a[i-1] + k;
// рекурзивно попуњавамо суфикс
svi_n_cfireni_sa_razlikom_k(broj, n, k, i + 1);
}
}
}
static void svi_n_cfireni_sa_razlikom_k(int n, int k)
{
// креирамо помоћни низ у којем чувамо текући број
int[] broj = new int[n];
// на прво место постављамо све могуће цифре
for (int i = 1; i <= 9; i++)
{
broj[0] = i;
// рекурзивно генеришемо све n-тоцифрене бројеве са датим збиром
svi_n_cfireni_sa_razlikom_k(broj, n, k, 1);
}
}