Разделяй и уравнивай

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

Для решения пункта в) заметим, что если взять палочки длин p₁, ..., p_n, то задача генерации требуемой случайной величины сведется к выбору случайной точки на одной из палочек. Если все палочки одной длины, то из них можно сложить прямоугольник — как получить случайную точку в нем? Подумайте, почему для эффективной работы алгоритма важно, что каждая палочка склеена не более чем из 2 кусков?

    а) Склеим все палочки в одну (в любом порядке), а затем разделим ее на равные куски произвольного размера, которые меньше самой маленькой из палочек. Заметим, что при таком разрезании каждая получившаяся палочка будет содержать не более 2 кусочков, то есть на каждой палочке будет не более одного места склейки. Действительно, если палочка содержит хотя бы два места склейки, то она содержит целиком какую-то из исходных палочек, что противоречит тому, что она короче их всех.

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

Очевидно, что в любом наборе всегда найдется хотя бы одна палочка не длиннее среднего и хотя бы одна палочка не короче среднего. Возьмем ту, что короче среднего. Ей недостает до средней длины какого-то куска, который тоже меньше среднего, а значит, его можно отрезать от той палочки, которая длиннее среднего.

Отложим получившуюся палочку в сторону. Останется n − 1 палочка, а средняя их длина не изменится, ведь мы убрали палочку, у которой как раз была средняя длина. Значит, описанную процедуру можно повторять еще и еще, пока не останется одна палочка, которая, очевидно, и будет нужной — средней — длины.

Чтобы выбрать любую точку на одной из них равновероятно, можно сначала равновероятно выбрать одну из палочек (с помощью функции генерации равномерного распределения, данной в условии, это можно сделать так: разбить единичный отрезок на n равных подотрезков, сгенерировать случайную точку и проверить, на какой отрезок она попала), а затем — точку на ней (для этого можно выбрать случайное число на отрезке [0, 1], а затем умножить его на длину палочки).

Осталось понять, какой из исходных палочек эта точка принадлежит. Для этого достаточно в процессе процедуры запомнить, из частей каких исходных палочек состоит каждая из n получившихся на первом этапе работы алгоритма палочек, и в каких местах находятся точки склейки. Если оказалось, что выбранная точка принадлежит куску, который исходно был частью палочки с номером k, то выдадим k как искомое значение случайной величины.

Подробно эффективность этого алгоритма мы обсудим в послесловии.

Прочтя условие пункта в), читатель может задаться вопросом: «А зачем нужна такая конструкция, если генерировать значения данной случайной величины можно гораздо проще?». Действительно, есть совсем простой алгоритм: склеим все палочки в одну, а затем выберем (точно так же, как это делалось в решении) случайную точку на этой длинной палочке. Определив, к какой из исходных палочек относится эта точка, можно получить искомое значение случайной величины.

Чем плох такой алгоритм?

На первый взгляд он проще в исполнении, однако в нем есть один шаг, который «на палочках» звучит просто, но если немного подумать, как реализовывать его в виде программы, то станет ясно, что он не так-то прост. Вот этот шаг: после того, как сгенерирована случайная точка x на длинной палочке, нужно понять, какой исходной палочке она принадлежит.

Информация о том, где находятся точки склейки, должна как-то храниться — скажем, в виде массива координат точек склейки: k-й элемент этого массива равен координате склейки кусочков \(p_k\) и \(p_{k+1}\) (легко видеть, что она равна частичной сумме префикса массива вероятностей: \(l_k = \sum\limits_{i=1}^{k} p_i\)). Чтобы понять, на каком из промежутков лежит точка x, нужно найти такое k, что \(l_k < x < l_{k+1}\) (для строгости добавим также частичные суммы для координат левого и правого концов длинной палочки: \(l_0\) и \(l_{n+1}\)). Найти такое k можно, перебрав все элементы массива за n операций, а алгоритмически подкованный читатель вспомнит, что бинарный поиск позволит сделать тоже за \(\log n\) операций. Таким образом, для генерации одного значения случайной величины требуется минимум \(O(\log n)\) операций в общепринятой нотации.

Покажем теперь, что предложенный в решении пункта в) алгоритм требует всего лишь \(O(1)\) — то есть какое-то постоянное (не зависящее от n) число операций. Действительно, сначала мы выбираем одну из палочек, затем точку на палочке. Поскольку на каждой палочке не более одного места склейки, то, чтобы понять, к какой из начальных палочек принадлежит сгенерированная точка, достаточно одной операции сравнения ее координаты с координатой места склейки. Выходит, что за счет некоторой предварительной обработки данных (нужно разрезать и склеить палочки), можно ускорить операции генерации. Если нам нужно много раз генерировать значения с одними и теми же параметрами p₁, ..., p_n, а число n достаточно большое, то выгода от ускорения каждой операции с лихвой перекроет расходы на предварительную обработку.

Наконец обсудим, как эффективно реализовать переклеивание палочек (алгоритм из пункта б)) в программе. На каждом шаге алгоритма нам нужно взять одну палочку не длиннее среднего и одну палочку не короче среднего. В программе можно завести два массива, в одном из которых будут лежать длины еще неиспользованных кусочков палочек, которые короче среднего, а в другом тех, которые длиннее (как мы упоминали в решении, средняя длина не меняется от шага к шагу). В начале работы алгоритма заполним эти массивы данными на входе палочками, а на каждом шаге будем доставать по одной палочке из каждого массива, записывать какие палочки мы склеиваем, а оставшийся неиспользованный кусок более длинной палочки возвращать в один из двух массивов, в зависимости от того, остался он длиннее среднего или нет.

Идея предварительного подсчета, когда мы один раз производим какие-то преобразования входных данных, чтобы потом эффективно выполнять однотипные операции, широко используется в алгоритмике. Упомянем два таких алгоритма: достаточно простой для понимания алгоритм Джонсона для поиска кратчайших путей в графе, а также куда более сложный и контринтуитивный, но весьма красивый классический алгоритм Фараха-Колтона и Бендера для многократного поиска минимума на различных подотрезках массива.