Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Понятие перестановки

Перестановка – упорядоченный набор чисел 1, 2, 3, …, n, обычно трактуемый как биекция на множестве {1, 2, 3, … , n}, которая i-й элемент из набора ставит в позицию, равную элементу перестановки ai. Значение n называют порядком перестановки.

Количество всевозможных перестановок из n элементов:

Например, перестановка (5, 1, 6, 4, 2, 3) имеет 6-ю степень и последовательное ее применение приводит к следующей последовательности:

(1,2,3,4,5,6) → (2,5,6,4,1,3) → (5,1,3,4,2,6) →
(1,2,6,4,5,3) → (2,5,3,4,1,6) → (5,1,6,4,2,3) → (1,2,3,4,5,6)

Любая последовательность применения перестановки приводит к циклу, который распадается на простые циклы:

Если L1, L2, …, Lk – длины простых циклов, то степень перестановки (длина всего цикла) равна:

L = НОК(L1, L2, …, Lk)

Значение L соответствует минимальному количеству применений перестановки к единичной перестановке так, что та переходит сама в себя, образуя цикл.

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

В библиотеке algorithm языка C++ есть функция next_permutation, которая позволяет по заданной перестановке получать следующую лексикографически минимальную. При этом функция возвращает true, если таковая перестановка существует. Очевидно, что для максимальной перестановки следующей не существует. В этом случае функция возвращает false и преобразует исходную максимальную перестановку в минимальную. В качестве входных данных может использоваться статический массив, вектор или строка:

В качестве входных данных для функции next_permutation может выступать не обязательно перестановка, то есть могут быть и повторяющиеся элементы. Также следует здесь упомянуть о существовании функции prev_permutation, которая позволяет получить предыдущую перестановку аналогичным образом.

С использованием функции next_permutation несложно организовать перебор всех возможных перестановок. Например, перебор всех возможных перестановок символов строки, заданной во входных данных, может быть следующим:

Next_permutation в Python

В стандартных библиотеках языка Python нет аналога функции next_permutation из C++. Однако, подобную функцию можно реализовать, например, следующим образом:

Тогда реализация аналогичного перебора всех возможных перестановок символов строки, заданной во входных данных, на языке Python при использовании вышеописанной функции будет следующей:

Заметим, что такая задача может быть решена с использованием функции permutations из библиотеки itertools следующим образом:

Однако, такое решение требует больше памяти и времени. Плюсом такого решения является только скорость реализации данного кода.

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Перестановки
 Структуры данных
 Библиотека алгоритмов
 A. Анаграмма
 B. Следующая перестановка ...
 C. Перестановки
 D. Перестановки - 2
 E. K-перестановки
 F. Задача о назначениях
 G. Следующее число
 H. Степень перестановки
 I. Перетягивание каната
 J. Перестановки - 3

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



Профессиональное оборудование и оснащение учебных аудиторий на сайте audioprofi.ru