Глава 2. Порождение комбинаторных объектов.

2.2. Перестановки
  2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности длины n, в которые каждое из чисел 1..n входит по одному разу). Решение. Перестановки будем хранить в массиве x[1],...,…
2.3. Подмножества
  2.3.1. Перечислить все k-элементные подмножества множества {1..n}. Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц.…
2.4. Разбиения
  2.4.1. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1,…
2.5. Коды Грея и аналогичные задачи
Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода. 2.5.1. Перечислить все последовательности…
2.6. Несколько замечаний
  Посмотрим ещё раз на использованные нами приёмы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного…
2.7. Подсчет количеств
  Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя…
2.1. Размещения с повторениями
  Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества.   2.1.1. Напечатать все последовательности длины k из чисел 1..n. Решение. Будем печатать…