Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Алгоритм генерации перестановок на языке Python
Начинаю целую серию статей о комбинаторных алгоритмах. Алгоритмы, конечно, жадные, но увлекательные. Мне скажут, что есть же библиотеки, зачем самим то. Но это же интересно. А по библиотекам будут ещё уроки, в частности по itertools.
Алгоритм генерации перестановок, в действительности, совсем не сложный, если вникнуть в смысл. Напомню, что количество перестановок считается по формуле n!.
Программа генерации перестановок массива см. ниже.
Несколько замечаний по программе.
- Исходный массив для перестановок ll. Массив lss вспомогательный массив. Элементы его двухкомпонентные. Первая компонента это элемент массива, вторая флаг, который определяет, что данный элемент массива ll уже использован в генерации очередной перестановки.
- В цикле ищется свободный элемент массива ll. Он присваивается очередному элементу массива lss. После этого вызывается рекурсивно функция perm(). Если параметр равен n, значит очередная перестановка сгенерирована. Если нет, то в цикле опять ищется свободный элемент массива ll. При этом пропускается элементы, используемые на предыдущих шагах рекурсии.
Ниже представлен вариант того же решения, но без использования в рекурсии глобальных переменных. Некоторые считают, что использование в рекурсивной функции глобальных переменных это дурной тон. Ну Бог им судья!
Кстати, в качестве тренировки. Дополните программу возможностью подсчёта количества перестановок. Конечно, мы знаем, что их n!, но попробуйте подсчитывать их непосредственно с учётом получения очередной перестановки.
Следующая статья по комбинаторике на Python...
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
