Посмотрев на фильтр Регуляр, мы видим, что он отвергает комбинацию 3, потому что f2 гарантирует, что п отображается на некоторый х1 из Х1-0браз (fl), тогда как f5 означает, что на х1 будет отображен некоторый п из Л, причем п < п, тогда как -(д:1)< -(д:/). Аналогично второй фильтр Регуляр отвергает комбинацию 4, и остаются только 1 и 2.

Здесь мы видим природу нового определения, введенного для Слияния в уравнениях (5) и (6) в разд. 5.3.1. Добавление дополнительного фильтра Регуляр в определении Перест в точности эквивалентно невключению этих комбинаций в декартово произведение. У нас нет необходимости исключительно в целях синтеза давать точное определение Регуляр, как мы делали это В уравнении 5.3.1(6). Вместо этого мы могли бы произвольно решить не включать эти комбинации и определить Регуляр как первоначально неопределенный фильтр, задаваемый этими опу. щениями. Очень похожее явление можно наблюдать при синтезе Сортировки Взбалтыванием и Сортировки Обменом в разд. 5.4.1.

Кроме ТОГО, теперь мы можем дать некоторое обоснование уравнению (7). Перест (Х) требует, чтобы каждый элемент X появлялся в первой позиции некоторого массива. Фильтр Регуляр гарантирует, что в первых позициях Слияния! {{nlxl} -\- fj, <,п2х2}+12, п + N) могут появиться только xl и х2 и, поэтому,

Теперь нужно исследовать, какая комбинация f\ выдержит все три фильтра. Будет проще, если мы представим это в виде таблицы. В приведенной здесь таблице строка с галочкой в / -й позиции означает, что все остальные f[ должны быть Ф, чтобы вся комбинация [] / прошла через рассматриваемый

фильтр.

Сначала рассмотрим фильтр Биект, который гарантирует нам, что составное отношение тотально на всей Области и Образе и задает функцию. Эти соображения дают нам право утверждать, что фильтр Биект пропускает лишь следующие комбинации:

чтобы убедиться, что каждый элемент Х1\}Х2 имеет шанс попасть в первую позицию, для Перест (XJIJХ2) мы должны рассмотреть все е Перест{XI) и все /2е Перест{Х2). Таким образом, «выживут» только два выражения

Cl = {nxl)-]-f6[jf7[jf8

где f6sNX XI, frsNX {х2}, fSs N X Х2

C2 = {nx2) + f5\]f6\}f8

где fSNX {xl), feNX XI, f8 NXX2.

и мы можем перекомбинировать декартово произведение, так что

Cl = {nxl) + fl где flNX{x2 + Xl{]X2) С2 = {пх2) + f2 где f2 N Х{х1 + X1U Х2).

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

Биект {{nxl) -{-fln + N, xl-]-Xl[jx2 + Х2) Биект {fl, N, Xl{jx2-\-X2) Регуляр {{nxl) -f fl, {nlxl) + fl) Регуляр {fl, fl) Регуляр {{nxl) + fl, {п2х2) + f2)

Регуляр {fl, {n2x2) + f2) Биект i{nx2) + f2, n + N, xl -\-XI \J x2-\- X2, < Биект {f2, N,xl-{-Xl\j X2) Регуляр {{nx2) + f2, {nlxl) + fl)

Регуляр{f2, {nlxl) + fl) Регуляр {{nx2) + f2, {п2х2) + f2) <=Регуляр{12, f2).

Таким образом, можно переписать

Слияние! {{nlxl) + , {п2х2) + f2,n + N)

{{nxl) + fl\fl sNXx2 + XlUX2 и Биект {fl, N, x2 + Xl[jX2) и Peгyляp{f}, fl) и Регуляр {fl, {n2x2) + f2)} и {{nx2)-{-f2\f2NXxl + Xl\]X2 и Биект{f2, N, xl+Xl\}X2) и Регуляр {f2, {nlxl)-\-fl) и Регуляр Q2, f2)}.

Вспомнив, что XI - Образ if 1), а Х2 = Образ{12), правую часть можно переписать в виде

{{nxl) -]-fr\flsNX Образ ifl) и Образ {{п2х2) + f2)

и Биект ifl, N, Образ (fl) [] Образ {{п2х2) + f2)) и Регуляр ifl, fl) и Регуляр ifl, {n2x2) + f2} и {{пх2) + f2 \f2sNX Образ ({nlxl) -f ) U Образ {f2)

и Биект if 2, N, Образ {{nix 1)-\-fl) [j Образ (f 2)) и Регуляр {f2, {nlxl)-\-fl) и Регуляр if 2, f2)}

6.5. Имеем

Сорт {X1[]X2)- и Упоряд (Слияние (fl, f2))

и Перест (XI) f2e Перест iX2)

Для свертки с 5.3.2(1) перепишем это как

ч= и Упоряд (Сяuянue(fl, f2)).

tl е Упоряд {Перест {XI)) f2 е Упоряд (Перест (Х2))

Легко видеть, что эта запись законна. Надо лишь показать, что для любой е Перест (XI) я fl ф Упоряд (Перест (XI)) или f2nepecT(X2) и f2 Упоряд(Перест(Х2)), Упоряд(Слия-Hue(fl, f))= Ф.

Но это очевидно, если мы вспомним, что фильтр Регуляр гарантирует, что Слияние не нарушает внутренний порядок или f2, и поэтому если fl или /2 не упорядочены, то и Слияние (f/,/2) не может быть упорядоченным. Более точно, мы имеем

Ф не ynop(fl)=>n{nlxl), (n2x2)fl-

п1<п2 и х2<х1 ® Yf Слияние(fl, f2)

=>(Peгyляp(f, fl)), т. е. Yx3, х4 Образ (fl)

fr(x3)<fr(x4) f-\x3)<f-(x4) Ф и ф=>YfCлuянue(fl, f2)-3{ntxl), {n2x2)f

п1<п2 и х2 < х1 =>не ynop(f), т. е. Упоряд (Слияние (fl, /2)) = Ф.

6.6. СлияниеС ({nlxl) + fl, {п2х2) + /2, п + N)

У по ряд (Слияние! ({nlxl) + fl,

{п2х2) + /2, п + Л))

Конкретизация 5.3.2(6) Упоряд ({{nxl) + I f/ е Слияние! (fl,

{n2x2) + f2, N)}