На этом шаге мы определимся с дальнейшим изложением.
Мы только что узнали, что задача об n ферзях сводится к задаче о перестановке первых n неотрицательных целых чисел, которая будет возникать во многих задачах. Кроме этого, большое число других задач сводится к нахождению различных подмножеств множества из n элементов. Поэтому важно знать, как генерировать перестановки и подмножества множества из n различных элементов. Далее приводятся алгоритмы, генерирующие такие комбинаторные объекты. Польза их в том, что они могут послужить отправными точками при разработке алгоритмов перебора с возвратами для многих других задач.
Отметим, что эти алгоритмы не будут создавать списков или иных структур данных для хранения всех подмножеств или перестановок. Это было бы непрактично из-за большого количества вариантов (для множества из n различных элементов существует n! перестановок и 2n подмножеств). Вместо этого методы будут использовать простой список, который содержит только одно частичное или полное решение (подмножество или перестановку) и обновляется в процессе выполнения алгоритма. Таким образом, методы будут выдавать все решения, не сохраняя их в единой структуре данных, а просто печатая их или подсчитывая их количество во время выполнения.
На следующем шаге мы рассмотрим подмножества.
