Комбінації генеруються в лексикографічному порядку. Алгоритм працює з порядковими індексами елементів множини.
Розглянемо алгоритм на прикладі.
Для простоти викладу розглянемо безліч з п'яти елементів, індекси в якому починаються з 1, а саме, 1 2 3 4 5.
Потрібно згенерувати всі комбінації розміру m = 3.
Спочатку Ініціалізація перша комбінація заданого розміру m - індекси в порядку зростання
1 2 3
Далі перевіряється останній елемент, т. Е. I = 3. Якщо його значення менше n - m + i, то він инкрементируется на 1.
1 2 4
Знову перевіряється останній елемент, і знову він инкрементируется.
1 2 5
Тепер значення елемента дорівнює максимально можливому: n - m + i = 5 - 3 + 3 = 5, перевіряється попередній елемент з i = 2.
Якщо його значення менше n - m + i, то він инкрементируется на 1, а для всіх наступних за ним елементів значення прирівнюється до значення попереднього елемента плюс 1.
1 (2 + 1) 3 (3 + 1) 4 = 1 3 4
Далі знову йде перевірка для i = 3.
1 3 5
Потім - перевірка для i = 2.
1 4 5
Потім настає черга i = 1.
(1 + 1) 2 (2 + 1) 3 (3 + 1) 4 = 2 3 4
І далі,
2 3 5
2 4 5
3 4 5 - остання поєднання, так як всі його елементи рівні n - m + i.
Схожі калькулятори:
Увійти через Facebook Увійти через Vk увійти через Twitter Увійти через PlanetCalc