Методы уменьшения размера задачи

Наиболее важными типами комбинаторных объектов являются перестановки, сочетания и подмножества данного множества.

Начнем с перестановок. Применим метод уменьшения размера к задаче о генерации всех `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`-элементного множества).