WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном (англ.) в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества

где означает, что пробегает все разбиения и  — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки .

Алгоритм

Алгоритм Робинсона — Шенстеда начинает работу с перестановки , записанной в лексикографическом порядке:

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

где  — пустые таблицы. На выходе получаются таблицы и .

На основе построенной формируется путём вставки Шенстеда (см. ниже) в . К добавляется в квадрат, добавленный к форме при вставке, чтобы формы для и были одинаковы для каждого . Таким образом, стандартная таблица записывает перестановку, а  — регистрирует «рост» диаграммы Юнга[1].

Вставка (4):
• (4) заменяет (5) в первой строке
• (5) заменяет (8) во второй строке
• (8) записывается в начало новой строки

Неформальное описание вставки Шенстеда

Для вставки строки в таблицу :

   1. сделать первую строку T текущей
   2. в текущей строке найти первый элемент, который больше x
   3. если такой элемент найден
        обменять значения x и найденной ячейки
        сделать следующую строку текущей
        перейти на шаг 2.
      иначе:
        добавить x к концу текущей строки
        закончить

Вариации и обобщения

Примечания

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии