Перестановки. Построение перестановки по таблице инверсий. (Лекция 6)
Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех объектов — а, b и с — существует шесть перестановок: аbс, acb, bac, bса. cab, cba. Для множества из N элементов можно построить N! различных перестановок: первую позицию можно занять N способами, вторую — (N – 1) способом, так как один элемент уже занят, и т. д. На последнее место можно поставить только один оставшийся элемент. Следовательно, общее количество вариантов расстановки равно N ⋅ (N −1) ⋅ (N − 2) ⋅ ... ⋅ 1 = N! Далее будем рассматривать перестановки элементов множества {1, 2, 3, … , N} Инверсии Пусть даны базовое множество из N элементов 1,2, 3,..., N и его перестановка Пара называется инверсией (инверсионной парой) перестановки , если при i < j. Например, перестановка 4, 1, 3, 2 имеет четыре инверсии: (4,1), (3,2), (4,3) и (4,2). Единственной перестановкой, не содержащей инверсий, является упорядоченная перестановка 1, 2, 3, ... , N. Таким образом, каждая инверсия — это пара элементов перестановки, нарушающих ее упорядоченность.
