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

165

365

Посмотреть ответы 2

Ответы на вопрос:

DorzayS

Алгебра

4,4(52 оценок)

Объем вычислительной работы будет значительно меньше, если порождать последовательность перестановок в порядке минимального изменения позиций элементов при переходе к каждой следующей перестановке. для того, чтобы изменение было минимальным, любая перестановка должна отличаться от предыдущей транспозицией двух соседних (смежных) элементов. например, следующие перестановки на множестве 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)