Question

Докажите,что любую транспозицию в перестановке можно выполнить с помощью транс позиций смежных элементов

Answer 1

Объем вычислительной работы будет значительно меньше, если порождать последовательность перестановок в порядке минимального изменения позиций элементов при переходе к каждой следующей перестановке. Для того, чтобы изменение было минимальным, любая перестановка должна отличаться от предыдущей транспозицией двух соседних (смежных) элементов. Например, следующие перестановки на множестве 3-х первых цифр римской системы счисления {I, V, X} отличаются транспозицией подчеркнутых смежных элементов:Пт: (I) ; (V) ; (X) ; (I) ; (V) ; (VIX)Транспозитивная последовательность легко выстраивается по следующему рекурсивному правилу. Пусть уже имеется последовательность (n-1)! перестановок из (n-1) элементов, в которой соседние перестановки отличаются транспозицией смежных элементов. Каждую из этих перестановок можно расширить до n-перестановки, добавляя элемент n на каждую позицию справа-налево для нечетных по номеру (n-1) перестановок и слева-направо для четных по номеру (n-1) перестановок. Порядок порождаемых таким образом перестановок для 3-х первых целых чисел показан на следующей диаграмме:П3:(123)1 (132)2 (312)3 (321)4 (231)5 (213)6- |-------------^------------------| |-----------------^----------------|- справо-налево слева-направо- П2:(12)1<-3 : добавить : 3-> (21)2- нечетно четно- |------------------------------^----------------------|- П1(1)1 <-2: добавить справа-налево- нечетноИз этой диаграммы должно быть понятно, что сначала из тривиальной 1-ой перестановки (1) добавлением справа-налево элемента 2 порождается последовательность 2-перестановок П2, содержащая перестановки (12) и (21). Затем в них добавляется элемент 3, соответственно справа-налево, чтобы получить в итоге желаемую последовательность П3, которая состоит из следующих 3-перестановок:П3:(1 2 3); (1 3 2); (3 1 2); (3 2 1); (2 3 1); (2 1 3)