index , prev , next

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). Написать функции УМН, ОБР, ЧЕТ, работающие с перестановками, записанными в виде циклов.

index , prev , next