>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь

24. Перестановки

Анаграммы являются известным примером перестановок:
   w=: 'STOP'
   3 2 0 1 { w
POST

   2 3 1 0 { w
OPTS

   3 0 2 1 { w
PSOT
Левые аргументы { выше, сами являются перестановками (списка i.4) ; они называются векторами перестановок, и используются для представления переставляющих функций в виде p&{ .

Если p вектор перестановки, то выражение p&C. выполняет перестановку так же как p&{ . Однако, в других случаях, функция циклы C. отличается от функции взять { . В частности, C. p дает циклическое представление перестановки p . Например:
   ]c=: C. p=: 2 4 0 1 3
+---+-----+
|2 0|4 3 1|
+---+-----+

   c C. 'ABCDE'                   C. c
CEABD                          2 4 0 1 3
Каждый упакованный элемент этого представления перечисляет список позиций, по которым происходит циклическое перемещение элементов при перестановке. В примере выше, элемент из позиции 3 перемещается в позицию 4 , элемент 1 перемещается в 3 , а элемент 4 в 1 .

Перестановке можно сопоставить ее индекс в таблице всех !n перестановок порядка n , перечисленных по возрастанию. Этот индекс называется индексом перестановки (anagram index). Соответствующую перестановку можно осуществить функцией A. , как показано ниже:
   1 A. 'ABCDE'                   A. 0 1 2 4 3
ABCED                          1

   (i.!3) A. i.3                  (i.!3) A. 'ABC'
0 1 2                          ABC
0 2 1                          ACB
1 0 2                          BAC
1 2 0                          BCA
2 0 1                          CAB
2 1 0                          CBA

Упражнения
24.1   Используйте следующее для упражнений по чтению и письму (в качестве исходных данных попробуйте a=:'abcdef' , b=: i. 6 и c=: i. 6 6):
f=: 1&A.                       Переставить два последних элемента
g=: 3&A.                       Провернуть три последних элемента
h=: 5&A.                       три последних элемента в обратном порядке
i=: <:@!@[ A. ]                k i a — последние k элементов в обр. порядке
24.2   Поэкспериментируйте со следующими (и другими подобными) выражениями, для определения правила использования сокращенных аргументов C. ; сравните свои выводы с определениями в словаре:
2 1 4 C. b=:i.6
(<2 1 4) C. b
(3 1;5 0) C. b
24.3   Напишите программу ac , производящую таблицу циклических представлений всех перестановок заданного порядка, вызываемую, например, как ac 3 .

Ответ: ac=: C.@(i.@! A. i.)




>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь