Преобразование Шютценберже – Студенческая лаборатория компьютерной математики

Основные понятия.

Преобразование Шютценберже перестраивает таблицу Юнга $T_n$ в таблицу Юнга $T_{n-1}$ .

Для этого выполняется следующая последовательность шагов:

Из таблицы удаляется первая клетка.
На свободное место перемещается одна из двух, расположенных сверху и справа от удаленной, соседних клеток, имеющих меньшее значение.
Освободившееся после перемещения клетки место заполняется по тому же принципу. Процесс повторяется до тех пор, пока не будет достигнута угловая клетка.
Все значения в таблице уменьшаются на единицу.

Декремент всех значений, выполняющийся на четвёртом шаге алгоритма, необходим для приведения таблицы Юнга к стандартному виду. В ином случае максимальный элемент таблицы Юнга будет иметь значение $n$ при размере таблицы $n-1$ .

Клетки, окрашенные в зеленый цвет, образуют нерв таблицы Юнга ( путь Шютценберже ) – множество клеток, перемещаемых в таблице Юнга при применении преобразования Шютценберже.

Неоднозначность преобразования Шютценберже.

После применения преобразования Шютценберже из полученной таблицы Юнга $T_{n-1}$ невозможно восстановить исходную таблицу $T_n$ . Это объясняется тем, что для таблицы $T_{n-1}$ могут существовать несколько различных таблиц-прообразов $T^i_n$ . В этом состоит неоднозначность преобразования Шютценберже.

Например, при применении преобразования Шютценберже к изображенным выше таблицам $T^1_n$ , $T^2_n$ и $T^3_n$ будет получена одна и та же таблица $T_{n-1}$ . Таким образом, по таблице $T_{n-1}$ невозможно точно определить, из какой таблицы Юнга она была получена.

Обобщение преобразования Шютценберже на трёхмерные и четырёхмерные таблицы Юнга.

При работе с трёхмерными и четырёхмерными таблицами Юнга алгоритм преобразования остается неизменным, за исключением количества соседних клеток, одна из которых будет перемещена на освободившееся после удаления первой клетки место.

Если пустая клетка имеет координаты $(x, y)$ , то на ее место будет перемещена клетка, имеющая наименьшее значение и стоящая на позиции $(x+1, y)$ или $(x, y+1)$ .

Для клетки с координатами $(x, y, z)$ трёхмерной таблицы Юнга соседними будут считаться: $(x+1, y, z)$ , $(x, y+1, z)$ , $(x, y, z+1)$ , то есть, правая, верхняя, и стоящая в следующем слое, над свободной, соответственно. Пример преобразования Шютценберже для такой таблицы представлен ниже.

В 4D таблице у клетки с координатами $(x, y, z, l)$ соседние клетки: $(x+1, y, z, l)$ , $(x, y+1, z, l)$ , $(x, y, z+1, l)$ и $(x, y, z, l+1)$ . Пример преобразования Шютценберже на четырёхмерной таблице Юнга представлен ниже.

Программная реализация преобразования Шютценберже.

Способы представления таблиц Юнга при программной реализации.

Чтобы задать конкретную таблицу Юнга, необходимо хранить все клетки, из которых она состоит. Клетка имеет две характеристики: координаты (в двумерном случае – пара чисел, в трехмерном – тройка, в четырехмерном – четверка) и значение, записанное в ней.

Стандартное представление таблиц Юнга как двумерного массива целых чисел имеет недостаток с точки зрения вычислительной стоимости и использования памяти. Это связано с тем, что в этом случае преобразование Шютценберже требует перенумерации всех клеток в таблице.

При программной реализации клетки таблицы хранятся в виде односвязного линейного списка, в котором элементами являются координаты клеток. Позиции элементов соответствуют значениям, записанным в клетках.

Например, на представленном ниже рисунке первым элементом списка будет клетка, хранящая значение 1, вторым – значение 2 и так по возрастанию.

Начало списка для данного примера будет следующим: $(0, 0); (0,1); (1,0); (2,0); (1,1);(0,2);(3,0)$ и т. д.

Такой способ хранения позволяет компактно хранить таблицы произвольной размерности, дает возможность восстанавливать соответствующие диаграммы Юнга.

Рассмотрим реализацию алгоритма для двумерных таблиц Юнга.

В начале алгоритма происходит удаление первой клетки (первого элемента списка), на ее месте образуется активная клетка: пустая клетка, на место которой нужно переместить соседнюю. То есть, активная клетка на данном шаге будет иметь координаты $(0,0)$ .

Следующий шаг: поиск соседней клетки с наименьшим значением, так как значения в клетках не убывают, то это будет первая найденная соседняя клетка, которая будет переставлена на место активной, а образовавшееся пустое место становится новой активной клеткой. При этом все не соседние клетки остаются на своих местах.

Условие окончания: алгоритм останавливается, когда все клетки таблицы будут обработаны.

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

Обозначения в листинге:
tab – таблица Юнга
actX, actY – координаты текущей активной клетки

Листинг. Преобразование Шютценберже на 2D-таблицах Юнга.

schutz(tab) 
	{
	// удаление первой клетки таблицы
	tab.remove(0, 0);
	// инициализация координат активной клетки
          actX = 0; actY = 0;
	// для каждой (x, y) таблицы Юнга
		for (it = tab.begin(); it != tab.end(); ++it)
		{
			// соседние клетка справа и сверху от активной
			if ((x == actX + 1) && (y == actY))  || 
			((x == actX) && (y == actY + 1)) 
			{
				// удаление из таблицы клетки
				tab.remove(x, y);
				// добавление активной клетки в таблицу
				tab.insert(actX, actY);
				// новая активная клетка
				actX = x; actY = y;
			}
		}          
		// функция возвращает координаты удаленной клетки
		return (actX, actY);
	}

Инволюция Шютценберже.

Инволюция – преобразование, обратное самому себе. Функция $f(x)$ называется инволюцией, если $f(f(x))=x$ для любого $x$ из области определения функции $f$ .

Примеры инволюции:

$f(x)=-x$ ;
$f(x)=\bar{x}$ ;
комплексное сопряжение;
транспонирование матрицы;
вычисление обратной матрицы;
вычисление обратной перестановки.

Инволюция Шютценберже ( двойственность Шютценберже ) – процедура, в ходе которой к таблице Юнга из $n$ клеток $n$ раз применяется преобразование Шютценберже, при этом на каждом шаге сохраняются координаты удаляемых клеток. По полученной последовательности координат строится новая таблица Юнга.

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

Связь между преобразованиями RSK и Шютценберже.

Алгоритм Робинсона-Шенстеда-Кнута (RSK) по последовательности натуральных чисел от 1 до $n$ формирует пару таблиц Юнга одинаковой формы: записывающую ( $P$ ) и нумерующую ( $Q$ ), которая фиксирует расширение записывающей таблицы.

Пусть дана бесконечная последовательность вещественных чисел $\sigma_1$ . Последовательность $\sigma_2$ получается из $\sigma_1$ сдвигом влево (стиранием первого элемента). После применения к последовательностям алгоритма RSK будут получены две пары таблиц: $P_1$ и $Q_1$ , $P_2$ и $Q_2$ для $\sigma_1$ и $\sigma_2$ соответственно.

В таком случае таблица $Q_2$ является результатом преобразования Шютценберже таблицы $Q_1$ .

Рассмотрим утверждение на примере, приведенном ниже.

Пусть дана последовательность натуральных чисел: $\sigma_1=\{2, 3, 9, 8, 4, 10, 1, 6, 7, 5\}$ .

Применим к последовательности $\sigma_1$ алгоритм RSK:

Выполним сдвиг влево последовательность $\sigma_1$ , получаем $\sigma_2=\{3, 9, 8, 4, 10, 1, 6, 7, 5\}$ .

Применим к последовательности $\sigma_2$ алгоритм RSK:

В результате имеем две нумерующие таблицы $Q_1$ и $Q_2$ последовательностей $\sigma_1$ и $\sigma_2$ соответственно:

Применим к таблице Юнга $Q_1$ преобразование Шютценберже:

Результат – нумерующая таблица $Q_2$ .

Преобразование Шютценберже с сохранением формы.

В данной модификации преобразования Шютценберже к преобразованной таблице $T_{n-1}$ добавляется удаленная клетка, так, что из исходной таблицы $T_n$ получается новая таблица $T^’_n$ . Очевидно, что в этом случае формы таблиц $T_n$ и $T^’_n$ будут одинаковыми.

Для преобразования Шютценберже с сохранением формы определено обратное преобразование, в котором для восстановления исходной таблицы необходимо выполнить действия преобразования в обратном порядке:

Из таблицы удаляется клетка с наибольшим значением. На ее место передвигается наибольшая по значению клетка, являющаяся соседней снизу или слева от активной.
Происходит поочередное перемещение клеток до тех пор, пока не будет достигнута клетка с координатами $(0, 0)$ .
Все значения в клетках увеличиваются на единицу.
В клетку с координатами $(0, 0)$ записывается единица.

Инкремент всех значений таблицы, производимый на третьем шаге, необходим для того, чтобы привести таблицу к стандартному виду. В противном случае таблица размера $n$ будет содержать две единицы, а максимальный элемент будет равен $n-1$ .

Применение к полученной прямым преобразованием Шютценберже таблице $T^’_n$ обратного преобразования восстанавливает исходную таблицу Юнга $T_n$ .

Циклы преобразования Шютценберже.

Поскольку преобразование Шютценберже с сохранением формы биективно, множество таблиц Юнга разбивается на циклы: полученная в результате преобразования таблица может быть снова преобразована. Другими словами, справедливы следующие утверждения:

При применении преобразования Шютценберже с сохранением формы получается новая таблица такой же формы.
Количество различных таблиц Юнга одной формы конечно.

Следовательно, при последовательном применении этого преобразования к таблицам Юнга, через конечное число шагов будет получена исходная таблица Юнга, то есть образуется цикл, длина которого равна количеству выполненных итераций преобразования Шютценберже.

Очевидно, что сумма длин всех циклов равна количеству таблиц Юнга соответствующей формы, то есть ее размерности.

Более подробный пример приведен ниже:

Пусть дана диаграмма Юнга, размерность которой равна пяти.

Список всех таблиц Юнга заданной формы:

Возьмем любую из имеющихся таблиц, вычеркнув ее из списка:

Применим к ней преобразование Шютценберже с сохранением формы:

Полученную таблицу также вычеркнем из списка:

К полученной на прошлом шаге таблице вновь применим преобразование и будем повторять этот шаг, пока не получим исходную таблицу Юнга. Получаемые таким образом таблицы также вычеркнем из списка.