Перебор всех перестановок
В комбинаторике перестановкой называется упорядоченный набор элементов, составленный из элементов исходного множества без повторений.
Перестановка, о которой мы здесь поговорим, заключается в том, как расположить n объектов в n позициях. Причем, в перестановке важен порядок элементов.
Как перечислить все перестановки?
Начнем с наименьшего числа (с 1) и далее будем получать все остальные перестановки из оставшихся чисел. Потом возьмем следующее после минимального и опять будем отавлять перестановки из оставшихся чисел по такому же принципу.
Например, нам необходимо перебрать все перестановки длиной 3 из первых трех букв английского алфавита. По описанному выше принципу перечисления перестановок, выглядеть список будет таким образом:
ABC
ACB
BAC
BCA
CAB
CBA
Всего перестановк из трех элементов 6.
Для n объектов количество перестановок равно
Pn = n!.
Рассмотрим другой полезный подход к решению задачи перебора. Идея заключается в том, чтобы создать глобальный массив, назовем его used, который будет содержать информацию о том, использовали ли мы каждое число или нет. Когда мы рассматриваем очередной элемент для добавления в перестановку, мы проверяем значение в used для этого элемента. Если оно равно false, то это значит, что число ещё не использовалось, и мы можем включить его в перестановку. Затем мы помечаем этот элемент как использованный, устанавливая соответствующий флаг в used на значение true.
Таким образом, мы гарантируем, что каждое число будет использовано только один раз в перестановке, и избегаем повторений.
Запишем алгоритм на псевдокоде
алгоритм generate(n, used, pref)
если длина(pref) = n то
check(pref)
иначе
для каждого next от 1 до n выполнить
если not used[next] то
used[next] = True
generate(n, used, pref + [next])
used[next] = False
конец если
конец цикла
конец если
конец алгоритма
В программе выше используется алгоритм
generate, который принимает три параметра:
n (максимальное число в перестановке),
used (массив, отслеживающий использованные каждого числа) и
pref (текущий префикс перестановки). Если префикс имеет длину
n, значит мы добавили в перестановку все числа. Вызываем процедуру
check для обработки перестановки.
Иначе, для каждого числа
next от 1 до
n (включительно), мы проверяем, было ли число использовано ранее (проверка
not used[next]). Если число не использовалось, помечаем его как использованное (
used[next] = True), рекурсивно вызываем алгоритм
generate с обновленными значениями
used и
pref, и затем освобождаем число для следующей ветки (следующей перестановки), помечая его как неиспользованное (
used[next] = False).
Реализуйте данный алгоритм на знакомом вам языке программирования!