Во вчерашнем выпуске Футурама поставила довольно интересную проблему — я не мог не проанализировать ее здесь.
Итак, сюжет такой: Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одном направлении.
После нескольких перестановок герои оказались в сложной ситуации, в которой им пришлось найти способ вернуться обратно в свои тела.
Вот здесь нам поможет «чистая математика» .
Итак, давайте начнем.
Позволять 
представляет собой цикл длины к на съемочной площадке [п] = {1… п} .
Не ограничивая общности, запишем:
Пусть это сейчас (а, б) это транспозиция, которая меняет содержимое а И б .
По предположению,
полученный с помощью некоторых замен над [н] .
Давайте представим два «новых тела» {х, у} и запиши
Для любого я = 1,… к давай запишем 
как серия перестановок:
Обратите внимание, что транспозиции изменяют элемент с [н] с любым элементом из {х, у} , поэтому все транспозиции отличаются от тех, которые образовали исходную замену
, а также от транспонирования (х, у) .
Проведя простую проверку, мы получаем:
Таким образом,
инвертирует цикл длины к , уход Икс И й переставить без использования транспозиции (х, у) .
Теперь позвольте
— случайная замена; он распадается на композицию независимых циклов, каждый из которых можно инвертировать с помощью полученного выше алгоритма, после чего при необходимости их можно поменять местами Икс И й , используя транспозицию (х, у) .
Так что.
А вы говорите, что у дискретного нет приложений в реале.
Теги: #футурама #дискретная математика #перестановки #алгоритмы #математика
-
Требуется Осторожность
19 Oct, 24 -
Экономика Внимания Почти Мертва
19 Oct, 24 -
Виртуальная Реальность На Мкс
19 Oct, 24 -
Поведенческий Измеритель
19 Oct, 24
