Школа программиста
Резервная копия - VPS Hoster 

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

HotLog


 

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

Перестановка – упорядоченный набор чисел 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++. Однако, подобную функцию можно реализовать, например, следующим образом:

def next_permutation(a): res = False i = len(a)-2 while i>=0 and a[i]>=a[i+1]: i -= 1 if i>=0: k = len(a)-1 while a[k]<=a[i]: k -= 1 a[i],a[k] = a[k],a[i] res = True a[i+1:] = reversed(a[i+1:]) return res

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

s = sorted(list(input())) print(''.join(s)) while next_permutation(s): print(''.join(s))

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

from itertools import permutations for s in set(permutations(list(input()))): print(''.join(s))

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

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

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



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