11.Перестановки
Совокупность всех взаимно однозначных отображений множества М, состоящего из n элементов, на себя образует группу, которая называется симметрической группой и обозначается через Sn . Элементы группы Sn называются перестановками. Элементы множества М называются символами, и обозначают их либо буквами, либо цифрами.
Будем считать, что элементы множества М являются символами в смысле языка рефал.
Пусть f - элемент Sn , т.е. f отображает М на себя. Тогда перестановку f будем представлять в поле зрения в виде последовательности из n скобок вида (х f(x)),где х - элемент множества М.
Перестановки перемножаются в соответствии с общим правилом композиции отображений:
(fg)(x) = f( g(x) )
Напишем функцию УМН умножения двух перестановок. Формат обращения :
<УМН (e.f) e.g >
где e.f, e.g - перестановки.
УМН { (e.1 (s.B s.C) e.2) (s.A s.B) e.3 = (s.A s.C) <УМН (e.1 e.2) e.3>;
( ) = ; }
Объясните, почему скобки (s.B s.C) и (s.A s.B) можно вообще выбрасывать?
Обратная перестановка имеет вид (f(x) x), поэтому функция обращения перестановки ОБР записывается так:
ОБР { (s.A s.B) e.1 = (s.B s.A) <ОБР e.1> ;
= ; }
Для каждой перестановки вводится понятие четности. Напишем функцию ЧЕТ, которая по перестановке выдает в качестве результата замены "0", если перестановка четная, и "1", если нечетная.
ЧЕТ { e.1 = <ЧЕТ1 '0' e.1>; } ЧЕТ1 { s.A (s.B s.B) e.1 = <ЧЕТ1 s.A e.1>; s.A (s.B s.C) e.1 (s.D s.B) e.2 = <ЧЕТ1 <ИЗМЧЕТ s.A> e.1 (s.D s.C) e.2>; s.A = s.A; } ИЗМЧЕТ { '0' = '1' ; '1' = '0' ; }
П Р И М Е Р. Рассмотрим известную игру в "пятнадцать" (см. например, [4], гл.4, п.2). В этой игре требуется от расположения фишек
f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
перейти к правильному расположению
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
С задачей ассоциируется перестановка f из группы S15 , действующая по формуле f(i) = fi. Переход в правильное расположение возможен, если перестановка f - четная.
Написать функцию ИГРА15, которая получает в качестве аргумента 15 чисел f1, f2, ... ,f15, перечисленных через запятую, и результатом замены которой является "1", если правильное расположение достижимо, и "0", если не достижимо.
Р Е Ш Е Н И Е. Сначала строим перестановку функцией ИГРА15А, затем функция ЧЕТ определяет четность перестановки, а функция ИЗМЧЕТ заменяет нули на единицы.
ИГРА15 { e.1 = <ИЗМЧЕТ <ЧЕТ <ИГРА15А 1 e.1 >>>; } ИГРА15А { s.A e.1 ',' e.2 = (s.A <NUMB e.1>) <ИГРА15А <ADD (s.A) 1> e.2>; s.A e.1 = (s.A <NUMB e.1>); }
Числа от 1 до 15 представляются макроцифрами.
З А Д А Ч А. В предыдущем примере предполагается, что пустая клетка находится в правом нижнем углу. Обозначив пустую клетку числом 16, мы получаем перестановку из группы S16. Написать функцию определения возможности перехода в правильное расположение, если начальное расположение задается шестнадцатью числами, перечисленными через запятую.
З А Д А Ч А. Имеется другой способ записи перестановок - в виде произведения циклов. Например, перестановка (1,2)(2,3)(3,1)(4,5)(5,4) записывается как (1 2 3)(4 5). Написать функции УМН, ОБР, ЧЕТ, работающие с перестановками, записанными в виде циклов.