Cyclic permutation of elements in one-dimensional array.pdf Введение Задача циклического сдвига одномерного массива из N элементов на k позиций вправо или влево является классической, казалось бы, ничем не выдающейся олим-пиадной «задачкой». Например, если N =11, k = 3 и для определённости сдвиг осуществляется вправо, то вектор «abracadabra» превратится в «braabracada». Однако эта задача имеет важное прикладное значение. Например, во всех современных текстовых редакторах обязательно присутствует возможность выделения мышкой текста и последующего его перемещения в любое другое место редактируемого файла. Операция циклического сдвига в некоторых языках программирования является элементарной [1], то есть выполняется одним оператором. При этом важно, что циклический сдвиг соответствует обмену соседних блоков памяти разного размера. Ограничения по времени и объёму памяти существенны для многих подобных приложений. Можно решить данную задачу, копируя первые k элементов массива во временный буфер, сдвигая оставшиеся (N - k) элементов влево на k позиций, а затем копируя данные из буфера в основной массив на последние k позиций. Однако данная схема использует k дополнительных переменных, т. е. требует выделения дополнительной памяти. Можно определить функцию, сдвигающую массив влево на один элемент (за время, пропорциональное N), а потом вызвать её k раз, но такой алгоритм будет отнимать слишком много времени. Другое очевидное решение «в лоб» - также использовать вспомогательный буферный N-элементный массив. Сначала элементы исходного массива перемещаются в буферный массив с сохранением их порядка. Далее в позицию с номером i (0 ^ i < N) исходного массива вставляется элемент с позиции /(i) из буферного массива, где отображение / : {0,... , N - 1} ^ {0,... , N - 1} задаётся по правилу где через [x] обозначена целая часть вещественного числа x. В этом решении мы также сталкиваемся с дополнительным расходом памяти. Таким образом, актуальным является построение алгоритма, который осуществляет перестановку элементов исходного массива, по возможности с наименьшим их перемещением в памяти и без дополнительного её расхода, или, по-крайней мере, чтобы этот расход не рос пропорционально объёму сдвигаемого фрагмента данных. 1. Алгоритмы циклической перестановки элементов массива Существует несколько проверенных временем и опытом алгоритмов [1, 2], которые позволяют обойтись лишь несколькими дополнительными переменными и завершить весь сдвиг за время, пропорциональное N. Алгоритм A. Вместо использования буферного массива введём только одну дополнительную переменную. Помещаем первый элемент массива x[0] во временную переменную t. Оставшиеся N - 1 элементов массива перемещаются на одну позицию влево, и в конец массива помещается содержимое переменной t. После применения данной процедуры m = k mod N раз получаем необходимую перестановку. Несложно подсчитать, что реализация такого алгоритма использует m (N + 1) операций перемещения элементов массива. Сложность алгоритма можно существенно уменьшить, если вместо m-разового применения операции циклического сдвига на одну позицию каждый элемент сразу сдвигать на m позиций. Таким образом приходим к следующему алгоритму. Алгоритм B. Элемент x[0] помещается во временную переменную t, затем x[m] помещается в x[0], x[2m] -в x[m] и так далее (перебираются все элементы массива x с одинаковыми по модулю N индексами), пока не возвращаемся к элементу x[0], вместо которого записывается содержимое переменной t. Если при этом не были переставлены все элементы, процедура повторяется, начиная с x[1], и так далее до достижения конечного результата. Отметим, что сложность данного алгоритма в сравнении с предыдущим примерно в m раз меньше. Алгоритм C. Можно предложить другой алгоритм, который возникает из рассмотрения задачи с другой точки зрения. Циклический сдвиг массива x сводится фактически к замене ав на ва, где а - первые k элементов массива x, в - оставшиеся элементы. Для определённости предположим, что а короче в. Тогда разобьём в на в^й, и вг^м, где вг-ight содержит k элементов (столько же, сколько и а). Поменяем местами а и вгщМ, получим вгщмвкйа. При этом а окажется в конце массива - там, где и полагается. Поэтому можно сосредоточиться на перестановке вг^м, и выъ Однако эта задача сводится к начальной, поэтому алгоритм можно вызывать рекурсивно. Алгоритм D. Нужно преобразовать массив {ав} в {ва}. Предположим, что у нас есть функция «переворота» reverse, переставляющая элементы массива в противоположном порядке. В исходном состоянии массив имеет вид ав. Алгоритм состоит в трёхразовом применении функции reverse: ва = reverse (reverse (а) reverse (в)). В [1] приведено: «Код, использующий функцию переворота, оказывается эффективным и малотребовательным к памяти, и настолько короток и прост, что при его реализации сложно ошибиться. Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе. В [3] Керниган пишет: «Эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной». Ниже предложен новый алгоритм циклической перестановки элементов одномерного массива, который вообще не требует дополнительной памяти и использует минимально возможное число попарных перестановок элементов. 2. Формулировка основного результата Для произвольного 0 ^ i < N обозначим через ш (i) наименьшее целое число, для которого выполняется неравенство f(w(i)) (i) = f (f (.../ (i))) ^ i, где операция композиции выполняется ш (i) раз. Отметим, что число ш (i) существует. Действительно, среди i + 1 чисел f(j) (i), j = 0,1,..., i, по крайней мере одно не меньше i. Следовательно, отображение ш : {0,... , N - 1} ^ {0,... , N - 1} определено корректно. Теорема 1. Наименьшее число попарных перестановок элементов одномерного массива (a[0], a [1] ,..., a [N - 1]), за которое можно осуществить его циклический сдвиг на k позиций вправо, равно мощности J (N, k) множества {i : N > i ^ 0 & g (i) > i} , где отображение g : {0,..., N - 1} ^ {0,... , N - 1} задаётся правилом g (i) = f (i) (0 ^ i < N), (2) а отображение f определяется соотношением (1). Не нарушая общности, ограничимся рассмотрением случая 0 < k < N. Для отображения (2) можно получить явное представление. Действительно, в случае 0 ^ i < k из (1) следует, что f (i) > i и, следовательно, ш (i) = 0. В случае i ^ k положим i = k + j, где 0 ^ j < N - k. Непосредственно проверяется, что для всех ш ^ 0 fИ (k + j) = rN - qk + j, где 0 ^ r ^ q, q ^ 1. Таким образом, задача определения наименьшего показателя композиции ш, при котором выполняется неравенство k+j ^ f(ш) (k + j) ^ N - 1, приводит к следующей задаче целочисленной минимизации: определить точку P (r, q) на плоскости с наименьшими целыми координатами r, q, которая расположена в области, заданной неравенствами k k N - j - 1 n ^r - ^q ^-N-, 1 ^r ^ q, q ^1. (3) Перейдём непосредственно к доказательству теоремы. Введём в рассмотрение операцию swap(i,j) перестановки элементов массива с индексами i и j. Для реализации данной операции не обязательно использовать вспомогательную буферную переменную, например, если на множестве элементов рассматриваемого массива a определены взаимно обратные операции сложения и вычитания, то можно обменять содержимое элементов a [i] и a [j], выполнив последовательно следующие операции: 1) a [i] := a [i] + a [j]; 2) a [j] := a [i] - a [j]; 3) a [i] := a [i] - a [j]. Далее, будем последовательно выполнять swap (i, f (i)) (0 ^ i < N) до тех пор, пока выполняется неравенство f (i) > i. Если для текущего значения i выполняется противоположное неравенство f (i) < i, то выполнение операции swap (i, f (i)) приводит к тому, что элемент a [i] обменивается содержимым с элементом a [f (i)], который ранее уже подвергался выполнению операции swap. Следовательно, в этом случае для определения правильного значения индекса второго элемента необходимо использовать функцию (2). Окончательно рассматриваемый алгоритм циклической перестановки может быть сформулирован в следующей форме. Алгоритм E. Циклический сдвиг вправо на k позиций произвольного N-элемент-ного массива (a [0] , a [1] ,... , a [N - 1]) можно осуществить, выполняя J (N, k) последовательных попарных перестановок его элементов: swap (0, g (0)) о swap (1, g (1)) о ... о swap (J (N, k) - 1,g (J (N, k) - 1)). В таблице приведены некоторые примеры применения данного алгоритма. В теоретико-групповой трактовке [4] полученный результат можно сформулировать следующим образом: любая k-циклическая перестановка элементов произвольного N-элементного массива может быть представлена как композиция не более чем J (N, k) транспозиций его элементов. k = 1, N = 6 k = 2, N = 6 ( 0 12 3 4 5 ) г ^ g(i) г ^ f (г) ( 0 1 2 3 4 5) г ^ д(г) г ^ f (г) (5 1 2 3 4 0 ) 0 ^ 5 0 ^ 5 (4 1 2 3 0 5 ) 0 ^ 4 0 ^ 4 ( 5 0 2 3 4 1 ) 1 ^ 0 ^ 5 1 ^ 0 (45: 2 3 0 1) 1 ^ 5 1 ^ 5 (501 3 4 2 ) 2 ^ 1 ^ 5 2 ^ 1 (450 3 2 1 ) 2 ^ 0 ^ 4 2 ^ 0 (5012 4 3 ) 3 ^ 2 ^ 5 3 ^ 2 ( 4 5 0 1 2 3) 3 ^ 1 ^ 5 3 ^ 1 (501234) 4 ^ 3 ^ 5 4 ^ 3 4 ^ 2 ^ 4 4 ^ 2 5 ^ 4 ^ 5 5 ^ 4 5 ^ 3 ^ 5 5 ^ 3 k = 3, N = 6 k = 4, N = 6 ( 0 1 2 3 45) г ^ g(i) г ^ f (г) ( 0 1 2 3 4 2 ) г ^ д(г) г ^ f (г) (3 1 2 0 4 5) 0 ^ 3 0 ^ 3 (2 1 0 3 4 5) 0 ^ 2 0 ^ 2 ( 3 4 2 0 1 5 ) 1 ^ 4 1 ^ 4 (23014 5) 1 ^ 3 1 ^ 3 (345012) 2 ^ 5 2 ^ 5 ( 2 3 4 [Г| 0 5 ) 2 ^ 4 2 ^ 4 3 ^ 0 ^ 3 3 ^ 0 ( 2 3 4 5 0 1) 3 ^ 5 3 ^ 5 4 ^ 1 ^ 4 4 ^ 1 4 ^ 0 ^ 2 ^ 4 4 ^ 0 5 ^ 2 ^ 5 5 ^ 2 5 ^ 1 ^ 3 ^ 5 5 ^ 1 k = 5, N = 6 ( 0 1 2 3 4 5 ) г ^ д(г) г ^ f (г) (1 2 3 4 5 ) 0 ^ 1 0 ^ 1 (12 0 3 4 5 ) 1 ^ 2 1 ^ 2 (12 3 0 4 1 5) 2 ^ 3 2 ^ 3 (12 3 4 0 5 ) 3 ^ 4 3 ^ 4 (12 3 4 5 0) 4 ^ 5 4 ^ 5 5 ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 5 ^ 0 Заключение Эффективность реализации алгоритма E определяется способом вычисления функции (2). С геометрической точки зрения эта задача сводится к решению задачи целочисленной минимизации (3). В качестве дальнейшего предмета исследования является открытым вопрос построения, по возможности, явного решения задачи (3).

Скачать электронную версию публикации