Combinatorics Algorithm

Combinatorics Algorithm

1. Nested Loops

   • НЕДОСТАТЪК! Написване на код за всяка задача

2. Използване на рекурсия

   • Имитира nested loops
     • Броя на "вместванията" е броят на елементите
     • Това може да е бавно!
   • Използва функция, която извиква себе си рекурсивно
     • Аргументи
       • Масив
         • Броят на елементите на масива, е равен на броя на елементите в комбинацията
       • Минимална и максимална стойност
         • За простота - минималната е нула, задаваме за максимална цяло положително число
           • Така максималната стойност е броя на позициите
       • Индекс, който се променя на всяка рекурсивна стъпка
         • Намаляваме или увеличаваме индекса - два различни варианта на алгоритъма
         • Използваме проверката за индекса като "дъно на рекурсията"
     • Без повторения?
       • Допълнителен масив за "използвани елементи
     • Ускоряване на търсенето
       • Намаляване на броя на елементите, като се прави "размяна" на вече обработен елемент с преместването му в края на масива

3. Използване на бройни системи

   • Всеки запис на число в определена бройна система, може да се разглежда като резултат от комбиниране на елементи
     • "Базата" е броят на елементите, които участвуват
     • "дължината на числото" = на използваните позиции
   • Ако търсим решение за елементи до 10 броя може да е удачно решение
     • Ще се наложи да се напише функция за превръщане от десетична в друга бройна система
   • За повече от 10 елемента, като броят е различен от 16 ще е трудно!!

4. Свойства на резултата

   • Колко елементи участвуват
   • В колко позиции
   • С повторение
   • Без повторение