PI. [Инициализация.] Присвоить г <- t, f <- 0. (В этом алгоритме всегда будет выполняться неравенство О < / < t\/r\.)

Р2. [Найти максимум.] Найти максимум {Ui,... ,Ur}. Если Ug - это максимум, присвоить f<r-r-f + s-l.

РЗ. [Замена.] Заменить Ur •(-> Us.

Р4. [Уменьшить г.] Уменьшить г на 1. Если г > 1, то вернуться к шагу Р2.

Последовательность (Ui,..., Щ) будет расположена в порядке возрастания, когда алгоритм остановит работу. Чтобы доказать, что функция / единственным образом характеризуется начальным порядком (Ui,..., Ut), заметим, что алгоритм Р может быть обращен.

Для г = 2, 3, ..., i присвоить S -f- / mod г, f [f/r] и заменить Ur Us+i-

Легко видеть, что это разрушит эффект шагов Р2-Р4. Следовательно, не существует двух перестановок, которые могут иметь одно и то же значение /, и алгоритм Р обоснован.

Главной идеей, которая лежит в основе алгоритма Р, является представление со смешанным основанием, называемым "факториальной числовой системой": каждое целое число на отрезке О < / < может быть единственным образом записано в виде

/=(... (ct-i x (( - 1) -ь ct-2) x (( - 2) 4- • • • 4- сг) x 2 -I- ci {t- 1)! ct-i +{t- 2)! q 2 4- • • 4- 2! c2 4-1! сь (7)

где "цифры" Cj - это целые числа, удовлетворяющие неравенствам

0<cj< j для l<j<t. (8)

В алгоритме Р Cr-i = s - 1, когда шаг Р2 выполнен для заданного значения г.

G. Критерий монотонности. В последовательности можно проверять распределение восходящих и нисходящих серий. Имеется в виду проверка распределений длин монотонных частей заданной последовательности (отрезки возрастания или убывания).

В качестве примера точного определения серии рассмотрим последовательность цифр "1298536704". Проводя вертикальные линии слева, справа, а также между Xj и Xj+i всякий раз, когда Xj > Xj+i, получим

1298536704. (9)

Таким образом выделяются восходящие серии: сначала - серия длиной 3, затем - две серии длиной 1, затем - снова серия длиной 3 и, наконец, серия длиной 2. В алгоритме из упр. 12 показано, как табулировать длину восходящей серии.

Мы не будем применять -ритерий к подсчету серий, как в критерии интервалов и критерии собирания купонов (которые во многих других отношениях

подобны этому критерию), поскольку смежные интервалы не являются независимыми. Длинные серии имеют тенденцию следовать за короткими и наоборот. Такого отсутствия независимости достаточно, чтобы применение х-критерия было неправомочным. Вместо этого можно подсчитать следующую статистику для случая, когда длины серий определены так, как в упр. 12:

V = (COUNT[i] - n6i)(C0UNT[j] - nbj)aij,

(10)

i<i,j<6

где n - длина последовательности и матрицы коэффициентов А = (ajj)i<j,j<6 и В = {bi)i<i<6 заданы в следующем виде:

/ 4529.4 9044.9 13568 9044.9 -18097 27139 13568 27139 36187 45234 55789

18091 22615 27892

40721 54281 67852

18091 22615 27892

36187 45234 55789

54281 67852 83685

72414 90470 111580

90470 113262 139476

83685 111580 139476 172860

(Значения Oij, приведенные здесь, только приблизительны; точные значения могут быть получены из формул, приведенных ниже.) Статистика V в (10) должна иметь Х-распределение с шестью, а не пятью, степенями свободы, когда п большое. Значение п должно, скажем, равняться 4 ООО или больше. Тот же критерий можно применить к нисходящей серии.

Значительно более простой и более практичный критерий монотонности приведен в упр. 14, так что читате.ль, интересующийся только проверкой генераторов случайных чисел, может пропустить несколько страниц ц перейти к критерию "максимум-" после выполнения этого упражнения. С другой стороны, с математической точки зрения поучительно увидеть, как можно изучить сложный критерий монотонности со взаимно независимыми сериями. Так что на некоторое время мы отклонимся в сторону.

Пусть задана- перестановка п элементов. Пусть Zpi = 1, если положение г является началом возрастающей серии длиной р или больше, и пусть Zpi = О в других случаях. Например, рассмотрим перестановку (9) с п = 10. Легко видеть, что

Zn = Z21 = Z31 = Z14 = Zi5 = Zie = 226 = Zse = Zi9 Z29 = 1,

a все оЛальные Zij равны нулю. В этих обозначениях

Rp = Zpi + Zp2 + --- + Zpn (12)

представляет собой число серий длиной >р и

Rp = Rp- Rp+г (13)

является числом серий, длина которых точно равна р. Наша цель - подсчитать среднее значение (mean) Rp, а также ковариацию (covar)

covar{Rp, Rg) - mean((i?p - теап(Лр)) [Rq - теап(Лд))),

являющуюся мерой зависимости Rp п Rg. Средние значения должны быть подсчитаны как среднее по множеству всех п! перестановок.

Равенства (12) и (13) показывают, что можно выразить в терминах средних значений Zpi и ZpiZqj, поэтому сначала получим следующий результат (предполагая, что г < j):

Sr 7 - J r. . iM еслиг<п-р-1-1;

О в других случаях.

7-7ТГ-,-т-если г-Hp = J < п - д-Н 1;

(p+l)!?! (р + 9+1)! -

. О в других случаях.

Суммирование () производится по всем возможным перестановкам. Для иллюстрации вычислений рассмотрим наиболее трудный случай, когда г-Нр = j <n-q-\-\, а г" > 1. Величина ZpiZqj равна либо нулю, либо единице, поэтому суммирование сводится к подсчету числа перестановок UiU2---Un, для которых Zpi = Zqj = 1, т. е. всех таких перестановок, что

Ui-i>Ui<---< Ui+p-i >Ui+p<---< Ui+p+g-i. (15)

Количество таких перестановок может быт). подсчитано следующим образом. Существует (p++i) возможностей выбора элементов дя положения, изображенного в (15), существует

<-->с:)-(:!Г)-сг)- <->

способов их расположения в таком порядке, как в (15) (см. упр. 13), и существует (п - р - g - 1)! способов упорядочения оставшихся элементов. Следовательно, выражение в (16) нужно умножить на (pi)(n - р - g - 1)! и разделить на п!, чтобы получить искомую формулу.

Из соотношения (14) и несколько громоздких вычислений получим

теап(Л;) = {п + 1)р/(р + 1)! - (р - 1)/р!, 1 < Р < п; (17)

соуаг(Лр, Rg) = mean(J?p R) - mean(J?p) теап(Л)

l<i,i<n

mean{Rl) + f{p,q,n), если p + q<n,

mem{R[) - теап(Лр) теап(Л), если p + q> n,