Все ссылки на статьи и ролики моего канала Old Programmer расположенные по темам: Программирование. Тематическое оглавление моего Zen-канала (Old Programmer). А здесь все мои ресурсы по рекурсивному программированию.
В моём новом канале, посвящённом программированию на Python есть статья, посвященную алгоритму генерации сочетаний
и целый раздел, посвящённый комбинаторике
Что такое сочетание в математике
Сегодня снова моя любимая тема: рекурсивное программирование. Рассмотрим генерацию количества сочетаний из n по k. Количество сочетаний вычисляется по следующий формуле (см. Рисунок 1). Оно отличается от числа размещений тем, что внутри подмножества генераций перестановок не происходит. Т.е. подмножества (сочетание по 3) 1 2 3 и 2 3 1 считаются тождественными.
Как генерировать сочетания программно
Теперь вспомним нашу статью о генерации размещений. Убедимся, что количество сочетаний меньше количества размещений в k! раз. Это и понятно, ведь мы не учитываем перестановки внутри подмножества. Это наталкивает на мысль, что можно взять программу main60.c из статьи и просто ее доработать. Собственно это я и сделал. Программы в сущности отличаются только циклами внутри рекурсивной функции (см. main60.c и main125.c). Заголовок
for(int i=h+1; i<n; i++)
как раз и обеспечивает нас тем, что перестановки внутри подмножества не генерируются. Сравним с
for(int i=0; i<n; i++)
из main60.c (статья о генерации размещений)
Пример.
На входе:
1 2 3 4
3
На выходе:
1 2 3
1 2 4
1 3 4
2 3 4
4
Пока все о рекурсии, до следующих встреч. Подписываемся на мой канал Old Programmer.
Я вижу, что вы забыли поставить ЛАЙК, не так ли?
