9.6 Генерация подмножеств с заданным нижним и верхним числом элементов

Пусть необходимо получить подмножество множества En, мощность которого не менее k и не более m. Причем 0 <= m <= k <= n. При k, равном m, это будет просто сочетание, и количество подмножеств можно вычислить по формуле сочетаний Eсли m и k разнятся на единицу, то необходимо найти сумму сочетаний

в общем случае количество подмножеств можно подсчитать по следующей формуле:

(9.8)

При m = 0 и k = n формула (9.8) приводит к известному тождеству:

Алгоритм генерации следующий.

Дано: множество En, m - нижняя граница, k - верхняя граница и целое число j - номер подмножества. Для j справедливо неравенство

Необходимо построить искомое подмножество.
1. Для i = m, k найти такое значение, чтобы выполнилось неравенство

(9.9)