Задача, которая на Python решается практически в одну строчку. Но благодаря ей, познакомимся с ещё одной полезной функцией стандартной библиотеки. Читаем условие:
Для начала надо определить, сколько может быть перестановок, чтобы понять, можем ли мы использовать Python или потребуется что-нибудь быстрее. Так как символы не повторяются, количество различных перестановок равно факториалу от N. То есть в самом худшем случае будет 8! = 40,320 перестановок.
Вывод очередной перестановки (как и построение следующей из предыдущей) занимает O(N) времени. Грубыми прикидками получаем существенно меньше миллиона операций, поэтому можем решать на Python.
Более того, мы будем использовать готовую функцию из библиотеки itertools, написанную на С++, то есть всё будет совсем быстро. Эта функция permutations:
itertools.permutations(iterable, r=None)
Return successive r length permutations of elements from the iterable.
If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.
The permutation tuples are emitted in lexicographic order according to the order of the input iterable. If the input iterable is sorted, the output tuples will be produced in sorted order.
То есть на вход функции можно передать любой итерируемый объект (список, кортеж, строку и т.д.), а она вернёт последовательность кортежей с перестановками.
С помощью параметра r можно ещё ограничить длину выходных перестановок. Но в нашем случае этого не требуется. И важное свойство функции - перестановки генерируются в лексикографическом порядке (относительно входного порядка элементов). В нашей задаче это не нужно, но если бы перестановки надо было выводить в алфавитном порядке, то мы могли бы просто отсортировать исходную строку и точно так же скормить её этой функции.
С матчастью закончили, пишем максимально простое решение:
Единственный момент - это преобразование кортежей с перестановками обратно в строки.
Предыдущий выпуск: Задача 156. Шахматы - 2
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.