Наиболее важными типами комбинаторных объектов являются перестановки,
сочетания и подмножества данного множества.
Начнем с перестановок.
Применим метод уменьшения размера к задаче о генерации всех `n!` перестановок
множества `{1,..., n}`. Задача меньшего
на единицу размера состоит в генерации всех `(n-1)!` перестановок.
Мы можем получить решение большей задачи путем вставки `n` в каждую из `n` возможных
позиций среди `(n-1)` элементов каждой из перестановок.
Все получаемые таким образом перестановки будут различны,
а их общее количество будет равно `n(n-1)! = n!`.
Следовательно, таким образом мы получим все перестановки множества
`{1,...,n}`.
--
К задаче о генерации подмножеств также непосредственно применим метод уменьшения размера
на единицу.
Все подмножества множества `A = {a_1,..., a_n}` можно разделить на
две группы — те, которые содержат элемент `a_n`, и те, которые не содержат его.
Первая группа представляет собой не что иное, как все подмножества
множества `{a_1,..., a_{n-1}}`, в то время как все элементы второй группы можно
получить путем добавления элемента `a_n` к подмножествам множества `{a_1,..., a_{n-1}}`.
Следовательно, мы можем получить все подмножества множества `A`, объединяя
список всех подмножеств множества `{a_1,..., a_{n-1}}` с аналогичным списком, в
в котором к каждому подмножеству добавлен элемент `a_n`.
--
Более простой способ решения поставленной задачи основан на взаимно
однозначном соответствии между всеми `2^n`
подмножествами `n`-элементного множества `A = {a_1,..., a_n}` и всеми `2^n`
битовыми строками `b_1,..., b_n` длиной `n`. Если `b_i = 1`, то `a_i`
включен в подмножество, иначе `a_i` не входит в множество. Например,
строка 101 представляет подмножество `{a_1,a_3}`.
Используя такое соответствие, мы можем сгенерировать все битовые строки длиной `n`, просто
перебирая последовательно двоичные числа от 0 до `2^n - 1`.
--
Сочетания можно рассматривать как подмножества размером `k`.
Метод уменьшения размера можно применить для получения `k`-й перестановки
или `k`-го подмножества и, наоборот,
для получения номера заданной перестановки или подмножества.
---
##### Задания для практики
1. Отряд из `n` солдат должен переправиться через широкую и глубокую реку, через которую нет моста. Солдаты заметили лодку с двумя мальчишками, но лодка так мала, что в ней могут поместиться либо два мальчишки, либо один солдат. Как солдатам переправиться через реку и после переправы возвратить лодку мальчишкам? Сколько раз при этом лодка проплывет от берега к берегу?
2. Разработайте алгоритм на основе метода уменьшения размера для генерации всех комбинаций из `k` элементов, выбранных из `n`-элементного множества (т.е. всех `k`-элементных подмножеств данного `n`-элементного множества).