Модуль: Перебор перестановок


Задача

1 /4


Все перестановки

Теория Нажмите, чтобы прочитать/скрыть

Перебор всех перестановок

 
В комбинаторике перестановкой называется упорядоченный набор элементов, составленный из элементов исходного множества без повторений


Перестановка, о которой мы здесь поговорим, заключается в том, как расположить 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 до (включительно), мы проверяем, было ли число использовано ранее (проверка not used[next]). Если число не использовалось, помечаем его как использованное (used[next] = True), рекурсивно вызываем алгоритм generate с обновленными значениями used и pref, и затем освобождаем число для следующей ветки (следующей перестановки), помечая его как неиспользованное (used[next] = False).

Реализуйте данный алгоритм на знакомом вам языке программирования!

Задача

Вам дано натуральное число n. Выведите все перестановки размера n в лексикографическом порядке.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 7).

Выходные данные
Выведите все перестановки по возрастанию в лексикографическом порядке. Каждую в отдельной строке. Числа в перестановке должны быть отделены пробелами.

 


Примеры
Входные данныеВыходные данные
1 3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6437
Java1
Python109
Комментарий учителя