для которого Un может дать только тп различных значений, потому что окончательная перестановка в таком случае полностью определяется первыми генерированными значениями U. Так, например, если т = 2, определенные перестановки из 13 элементов никогда не появятся, поскольку 13! и 1.45 х 2. В большинстве случаев на самом деле нет необходимости получать все 13! перестановок, но огорчает, что исключение данных перестановок определяется фактически простым математическим правилом, таким как решетчатая структура (см. раздел 3.3.4).

Эта проблема не возникает, когда используется генератор Фибоначчи с запаздыванием, подобный 3.2.2-(7), с достаточно длинным периодом. Но даже таким методом невозможно получать все перестановки постоянно, если нельзя точно задать по крайней мере t\ различных начальных значений для инициализации генератора. Другими словами, не существует возможности получить \gt\ истинно случайных двоичных разрядов на выходе, если не получить Ig t\ истинно случайных двоичных разрядов на входе. Как говорится в разделе 3.5, не стоит из-за этого огорчаться.

Алгоритм S можно легко преобразовать для получения случайной перестановки случайных сочетаний (см. упр. 15). Случайные объекты комбинаторики других видов (например, разбиения) рассматриваются в разделе 7.2 и в книге CombinatoriaJ Algorithms by Nijenhuis and Wilf (New York: Academic Press, 1975).

УПРАЖНЕНИЯ

1. [M12] Объясните (1).

2. [80] Докажите , что алгоритм S никогда не пытается прочесть более Л згшисей своего входного файла.

► 3. [22] (*--1)-я запись в алгоритме S выбирается с вероятностью (n-m)/(Af-i), а не п/Л, однако алгоритм требует, чтобы выборка была беспристрастной, поэтому каждая запись должна выбираться с одинаковой вероятностью. Почему оба эти утверждения правильны?

4. [М23] Пусть p{m,t) - вероятность того, что выбрано точно т записей среди первых t в методе отбора выборок. Покажите непосредственно из алгоритма S, что

5. [М24] Чему равно среднее значение t по завершении алгоритма S? (Другими словами, сколько из Л записей будет просмотрено в среднем, прежде чем выборка станет полной?)

6. [М24] Чему равно среднеквадратичное отклонение значения, вычисленного в упр. 5?

7. [М25] Докажите, что любой заданный выбор п записей из множества Л записей может быть получен алгоритмом S с вероятностью 1/(). Следовательно, выборка является совершенно беспристрастной.

► 8. [МЗО] (Д. С. Виттер (J. S. Vitter).) Алгоритм S производит одну равномерно распределенную случайную величину для каждой входной записи. Цель этого упражнения - рассмотреть более эффективный подход, при котором можно быстрее вычислить точное число X входных записей, которые следует пропустить, прежде чем сделать первый выбор.

a) Чему равна вероятность того, что X >к,к задано?

b) Покажите, что результат (а) позволяет выполнить вычисление X, генерируя только одну равномерно распределенную случайную величину U, и производит 0(A) других вычислений.

c) Покажите, что можно также присвоить X <- min(yiv, Yn-i,- , Fv-n+i), где Yt независимы и каждое У« является случайным целым числом в области О < У« < t.

d) Найдите максимальную скорость, т. е. покажите, что X также может быть вычислено в среднем за 0(1) шагов, если использовать "метод втискивания", подобный 3.4.1-(18).

9. [12] Пусть п = 3. Если алгоритм R применяется к файлу, содержащему 20 записей, которые пронумерованы от 1 до 20, и если случайные числа, генерированные на шаге R3, равны соответственно

4,1,6,7,5,3,5,11,11,3,7,9,3,11,4,5,4,

какая запись попадет в резервуар? Какая из них окажется в окончательной выборке?

10. [15] Преобразуйте алгоритм R так, чтобы обойтись без резервуара, предполагая, что п записей текущей выборки можно хранить в памяти.

► 11. [М25] Пусть рт - вероятность того, что точно т элементов занесены в резервуар в течение первого прохода алгоритма R. Определите производящую функцию G{z) = YlmP" найдите среднее значение и среднеквадратичное отклонение. (Используйте идеи из раздела 1.2.10.)

12. [М26] Суть алгоритма Р состоит в том, что любую перестановку тг можно однозначно записать как результат транспонирования в виде тг = («<<)... (азЗ)(а22), где 1 <aj < j для t > j > 1. Докажите, что существует также единственное представление вида тг = (Ь22)(ЬзЗ)... (btt), где 1 < bj < j для 1 < j < t, и составьте алгоритм для вычисления Ък через Uk за 0{t) шагов.

13. [М23] (С. В. Голомб (S. W. Golomb).) Один из наиболее простых способов тасования игральных карт - разделение колоды карт на две максимально равные части и их тасование вместе. (В правилах Хойла карточных игр при обсуждении профессиональной этики игроков в карты сказано: "Тасование такого вида можно выполнить приблизительно трехкратным тщательным перемешиванием игральных карт".) Рассмотрим колоду из 2п - 1 игральных карт Xi, Х2, , X2n-i- "Идеальное перемешивание" - это разделение S раз этой колоды на части Al, 2, ..., Х„ и Xn+i, , X2n-i- Чередуя их, получим Xi, Хп+1, Х2, Хп+2, Х2П-1, Хп- Операция "разрезания" с меняет Xi, Х2, Х2П-1 на Aj+i, ..., A2n-i, Al, ..., Xj. Покажите, что, комбинируя идеальное перемешивание и разрезание, можно получить не более (2п -1 )(2п - 2) различных упорядочений компоновок игральных карт, если п > 1.

14. [22] Разрезав и перетасовав перестановку aodi Лп-г, можно заменить ее последовательностью, содержащей подпоследовательности

0ха(х+1)тьап 0.y-l)Tnodn И «у a(j,+i) mod п • "(i-l) mod п,

которые перемешаны определенным способом для некоторых хну. Таким образом, последовательность 3890145267 является разрезанием и перетасовкой 0123456789 с а; = 3 и У = 8.

а) Начав с расположенных обычным образом 52 игральных карт

23456789 10 JQKA23456789 10 JQKA23456789 10 JQKA23456789 10 JQKA

мистер Д. Г. Квик (J. Н. Quick) ("Студент") сделал случайное разрезание и перетасовку, затем убрал крайнюю слева карту и вставил ее в случайное место. Получилась последовательность

910KJQAKA2Q32345674895I0 6J7Q8K910JQAK23A42345656787910J8

Кгжую карту он убрал из крайней слева позиции?

b) Начав снова с колоды в ее обычном порядке, Квик сделал три разрезания и перетасовки, прежде чем сдвинул крайнюю слева карту на новое место:

10JQ3456JJQ46KA23K4756QA75A876KK9A78910810 825J2 3Q4932910

Какую карту он сдвинул на этот раз?

► 15. [30] (Оле-Йохан Дахл (Ole-Jolian Dahl).) Если Х/, = к для 1 < А; < t в начале алгоритма Р и если остановить алгоритм, когда j достигнет значения t - n, последовательность Xt~n+i, , Xt станет случайной перестгшовкой случайных комбинаций из п элементов. Покажите, как эффективно смоделировать эту процедуру, используя только 0{п) ячеек памяти.

► 16. [М25] Придумайте метод вычисления случайной выборки по п записей из Л при заданных и п, оаювываясь на идее рандомизации (раздел 6.4). Можете использовать в нем 0{п) ячеек для хранения и в среднем 0{п) единиц времени. Метод должен представлять выборку как упорядоченное множество целых чисел 1 < Al < Лг < • < Х„ < N.

17. [М22] (Р. В. Флойд (R. W. Floyd).) Докажите, что следующий алгоритм генерирует случайную выборку S из п целых чисел из {1,..., Л}. Присвойте сначала S <- 0, а затем для }*~N - n-\-\,N-n + 2, ...,N{b таком порядке) присвойте к <- \ jU\ -I- 1 и

rSU{A;}, если А; S; l5U{j}, еслиА:€5.