Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Статистика случайных перестановок, например, структура цикла случайной перестановок, имеет фундаментальное значение в анализе алгоритмов, особенно сортировочных алгоритмов, которые работают на случайных перестановок. Предположим, например, что мы используем quickselect (двоюродный брат quicksort) для выбора случайного элемента случайной пермутации. Quickselect будет выполнять частичную сортировку массива, поскольку разделяет массив в соответствии с поворотом. Следовательно, после выполнения быстрого выбора перестановка будет менее беспорядочной. Количество оставшихся нарушений может быть проанализировано с помощью генерирующих функций. Эти генерирующие функции в основном зависят от генерирующих функций статистики случайных перестановок. Поэтому очень важно вычислить эти генерирующие функции. Статья о случайных перестановках содержит введение в случайные перестановки.
The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions. The article on random permutations contains an introduction to random permutations.
Инварианты нечетного цикла
Типы пермутаций, представленные в двух предыдущих разделах, т. е. пермутации, содержащие четное число четных циклов и пермутации, которые являются квадратами, являются примерами так называемых нечетных инвариантов цикла, изученных Сунгом и Чжан (см. внешние ссылки). Термин "инвариант нечетного цикла" просто означает, что принадлежность к соответствующему комбинаторному классу не зависит от размера и количества нечетных циклов, возникающих в пермутации. Фактически мы можем доказать, что все нечетные инварианты цикла подчиняются простому повторению, которое мы выведем. Во-первых, вот еще несколько примеров нечетных инвариантов цикла.
The types of permutations presented in the preceding two sections, i. e. permutations containing an even number of even cycles and permutations that are squares, are examples of so called odd cycle invariants, studied by Sung and Zhang (see external links). The term odd cycle invariant simply means that membership in the respective combinatorial class is independent of the size and number of odd cycles occurring in the permutation. In fact we can prove that all odd cycle invariants obey a simple recurrence, which we will derive. First, here are some more examples of odd cycle invariants.
Обобщения
Аналогичная статистика доступна для случайных эндоморфизмов на конечном множестве.
Similar statistics are available for random endomorphisms on a finite set.