Подразделы

Другие разделы

Дата и время

16/12/2025 00:26:36

Авторизация

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

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Алгоритмы генерации комбинаторных объектов

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

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

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

Алгоритмы генерации комбинаторных объектов