Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
f(A ∩ B) = f(A) ∩ f (B). 5.Сюръективные отображения. Пусть |X| = m, |Y | = n. Здесь мы получим две формулы — знакопере- менную и комбинаторную — для числа | Sur(X, Y )| сюръективных отобра- жений. Написать знакопеременную формулу совсем просто. 5.1. Пусть |X| = m, а |Y | = n. Докажите, что | Sur(X, Y )| = n m − n(n − 1) m + n 2 (n − 2) m − . . . + (−1) n −1 n n − 1 . Решение. Это просто формула решета, примененная к ситуации Sur(X, Y ) = Map(X, Y ) \ n [ i=1 Map(X, Y \ {y i }). А именно, первое слагаемое это общее количество всех отображений X −→ Y , равное n m . Так как каждое из множеств Y \{y i } содержит n−1 элемент, а их количество равно m, то второе слагаемое это просто сумма порядков Map(X, Y \ {y i }). Однако, при этом элементы, попавшие в их попарные пересечения, оказались выброшеными два раза, их количество нужно снова прибавить. Словом, обычное включение-исключение. Комбинаторная формула потребует некоторой подготовки. Пусть f : −→ Y — произвольное отображение. Ему можно сопоставить разбиение мно- жества X, блоками которого являются полные прообразы f −1 (y) точек y ∈ Im(f). Это разбиение называется ядром отображения f и в комби- наторике обозначается Ker(f ) или N (f ), от английского kernel или nu- cleus. Иными словами, ядро — это разбиение X, отвечающее отношению эквивалентности ∼, определенному слоями alias множествами уровня отображения f . Для этого отношения эквивалентности x 1 ∼ x 2 ⇐⇒ f (x 1 ) = f (x 2 ). В алгебре, когда рассматриваются гомоморфизмы алгебраических си- стем, ядро определяет не просто отношение эквивалентности на X, а кон- груэнцию на X. Поэтому ядро гомоморфизма полностью определя- ется заданием одного из своих блоков, обычно прообраза нейтраль- ного элемента, и в алгебре обычно именно этот блок называется ядром и обозначается Ker(X). В предыдущем пункте мы убедились, что убывающие факториалы слу- жат для перечисления инъективных отображений. А сейчас мы сможем оценить, в чем пафос чисел Стирлинга. 5.2. А теперь еще раз посчитайте, сколько существует сюръективных отоб- ражений m-элементного множества на n-элементное? 407 Ответ. Столько же, сколько упорядоченных разбиений n-элементного мно- жества на n непустых блоков, т.е. n! n m n o . В самом деле, ядро N (f ) сюръ- ективного отображения f : X −→ Y , где |X| = m, |Y | = n, представляет собой разбиение X на n штук непустых блоков. Таким образом, общее количество ядер сюръективных отображений X −→ Y равно n m n o . Од- нако, отображение не полностью определяется своим ядром. Важно еще знать, в какой элемент Y переходят элементы каждого из блоков. Ины- ми словами, чтобы полностью определить отображение f , мы должны еще установить биекцию между блоками ядра и элементами множества Y . Но, как мы знаем из предыдущего параграфа, количество биекций между дву- мя n-элементыми множествами равно n!. 5.3. Напишите программу, генерирующую все сюръективные отображения f : X −→ Y . В отличие от случая произвольных/инъективных отображений следую- щая задача не совсем очевидна — если, конечно, не делать каких-то заведо- мых глупостей типа выбора отображения со случайным номером из списка всех сюръективных отображений. 5.4. Напишите программу, генерирующую случайное сюръективное отоб- ражение f : X −→ Y . Указание. Сделать это, задавая образы элементов, совсем непросто. Про- ще всего задать случайное разбиение X на n блоков и потом случайную перестановку степени n. Имеются и другие эффективные методы сделать это, которые мы здесь не обсуждаем. 5.5. Докажите, что сюръективность отображения f : X −→ Y эквива- лентна тому, что для всех подмножеств B ⊆ Y выполняется равенство B = f (f −1 (B)). 6. Чистые и анонимные функции. 182 Большинство команд функционального программирования требуют об- ращения к функции по имени. Вот несколько примеров команд и конструк- ций, в которых необходимо упоминать имя функции. • Команды применения функции к спискам или элементам списка, ко- манды композиции и итерации такие, как Apply, Map, Fold, Nest, и многие другие. • Команды, использующие критерии такие, как Select, Sort, Split и другие • Различные конструкции такие, как PatternTest. Конечно, мы всегда можем задать имя функции при помощи конструкции f[x ]:=rhs. Однако, что если эта функция требуется нам ровно один раз в определенном контексте для применения команды функционального про- граммирования? Оправдано ли в этом случае присвоение такой функции 182 All I want is a warm bed, a kind word and unlimited power. 408 специального имени? В этом параграфе мы рассмотрим форматы чистой и анонимной функции, которые позволяют обращаться по имени к функции, у которой нет обычного имени. С математической точки зрения команда Function представляет собой реализацию операции абстрагирования λ-исчисления Черча. Эта опе- рация реализуется также в некоторых других языках программирования, в частности, в Lisp. & Function[x,y] применение чистой функции x 7→ y # Slot[] аргумент Function #n Slot[n] n-й аргумент Function ## SlotSequence[] последовательность аргументов Function ##n SlotSequence[n] последовательность аргументов, начиная с n-го Лишь очень немногие функции такие, как Cos, Log, Floor, PrimeQ или Equal, имеют специальные имена. Многие даже часто встречающиеся функции не имеют обычных имен, не включающих имени переменной. Как, например, называются функции x 7→ 1 + x 2 или x 7→ 1/(1 + x)? Так вот, при помощи команды Function можно обратиться к любой функции x 7→ f (x) в формате чистой функции Function[x,f[x]]. Тем самым, двум упомянутым выше функциям присваиваются имена Function[x,1+x^2] и Function[x,1/(1+x)]. Теперь в любом контексте мы можем обращаться к этим функциям по имени. В действительности в большинстве случаев чистые функции вызываются в операторном формате или, как принято говорить, в формате аноним- ных функций f[#]&. Дело в том, что в большинстве ситуаций не только имя функции, но и имена используемых ей аргументов не имеют никако- го значения. В реальной ситуации мы, скорее всего, назовем только что упомянутые функции (1+#^ 2)& и 1/(1+#)&. Использованный здесь оператор # = Slot, обозначает аргумент чистой функции, которому мы не хотим присваивать никакого индивидуального имени. Оператор & есть просто сокращение для Function, и обозначает применение чистой функции. Если у анонимной функции несколько аргументов, то они обозначаются #1,#2,#3 и так далее. В случае, когда Function[body] или body& при- меняется к списку аргументов, #1 заменяется первым аргументом, #2 — вторым и так далее. Мы уже много раз использовали конструкцию аноним- ной функции в конкретных ситуациях. Рассмотрим одну лингвистическую тонкость в которой мы до сих пор не встречались. Последовательность слотов ## = SlotSequence заменяет последователь- ность аргументов. Однако, при этом ##n имеет совершенно другой смысл, чем в #n. А именно, ##n обозначает последовательность всех аргументов анонимной функции, начиная с n-го. Команду SlotSequence удобно ис- пользовать для манипуляции с аргументами функции f даже в тех случаях, когда у нее уже есть имя. 409 6.1. Задайте f (y, z, x) не применяя никаких операций к последовательно- сти аргументов x, y, z. Решение. Можно f[#2,#3,#1]&[x,y,z], но лучше f[##2,#1]&[x,y,z]. 6.2. Задайте функцию f (a, . . . , z, a, . . . , z, a . . . , z) где в качестве аргумен- тов 3 раза повторяются буквы латинского алфавита. Решение. Проще всего так: f[##,##,##]&[Apply[Sequence, ToExpression[CharacterRange["a","z"]]]] 7. Композиции и итерации функций. Два отображения f и g такие, что R(f ) = D(g) можно скомпониро- вать. Точнее, пусть f : X −→ Y и g : Y −→ Z суть два отображения, область значений первого из которых совпадает с областью определения второго. Тогда их композиция g ◦ f : X −→ Z задается посредством ра- венства (g ◦ f)(x) = g(f(x)), для любого x ∈ X. При этом g ◦ f читается как композиция f и g или g кружочек f . Обратите внимание на порядок фак- торов: отображение f , действующее первым, записывается вторым. Это связано с тем, что мы пишем функцию слева от аргумента, как f (x). Ра- зумеется, если бы мы использовали обозначение (x)f , то и композиция f и g записывалась бы как f ◦ g, по формуле (x)(f ◦ g) = ((x)f)g. Самым важным свойством композиции отображений является ее ассо- циативность. А именно, если одно из выражений (h ◦ g) ◦ f и h ◦ (g ◦ f) определено, то определено и второе и при этом (h ◦ g) ◦ f = h ◦ (g ◦ f). В то же время композиция отображений весьма далека от коммутативности, иными словами, для двух отображений f и g, вообще говоря, f ◦ g 6= g ◦ f. Пусть X — любое множество. Тогда определено отображение id = id X : X −→ X такое, что x 7→ x для всех x ∈ X, называемое тождественным отображением X на себя. Обозначение id X является сокращением от ан- глийского identical. Тождественные отображения действительно ведут себя как нейтральные элементы для композиции функций, но отсутствие коммутативности накладывает свой отпечаток. А именно, для отображе- ний из Map(X, Y ) тождественное отображение id X выступает как правая единица, а id Y — как левая единица. Иными словами, для любого f ∈ Map(X, Y ) имеем f ◦ id X = f = id Y ◦f. По отношению к отображениям X в себя id X является уже двусторонней единицей. Самым важным свойством биективных отображений является то, что они обратимы. Иначе говоря, в этом случае сопоставление y 7→ f −1 (y) задает биективное отображение f −1 : Y −→ X, называемое отображением, обратным к f . Определенное так в терминах прообразов отображение f −1 действительно является обратным к f по отношению к композиции. При этом (f −1 ) −1 = f , так что в действительности f и f −1 совершенно равноправны. 410 Identity тождественная функция Composition[f,g,h] композиция функций f, g, h ComposeList[ {f,g,...},x] список {x, f(x), g(f(x)), . . . } InverseFunction[f] обратная к f функция Внутренняя функция Composition[f,g] представляет собой теоретико- множественную композицию отображений f и g. Иными словами, вычис- ление Composition[f,g][x] возвращает f[g[x]]. Функция Composition имеет две операторных записи. • Оператор @ представляет собой теоретико-множественную запись ком- позиции справа налево, когда (f@g@h)[x]===f[g[h[x]]]. • Оператор // представляет собой теоретико-категорную запись компо- зиции слева направо, когда (f//g//h)[x]===h[g[f[x]]]. 7.1. Убедитесь, что Mathematica знает тот факт, что при обращении ком- позиции двух отображений порядок факторов заменяется на противопо- ложный, (f ◦ g) −1 = g −1 ◦ f −1 Последовательное n-кратное применение отображения f : X −→ X на- зывается n-й итерацией f и обозначается f ◦n = f ◦ . . . ◦ f (отображение f применяется n раз). Согласно этому определению, f ◦0 = id X , f ◦1 = f . Команда Nest[f,x,n] вычисляет значение f ◦n (x). Вторая команда, свя- занная с итерациями функции NestList[f,x,m], генерирует список значе- ний (x, f (x), f 2 (2), . . . , f n (x)). Nest[f,x,n] вычисление f n (x) NestList[f,x,n] вычисление списка {x, f(x), . . . , f n (x) } Следующие задачи показывают, что, строго говоря, задание этих функ- ций является излишним, но в практических вычислениях итерации встре- чаются настолько часто, что удобно иметь для них специальные названия. 7.2. Выразите функцию Nest через Composition. Указание. Для этого нужно лишь создать состоящую из n членов после- довательность f, . . . , f . 7.3. Выразите функцию NestList через ComposeList. Говорят, что f : X −→ X — отображение конечного порядка, если найдется такое n ∈ N, что f ◦n = id X . Если такого натурального n не существует, то говорят, что порядок f бесконечен. 7.4. Докажите, что если f ◦n = id X , то f — биекция. 7.5. Вычислите n-ю итерацию отображения x 7→ x/ √ 1 + x 2 Ответ. x 7→ x/ √ 1 + nx 2 411 Наряду с обычными итерациями для функций от двух аргументов во многих итеративных алгоритмах широко применяется фолдинг 183 , при котором на каждом следующем шаге в функцию скармливается новое зна- чение одного из аргументов. Fold[f,x, {a,b,c}] вычисление f (f (f (x, a), b), c) FoldList[f,x, {a,b,...}] вычисление списка {x, f(x, a), f(f(x, a), b), . . . } Типичным примером функций, над которыми особенно часто произво- дится фолдинг, являются ассоциативные алгебраические операции. Напри- мер, Fold[Plus,x, {a,b,c}] дает ((x + a) + b) + c. Обратите внимание, что для неассоциативных операций при этом получается левонормированный результат. 7.6. Даст ли вычисление Fold[Plus,x, {a,b,c}] значение x a bc ? 7.7. Выразите сумму списка в терминах функции Fold. Решение. Cумма списка вычисляется посредством Apply[Plus,x]. Одна- ко, можно и так Fold[Plus,First[x],Rest[x]]. 7.8. Выразите произведение списка в терминах функции Fold. 7.9. Задайте функцию, которая в применении к тройке f , x, y, где y = {..., a, b, c} даст правонормированный результат . . . f(a, f(b, f(c, x))) . . . ). Решение. Ну, например, Fold[f[#2,#1]&,x,Reverse[y]]. 8. Траектории и неподвижные точки. All the wonders of our Universe can in effect be captured by simple rules, yet there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold. Stephen Wolfram. A New Kind of Science Пусть f : X −→ X — преобразование множества X, иными словами, отображение X в себя. Зафиксируем точку x ∈ X и будем последовательно применять f к этой точке и ее образам. Получившаяся последовательность x, f (x), f 2 (x), f 3 (x), . . . — или множество {x, f(x), f 2 (x), f 3 (x), . . . } — на- зывается траекторией точки x под действием f . Поведение траекторий функции f называется динамикой этой функции. В отличие от функции Nest[f,x,n], которая вычисляет f n (x) и на этом успокаивается, функция NestWhile[f,x,test] последовательно вычисляет x, f (x), f 2 (x), . . . , до тех пор, пока test дает значение True и возвращает первое значение f n (x), для которого тест дает значение False. Функция 183 Альтернативными названиями этой операции являются немецкое фальцовка и ла- тинское флексура. Мы остановились на английском названии, так как только оно ис- пользуется в программировании. 412 NestWhile[f,x,test] возвращает все полученные до этого момента значе- ния f i (x). NestWhile[f,x,test] вычисление f i (x), с условием test NestWhileList[f,x,test] вычисление списка {x, f(x), . . . , f i (x) } с условием test В случае, когда найдется такое n, что f n (x) = x, траектория {x, f(x), f 2 (x), . . . , f n −1 (x) } точки x называется ее орбитой 184 . Для функции на конечном множестве все траектории конечны. Отсюда легко вывести, что от каждой точки x за конечное число шагов можно дойти до такой точки y, для которой найдется такое n, что f n (y) = y. Для многих приложений особенно важен следую- щий частный случай. Точка x ∈ X такая, что f(x) = x называется непо- движной точкой отображения f . Орбита неподвижной точки состоит из единственного элемента. Функция FixedPoint[f,x] ищет неподвижную точку в траектории x под действием f , а функция FixedPointList[f,x] возвращает начало траектории до неподвижной точки. FixedPoint[f,x] решение уравнения f n (x) = f n+1 (x) FixedPointList[f,x] список {x, f(x), f 2 (x), . . . , f n (x), f n+1 (x) } до первого решения f n (x) = f n+1 (x) 8.1. Выразите функцию FixedPoint через NestWhile. Решение. Естественнее всего так: NestWhile[f,n,f[#]!=#&]. 8.2. Выразите функцию FixedPointList через NestWhileList. Рассмотрим симметризацию rev : a 1 . . . a n 7→ a 1 . . . a n + a n . . . a 1 . 8.3. Для каждого числа n ≤ 100 вычислите, сколько раз нужно применить симметризацию rev, для того, чтобы получился палиндром. 8.4. Для каждого числа n ≤ 100 найдите первый палиндром, который получается при многократном применении к нему симметризации rev. 8.5. Сопоставим натуральному числу n разность f (n) наибольшего и наи- меньшего чисел, получающихся из n перестановкой цифр. Найдите, через сколько применений f мы дойдем до цикла и какова длина этого цикла. 184 Мы не обсуждаем здесь общее понятие орбиты. В общем случае орбита обратимо- го преобразования f является объединением начинающихся с одного и того же элемента траекторий f и f −1 . Однако, орбиты необратимых преобразований определяются до- статочно сложно. 413 Расмотрите следующую арифметическую функцию: f (n) = 3n + 1, если n нечетно, n/2, если n четно. 8.6. Исследуйте динамику этой функции. Для каждого n ≤ 1000 найдите минимальное количество итераций m такое, что f m (n) = 1. 8.7. Что можно сказать об итерациях функции Эйлера ϕ : n 7→ ϕ(n)? 8.8. Зафиксируем натуральное k и рассмотрим арифметическую функцию f : n 7→ kϕ(n). Исследуйте поведение итераций f m функции f в зависимо- сти от k. Рассмотрите множество последовательностей длины n, состоящих из +1 и −1 и следующее преобразование этого множества: f : (u 1 , u 2 , . . . , u n −1 u n ) 7→ (u 1 u 2 , u 2 u 3 , . . . , u n −1 u n , u n u 1 ). 8.9. Убедитесь, что если n нечетно, а последовательность u отлична от последовательностей (+1, . . . , +1) и ( −1, . . . , −1), состоящих только из +1 или только из −1, то не существует натурального m такого, что f m (u) = u. 8.10. Убедитесь, что если n = 2 k , то для любой последовательности u существует m ≤ n такое, что f m (u) = u. 8.11. Для произвольного n найдите все последовательности длины m для которых существует натуральное m такое, что f m (u) = u. Рассмотрим множество последовательностей длины n, состоящих из на- туральных чисел и следующее преобразование этого множества: g : (x 1 , x 2 , . . . , x n −1 x n ) 7→ (|x 1 − x 2 |, |x 2 − x 3 |, . . . , |x n −1 − x n |, |x n − x 1 |). 8.12. Убедитесь, что если n = 2 k , то для любой последовательности x существует m такое, что f m (x) = (0, . . . , 0). Рассмотрите преобразование n 1 . . . n s 7→ n 3 1 + . . . + n 3 s сопоставляющее натуральному числу сумму кубов его цифр. 8.13. Найдите неподвижные точки этого отображения, меньшие 100000. Рассмотрите преобразование n 1 . . . n s 7→ n n 1 1 + . . . + n n s s сопоставляющее натуральному числу сумму степеней его цифр, причем каждая цифра возводится в степень равную ей самой. 414 8.14. Это преобразование имеет ровно одну неподвижную точку на мно- жестве натуральных чисел, кроме 1. Найдите эту точку. 8.15. Будем строить последовательность по следующему правилу. На пер- вом шаге напишем подряд две единицы. На втором шаге впишем между ними двойку. На третьем шаге впишем 3 между любыми двумя числа- ми, сумма которых равна 3. На четвертом шаге впишем 4 между любыми двумя числами, сумма которых равна 4 и т.д. Сколько раз в эту последо- вательность будет вписано число n? Ответ. Проведя несколько первых итераций, легко заметить, что это в точности последовательность знаменателей чисел Фарея, так что n вписано в нее в точности ϕ(n) раз. 9. Применение функции к элементам списка. Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом си- стемному программисту. Он исправит ошибки в трансляторе. Дональд Кнут Один из важнейших навыков грамотного программирования состоит в том, чтобы тщательнейшим образом различать • применение функции к самому списку f[{x,y,z}], • применение функции к последовательности, образованной элементами списка f[x,y,z], • применение функции к каждому элементу списка {f[x],f[y],f[z]}. Нельзя сказать, чтобы понимание этого отличия представляло какую-то трудность. Однако, выработка полного автоматизма в такого рода вещах требует длительной практики, а для вложенных списков даже самый опыт- ный пользователь при потере вигильности может легко допустить ошибку в определении уровня, на котором следует применить функцию. Вот основ- ные команды применения функции к элементам списка. Следует обратить особое внимание на отличие Map[f,x] от Apply[f,x, {1}] — такое же, как отличие f[ {x,y}] от f[x,y], но на уровне 1! f@@x Apply[f,x] применение функции к последовательности элементов списка f/@x Map[f,x] применение функции к индивидуальным элементам списка на уровне 1 f@@@x Apply[f,x, {1}] применение функции к последовательностям элементов списка на уровне 1 f//@x MapAll[f,x] применение f ко всем уровням x 9.1. Задайте функцию, превращающую список {a, b, c, . . . } в список син- глетонов {{a}, {b}, {c}, . . . }. Решение. Конечно, Map[List,x] или, что то же самое, Map[ {#}&,x]. 415 Следующая небольшая вариация на эту тему позволит нам в следую- щем параграфе дать еще одно, замечательно простое, решение задачи о генерации подмножеств. 9.2. Задайте функцию, которая превращает список {a, b, c, . . . } в список пар {{∅, {a}}, {∅, {b}}, {∅, {c}}, . . . }. 9.3. Задайте функцию, которая возводит элементы списка в квадрат. Чтобы грамотно использовать эти команды, необходимо понимать, как устроены спецификации уровня = level specification, см. [VH2] по поводу технических подробностей. По умолчанию Apply использует спецификацию уровня {0}, а Map — спецификацию уровня {1}. Од- нако, в каждой из этих команд можно факультативно задавать в качестве третьего аргумента любую легальную спецификацию уровня. Команда Ma- pAll, строго говоря, является излишней, так как она дублирует команду Map[f,x, {0,Infinity}]. 9.4. Примените функцию f к каждому элементу матрицы {{a,b},{c,d}}. Решение. Вычисление Map[f, {{a,b},{c,d}},{2}] даст правильное {{f[a],f[b]},{f[c],f[d]}}. Для сравнения укажем, что вычисление Map[f, {{a,b},{c,d}}] без явного указания уровня применит f не на втором, а на первом уровне, {f[{a,b}],f[{c,d}]}. При неправильном указании уровня Map[f, {{a,b},{c,d}},2] — или, что то же самое, Map[f, {{a,b},{c,d}},{1,2}] — команда Map применит f как на первом, так и на втором уровне, {f[{f[a],f[b]}],f[{f[c],f[d]}]}. 9.5. Задайте функцию, возвращающую среднее арифметическое x 1 + . . . + x n n элементов списка. Решение. Ну, конечно, так mean[x ]:=Apply[Plus,x]/Length[x] 9.6. Задайте функцию, возвращающую среднее геометрическое n √ x 1 . . . x n элементов списка. 9.7. Задайте функцию, возвращающую среднее гармоническое n 1 x 1 + . . . + 1 x n элементов списка. 416 Во многих случаях необходимо применить функцию не ко всем элемен- там списка, а только к элементам, находящимся в определенных позициях. Этому служат команды селективного применение функции к элементам списка MapAt и MapIndexed. MapAt[f,x,i] применение f к i-й части x MapAt[f,x, {i,j}] применение f к (i, j)-й компоненте x MapAt[f,x, {{i},{j}}] применение f к i-й и j-й частям x MapIndexed[f,x] применение функции к парам, состоящим из части списка и ее адреса Команда MapAt действует так же, как Map, но при этом применяет функ- цию f только к частям или компонентам списка, находящимся на указан- ных позициях. Для вложенных списков MapAt использует те же соглашения относительно адресации частей, что и команды Extract, Delete, Insert и ReplacePart. Отметим, что команда MapIndexed особенно удобна при ра- боте с матрицами. 9.8. Задайте функцию, применяюшую f к первому элементу списка. 9.9. Задайте функцию, применяюшую f к последнему элементу списка. 9.10. Задайте функцию, применяюшую f к последнему элементу первого элемента списка. 9.11. Задайте функцию, возводящую в квадрат элементы списка на местах с нечетными номерами. 9.12. Задайте функцию, меняющую знак у элементов списка на местах с четными номерами. 9.13. Задайте функцию, заменяющую на 0 элементы списка на местах с нечетными номерами. 9.14. Задайте функцию, заменяющую на 1 элементы списка на местах с четными номерами. Совершенно замечательно, что среди адресов в команде MapAt могут быть повторяющиеся. В этом случае функция f будет многократно приме- няться к одному и тому же элементу. 9.15. Задайте функцию два раза применяющую f ко второму элементу списка. Решение. Например, так Map[f,x, {{2},{2}}]. 417 10. Применение функции к элементам нескольких списков. Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом си- стемному программисту. Он исправит ошибки в трансляторе. Дональд Кнут To tell between Murphy's and Guinness is sure not a task for beguin- ness. Еще более суровые засады сулит начинающему применение функций нескольких переменных к элементам нескольких списков. В настоящем пункте мы лишь совсем коротко рассмотрим основные команды распреде- ления и протаскивания функции через списки. Основные команды распределения Outer и Distribute уже встреча- лись нам при обсуждении прямых произведений. Область их применения гораздо шире, они могут производить распределение по любому заголовку, но нас здесь интересует только распределение по спискам. Распределение состоит в том, чтобы применить f ко всем парам (a, b), первый элемент которых берется из первого списка, а второй — из второго, организовав результат в виде списка, возможно вложенного. Outer[f,x,y] распределить f по компонентам списков x и y на самом глубоком уровне Outer[f,x,y,n] распределить f по компонентам списков x и y на уровне n Distribute[f[x],List] распределить f по входящим в x спискам Важнейшей синтаксической особенностью функции Outer является то, что по умолчанию она действует не на верхнем уровне, как подавляющее большинство функций работы со списками, а, наоборот, на самом глубоком уровне выражения. Это значит, что для вложенных списков она всегда дает не тот результат, который ожидает начинающий. Функция Distribute имеет один аргумент, а именно, само выражение, и четыре параметра. Ее полный формат таков: Distribute[x,g,f,gg,ff] При вызове Distribute в таком формате происходит следующее: функ- ция g распределяется по тем компонентам выражения x, которые имеют заголовок f и в получившемся выражении f заменяется на ff , а g на gg. 10.1. А теперь напишите однострочную команду, генерирующую все под- множества множества X. Решение. Вот феерическое решение из книги Вольфрама: subsets[x ]:=Distribute[Map[ {{},{#}}&,x],List,List,List,Join] Так как первая часть этой команды, перерабатывающая список {a, b, c} в список пар {{∅, {a}}, {∅, {b}}, {∅, {c}}} уже встречалась нам в предыдущем параграфе, то все дело здесь в выборе параметров команды Distribute!!! 418 Это блестящий пример концептуального программирования, осно- ванного на полном контроле над тем, что происходит при вычис- лении, с точки зрения математики! Мы, конечно, далеки от мысли, что нам удастся в течение полугода научить студента, который до этого никогда серьезно не занимался вычислениями, программировать в таком стиле — и, собственно говоря, не ставим такой цели. 10.2. Скажите, не включая компьютера, что проиойдет, если переставить в решении предыдущей задачи два последних параметра местами? Что, например, дает вычисление Distribute[Map[ {{},{#}}&,{a,b}],List,List,Join]? 10.3. Скажите, не включая компьютера, что произойдет, если заменить в том же решении предпоследний параметр на Join? Что, например, дает вычисление Distribute[Map[ {{},{#}}&,{a,b}],List,List,Join,Join]? Как мы знаем из параграфа, посвященного прямым произведениям, с помощью команды Outer, если следить в ней за уровнем и производить выравнивания ответа, обычно удается добиться того же результата, что с помощью команды Distribute. 10.4. Напишите основанную на той же идее программу генерации подмно- жеств, использующую Outer вместо Distribute. Указание. Во-первых, Distribute распределяется через любое количе- ство списков, а Outer — только через два, поэтому необходимо применить фолдинг. Во-вторых, чтобы получить правильный ответ для вложенных списков, Outer нужно применять только к элементам списков на уровне 1. В-третьих, Outer создает список с дополнительным уровнем вложенности, который необходимо убрать. Решение. Конечно, с учетом всех упомянутых лингвистических особен- ностей решение, использующее Outer, чуть сложнее решения с Distribute, но все равно более, чем убедительно: subsets[x ]:=Fold[Flatten[Outer[Join,#1,#2,1],1]&, {{},{First[x]}},Map[{{},{#}}&,Rest[x]]] А вот основные команды протаскивания, Inner, Thread и MapThread. Протаскивание состоит в том, чтобы продеть f через два списка одинако- вой длины применив f ко всем парам вида (a i , b i ), компоненты которых находятся на позициях с одинаковыми номерами. Inner[f,x,y,g] протащить f через списки x и y, заменив заголовок на g Thread[f[x,y]] протащить f через списки x и y MapThread[f,x] протащить f через входящие в x списки Различие между Thread и MapThread не математическое, а чисто синтак- сическое. Как вычисление 419 Thread[f[ {a,b,c},{x,y,z}]] так и вычисление MapThread[f, {{a,b,c},{x,y,z}}] возвращает {f[a,x],f[b,y],f[c,z]} 10.5. Определите функцию Thread в терминах других функций примене- ния функций к элементам списков. Решение. Вот несколько совсем очевидных решений, которые работают для линейных списков: Apply[f,Transpose[ {{a,b,c},{x,y,z}}],1] Inner[f, {a,b,c},{x,y,z},List] Tr[Outer[f, {a,b,c},{x,y,z}],List] Еще одно напрашивающееся решение Map[f,Transpose[ {{a,b,c},{x,y,z}}]] приводит к синтаксической ошибке {f[{a,x}],f[{b,y}],f[{c,z}] Однако, стоит ввести вспомогательную функцию ff[ {x ,y }]:=f[x,y], принимающую в качестве аргумента список аргументов функции f , как оно становится правильным: Map[ff,Transpose[ {{a,b,c},{x,y,z}}]] Получить столь же ясные и естественные решения для вложенных спис- ков совсем не так просто!!! Дело в том, что между тем, как применяются к вложенным спискам команды Inner и Outer с одной стороны, и тем, как действуют Thread и MapThread, имеется принципиальное различие. Дело в том, что по умолчанию Inner и Outer применяется на нижнем уровне, а Thread и MapThread — на верхнем уровне. 10.6. Задайте функцию, которая проверяет, что каждый элемент списка x содержится в соответствующем элементе списка y. Решение. Единственная команда, при помощи которой эта задача реша- ется без дальнейших хлопот это MapThread: Apply[And,MapThread[MemberQ, {y,x}]] Распределить действие функционального символа f при помощи команды Thread тоже совсем просто. Вычисление Thread[f[ {{a,b},{c,d}},{u,v}]] возвращает нужный нам промежуточный результат {f[{a,b},u],f[{c,d},v]}. 420 Проблема состоит в том, что если подставить сюда вместо f функцию с вы- соким приоритетом такую, как MemberQ, система попытается эвалюировать еще до того, как применит Thread, что, естественно, приведет к совершенно бессмысленному ответу. Именно для борьбы с такими явлениями в системе предусмотрены команды удерживания = подмораживания, которые не дают провести эвалюацию функций, до тех пор, пока удерживание не бу- дет снято соответствующей командой освобождения. В данной ситуации проще всего воспользоваться общим удерживанием Hold и освобождением Release = ReleaseHold, примерно так: ReleaseHold[Thread[Hold[MemberQ][y,x]]] Теперь уже, конечно, ясно, как добиться требуемого эффекта с помощью Inner, для этого нужно подморозить не только эвалюацию MemberQ, но и все подмножества, входящие в состав второго списка, чтобы команда Inner не вникала в их внутреннюю структуру, и освободить их только после протаскивания Hold[MemberQ]. Это можно сделать так: ReleaseHold[Inner[Hold[MemberQ],Map[Hold,y],x,List]] Ясно, что подобный текст находится за пределами того, что разумно тре- бовать от начинающего. Более того, даже в книге Вольфрама в этом месте допущена ошибка, так как определенная там в терминах функции Inner функция cartesianInclude, решающая следующую задачу, работать не может — и не работает. 10.7. Дано множество X состоящее из упорядоченных n-ок и список мно- жеств Y 1 , . . . , Y n . Задайте функцию, которая выбирает те элементы X, которые лежат в прямом произведении Y 1 × . . . × Y n Решение. Проще всего при помощи MapThread: cartesianInclude[x ,y ]:=Select[x,Apply[And, MapThread[MemberQ, {y,#}]]&] 10.8. Задайте функцию, которая по любому списку x длины n и списку натуральных чисел y длины n строит список той же длины, i-й частью которого является список, состоящий из повторенного y i раз элемента x i Решение. Если список невложенный, то хотя бы так: Inner[Table[#1, {#2}]&,x,y,List] А теперь измените этот текст таким образом, чтобы получающаяся команда правильно работала для вложенных списков — а лучше замените Inner на MapThread. 10.9. Задайте функцию, которая строит список элементов мультимноже- ства по его носителю и списку кратностей. Vail's Second Axiom: The amount of work to be done increases in proportion to the amount of work already completed. 421 § 4. Перестановки Аз есмь Алфа и Омега, начало и конец, первый и последний. Откровение Святого Иоанна Богослова, Глава 22–13 Двадцать две основные буквы: Бог их нарисовал, высек в камне, соединил, взвесил, переставил и создал из них все, что есть, — и все, что будет. Сефер Йецира Some of the particulars recommended by Abulafia contributed to the aura of magic surrounding Kabbalah: the best hour for meditative permutations (known as tzeruf) was midnight. The meditator was to light many candles, wear phylacteries and a prayer shawl, and write out the permutations of the alphabet with ever increasing speed. The resulting ecstatic state accompanied by the desire of the soul to leave the body could be so powerful that there was even the possibility of death. At the peak of ecstatic experience there would be a rush of unintelligible language and the kabbalist had to envision a surrounding circle of angels who could help to decipher the divine message. It was the sheer force of the letters themselves which brought forth the meaning , since the only link between the Sephirot of non-verbal Wisdom and verbal Intelligence was through the letters of the alphabet. Johanna Drucker, The Alphabetic Labyrinth 185 В русском алфавите, как известно, букв намного больше, чем в древнееврейском, так что возможности для практической кабба- листики открываются самые широкие. Виктор Пелевин, ГКЧП как тетраграмматон Этот параграф содержит введение в практическую каббалистику. А именно, здесь мы изучаем симметрическую группу, состоящую из всех пе- рестановок n-элементного множества. В частности, читатель без труда смо- жет повторить все основные результаты каббалистов, относящиеся к группе S 22 . Среди алгебраистов широко распространено убеждение, что комбина- торика является разделом теории групп и что вообще не существует ни- какой комбинаторики, кроме комбинаторики симметрической группы 186 Однако, даже те кто не готов встать на столь радикальную точку зрения, согласятся с тем, что изучение симметрической группы представляет собой важнейшую часть комбинаторики и естественно возникает всюду в мате- матике и ее приложениях — теория перечисления, теория кодирования, задачи сортировки, дискретная оптимизация, etc., etc., etc. 1. Запись перестановки. 187 185 J.Drucker, The Alphabetic Labyrinth: The Letters in History and Imagination. — Thames and Hudson, London, 1995. 186 На самом деле, конечно, комбинаторики групп Вейля. 187 Vidi, Vici, Veni. c Giulio Cesare 422 Напомним, что перестановкой степени n называется биекция множе- ства n = {1, . . . , n} на себя. Множество всех перестановок степени n назы- вается симметрической группой степени n и обозначается через S n Permutations[Range[n]] симметрическая группа степени n Чаще всего перестановки изображаются двумя строками следующим об- разом. В первой строке перечисляются элементы множества n в каком-то — например, в естественном — порядке, а во второй строке под каждым элементом записывается его образ под действием перестановки. Пусть, например, π — перестановка, переводящая j в π(j) = i j . Тогда пишут π = 1 . . . n i 1 . . . i n — это так называемая полная или развернутая за- пись перестановки π. Например, тождественная перестановка может быит записана как id = 1 . . . n 1 . . . n Ясно, что если элементы множества n приведены в естественном по- рядке, то при этом π вполне определяется своей второй строкой и иногда пишут просто π = (i 1 , . . . , i n ), это так называемая сокращенная запись перестановки. Специалисты в области комбинаторики и теории групп не любят пользоваться сокращенной записью, из-за конфликта с обозначе- нием циклов. Однако, в программировании обычно удобнее пользоваться сокращенной записью, а разложение на циклы задавать вложенным спис- ком. Для примера перечислим все элементы симметрической группы S 3 сте- пени 3 в полной записи: 1 2 3 1 2 3 , 1 2 3 1 3 2 , 1 2 3 2 1 3 , 1 2 3 2 3 1 , 1 2 3 3 1 2 , 1 2 3 3 2 1 . и все элементы симметрической группы S 4 степени 4 в сокращенной записи: (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) (2 1 3 4) (2 1 4 3) (2 3 1 4) (2 3 4 1) (2 4 1 3) (2 4 3 1) (3 1 2 4) (3 1 4 2) (3 2 1 4) (3 2 4 1) (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 1 3 2) (4 2 1 3) (4 2 3 1) (4 3 1 2) (4 3 2 1) Преимущество развернутой записи состоит в том, что при этом не нужно требовать, чтобы элементы первой строки стояли в естественном порядке, что особенно удобно при образовании обратной перестановки. Иными сло- вами, если j 1 , . . . , j n — любое расположение чисел 1, . . . , n, и π(j h ) = k h , то перестановка π может быть записана и как π = j 1 . . . j n k 1 . . . k n . Например, 1 2 3 4 3 1 4 2 = 4 2 1 3 2 1 3 4 . 423 Таким образом, каждая перестановка степени n имеет ровно n! различных полных записей. В соответствии с только что сказанным, мы будем записывать переста- новку π одним из трех следующих образов: • сокращенная запись {i1,...,in}; • полная запись {{j1,...,jn},{k1,...,kn}}; • табличная запись {{j1,k1},...,{jn,kn}}. Переход от полной записи к табличной и наоборот осуществляется внут- ренней командой Transpose. 1.1. Напишите команды, осуществляющие переход от полной записи пере- становки к сокращенной и наоборот. Решение. Перейти от сокращенной записи x к полной совсем просто, нужно лишь предварить сокращенную запись x списком 1, . . . , n нужной длины: {Range[Length[x]],x} Получить сокращенную запись из полной чуть сложнее, так как для этого нужно прежде всего отсортировать первую строку. Проще всего это дела- ется так: мы переходим от полной записи к табличной, сортируем пары (по умолчанию сортировка пар начинается с сортировки по первому элементу) и снова возвращаемся к полной записи. Однако, теперь первая строка от- сортирована и отбрасывая ее мы получаем сокращенную запись: Last[Transpose[Sort[Transpose[x]]]] 1.2. Напишите команду, порождающую по сокращенной записи переста- новки список всех ее полных записей. Указание. Можно использовать внутреннюю команду Permutations. Еще раз подчеркнем, что в большинстве ситуаций программисты рассматрива- ет именно сокращенную запись перестановки как основную. Например, команда Permutations[list] порождает все перестановки списка list в сокращенной записи. 1.3. Породите случайную перестановку степени n. Решение. Наивное решение состоит в том, чтобы породить симметриче- скую группу степени n и выбрать в ней случайный элемент: Permutations[Range[n]][[Random[Integer, {1,n!}]]] Однако, уже для n = 12 порождение всех 12! = 479001600 перестановок только для того, чтобы выбрать из них одну, представляет собой в высшей степени сомнительное предприятие. В 1990 году Джо Кристи в пакете SymmetricGroup 188 предложил сле- дующее изумительное решение, поражающее воображение сочетанием бру- тальности и изящества: 188 В настоящее время этот пакет в основном включен в стандартный пакет Combina- torica, входящий в поставку системы. 424 RandomPermutation[n]:=Block[ {xxx}, xxx=Table[ {Random[],i},{i,1,n}]; Last[Transpose[Sort[xxx]]]] Здесь происходит следующее. Прежде всего, генерируется список пар, со- стоящих из случайного вещественного числа в интервале (0, 1), с машин- ной точностью, и номера i = 1, . . . , n. После этого список сортирует- ся — вспомним, что по умолчанию сортировка производится по первому (случайному!) элементу. В результате этого вторые элементы пар окажут- ся случайным образом переставлены. Вероятность того, что два числа, порожденных командой Random[], совпадут, равна примерно 10 −16 и для всех практических целей ею можно пренебречь. Порождение перестанов- ки степени 10 6 при помощи этой процедуры занимает примерно столько же времени, как выбор перестановки из списка всех перестановок степени 10. Иногда используется еще одна запись перестановки, матричная за- пись. При этом каждой перестановке степени n сопоставляется ортого- нальная матрица степени n, состоящая из 0 и 1. А именно, для перестанов- ки π ∈ S n обозначим через (π) матрицу перестановки, элемент которой в позиции (i, j) равен δ i,π(j) Изобразим для примера матрицы перестановки степени 3: 1 0 0 0 1 0 0 0 1 , 1 0 0 0 0 1 0 1 0 , 0 1 0 1 0 0 0 0 1 , 0 0 1 1 0 0 0 1 0 , 0 1 0 0 0 1 1 0 0 , 0 0 1 0 1 0 1 0 0 , Мы можем записывать перестановку задавая соответствующую матрицу перестановки — эта запись называется матричной записью перестанов- ки. Например, матричная запись перестановки (5, 4, 3, 1, 2) равна {{0,0,1,0,0},{0,0,0,1,0},{1,0,0,0,0},{0,1,0,0,0},{0,0,0,0,1}} 1.4. Напишите команду, порождающую по сокращенной записи переста- новки ее матричную запись. 1.5. Напишите команду, порождающую по матричной записи перестановки ее сокращенную запись. 2. Алгебра перестановок. В полной записи обратная перестановка получается просто перестанов- кой первой и второй строк, иными словами, применением функции Reverse. 2.1. Напишите команду, вычисляющую обратную перестановку по сокра- щенной записи исходной перестановки. Ответ. Проще всего приписать к сокращенной записи исходной переста- новки список нужной длины, только не в начале, а в конце: {x,Range[Length[x]]}. 425 2.2. Напишите команду, вычисляющую сокращенную запись обратной пе- рестановки по сокращенной записи исходной перестановки. Ответ. Вообще-то, для перестановок начального отрезка натурального ря- да это просто внутренняя функция Ordering, которая как раз и возвращает список, состоящий из позиций последовательных натуральных чисел в ис- ходном списке. В общем случае естественнее всего при помощи двойного применения Transpose. А именно, для получения полной записи обратной перестановки достаточно приписать к исходной перестановке единичную перестановку. Чтобы перейти отсюда к обычной (сокращенной) записи можно поступить так: транспонировать полную запись, отсортировать ее по первому элемен- ту, после чего снова транспонировать. При этом получится полная запись обратной перестановки с упорядоченной первой строкой. Чтобы получить из нее сокращенную запись обратной перестановки, достаточно отбросить в получившейся записи первую строку. В коде это выглядит так: inv[x ]:=Last[Transpose[Sort[Transpose[ {x,Range[Length[x]]}]]]] Впрочем, вместо второго применения Transpose можно просто применить Last к каждому элементу inv[x ]:=Map[Last,Sort[Transpose[ {x,Range[Length[x]]}]]] Произведение перестановок определяется как композиция отобра- жений. В приведенных обозначениях умножение двух перестановок σ и π осуществляется так: нужно записать первую строку σ как вторую строку π, тогда σπ — это перестановка, первая строка которой совпадает с первой строкой π, а вторая строка — со второй строкой σ в этой новой записи. Пусть, например, σ = 1 2 3 4 5 4 2 1 5 3 , π = 1 2 3 4 5 5 1 2 4 3 , переписывая σ в виде σ = 5 1 2 4 3 3 4 2 1 5 , получим σπ = 1 2 3 4 5 3 4 2 1 5 . Обратите внимание, что перестановки умножаются как отображения, а именно, справа налево: первой действует правая перестановка, а потом левая. 2.3. Напишите команду, вычисляющую произведение перестановок в со- кращенной записи. Ответ. Пусть x и y — две перестановки в сокращенной записи. Тогда x[[y]] — сокращенная запись их произведения. 2.4. Напишите команду, вычисляющую произведение перестановок в пол- ной записи. 426 2.5. Напишите команду, вычисляющую произведение перестановок в таб- личной записи. 2.6. Убедитесь, что матричная запись согласована с алгеброй перестано- вок, иными словами, умножению перестановок отвечает умножение мат- риц, а обратная перестановка переходит в обратную — или, что в данном случае то же самое, транспонированную — матрицу. В этом случае математик сказал бы, что отображение, сопоставляющее перестановку матрицу перестановки, является гомоморфизмом: (σπ) = (σ)(π). 3. Генерация перестановок. 189 В этом и следующих разделах мы изучим несколько способов постро- ить — или, как говорят программисты, сгенерировать — все перестановки степени n. Чаще всего для этого используется рекурсия, т.е. список пере- становок степени n строится на основе списка перестановок степени n − 1. 3.1. Напишите код, который порождает все перестановки степени n. Ответ. Можно воспользоваться рекурсией. Если мы уже породили все перестановки степени n − 1, то перестановки степени n получаются врисо- выванием n в каждую из них на все позиции с первой по n-ю, или, как мы это делаем ниже, с n-й по первую: perm[1]= {{1}}; perm[n ]:=perm[n]=Flatten[Outer[Insert[#1,n,#2]&, perm[n-1],Reverse[Range[n]],1],1] Индукцию можно начинать и с n = 0, положив perm[0]= {{}}. Конечно, на языке Mathematica существуют десятки (сотни?) способов выразить ту же самую мысль. Вот еще один, при котором перестановка степени n − 1 разбивается на начальную и конечную часть, может быть пустые, между которыми вставляется n: permbis[1]= {{1}}; permbis[n ]:=permbis[n]=Flatten[Map[ ReplaceList[#, {x ,y }->{x,n,y}]&,permbis[n-1]],1] 3.2. Напишите программу, которая порождает все перестановки элементов списка list. Ответ. Точно так же, как в предыдущей задаче: permut[ {x }]:={{x}}; permut[list ]:=Flatten[Outer[Insert[#1,Last[list],#2]&, permut[Most[list]],Reverse[Range[Length[list]]],1],1] В книге Кнута описан другой алгоритм генерации перестановок степени n. Этот алгоритм столь же прост для реализации, хотя придумать его, пожалуй, несколько труднее. А именно, допишем к каждой перестановке степени n − 1 полуцелые числа 1 2 , 3 2 , 5 2 , . . . , n − 1 2 . Например, из переста- новки (213) степени 3 получаются четыре списка (213 1 2 ), (213 3 2 ), (213 5 2 ), 189 I have the simplest tastes. I am always satisfied with the best. c Oscar Wilde 427 (213 7 2 ). После этого заменим элементы каждого из списков list числа- ми 1, 2, . . . , n сохраняя порядок. Однако, в действительности чуть проще реализовать версию этого алгоритма, в которой на последнем шаге проде- лывается обратная процедура, а именно, каждый список list заменяется на список позиций в list на которых появляются элементы Sort[list]. Дело в том, что при этом можно воспользоваться внутренней функцией Ordering 3.3. Напишите программу, которая реализует этот алгоритм генерации перестановок степени n. Ответ. Как и в первой задаче этого параграфа, проще всего воспользо- ваться командой Outer, примененной на уровне 1, для того, чтобы дописать поочередно к каждой перестановке степени n − 1 последовательно каждый из элементов списка { 1 2 , 3 2 , 5 2 , . . . , n − 1 2 } и указать позиции элементов полу- чившегося списка в порядке возрастания: perm[1]:= {{1}} perm[n ]:=Flatten[Outer[Ordering[Join[#1, {#2}]]&, perm[n-1],1/2+Range[0,n-1],1],1] 3.4. А теперь напишите программу, которая реализует этот алгоритм ге- нерации перестановок степени n в исходной редакции. Ответ. Нужно лишь дописать в предыдущем коде inv поверх Ordering. А вот еще одна литературная обработка той же самой идеи. Зафикси- руем перестановку степени n − 1 и какое-то число m, 1 ≤ m ≤ n. А теперь прибавим 1 ко всем числам в исходной перестановке, которые ≥ m. При этом получится перестановка чисел 1, . . . m −1, m+1, . . . , n и дописав к ней m мы получим перестановку степени n. 3.5. Напишите программу, которая реализует эту версию алгоритма гене- рации перестановок степени n. Указание. Проще всего отдельно определить функцию edit[x,m], кото- рая проделывает с перестановкой x степени n − 1 описанное выше преоб- разование, а потом, как всегда, применить эту функцию к элементам двух списков посредством Outer. 4. Генерация перестановок в лексикографическом порядке. 190 Внутренняя команда Permutations генерирует перестановки в лекси- кографическом порядке. Например, вычисление Permutations[3] воз- вращает (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1). В то же время, описанная в предыдущем параграфе функция perm порож- дает перестановки в другом порядке. Например, perm[3] даст (1 2 3), (1 3 2), (3 1 2), (2 1 3), (2 3 1), (3 2 1). 190 Те же тестикулы, но в ортогональной проекции . . . c Николай Фоменко |