Как сделать перестановку в массиве

Одномерные массивы

Тема: Перестановка элементов массива.

Перестановка двух элементов

Задача. Поменять местами два элемента массива с номерами k1 и k2.

Рассмотрите процедуру, с помощью которой эта задача легко решается.

Перестановка части массива

Задача. Дан одномерный массив А, состоящий из 2n элементов. Поменять местами первую и вторую его половины

Задание. Оформите решение этой задачи, применив процедуру обмена значений Obmen2, рассмотренную выше.

Задание. Выберите с учителем задачи для самостоятельного решения из предложенного списка:

Работа с несколькими массивами

В Turbo Pascal можно одним оператором присваивания передать все элементы какого-либо массива другому массиву того же типа, например:

После такого присваивания все пять элементов массива a получат значения из массива b.

Рассмотрим одну из типичных задач.

Задача. Найти скалярное произведение двух массивов.

Скалярным произведением двух массивов одинаковой размерности называется сумма произведений соответствующих элементов. Это можно записать так:

Тогда можно составить следующую функцию:

Задание. Выберите с учителем задачи для самостоятельного решения:

Источник

Генерация перестановок

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N!. Действительно:

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N, а последней — N N-1 … 1.

Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:

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

Результат выполнения

Перестановки с повторениями

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

Результат работы приведенного выше алгоритма:

Источник

Зона кода

Листал я недавно книгу Никлауса Вирта «Алгоритмы и структуры данных» 2010-го года издания и наткнулся на задачу для самостоятельного решения, в которой предлагалось написать процедуру порождения всех перестановок из n элементов. Машинально я отметил эту задачу как простую и, по этой причине, неинтересную. А потом вдруг задумался: «И как же их порождать?»

К своему удивлению, сходу задачу решить не смог. И, немного подумав, тоже не смог. Пришлось минут 40 поваляться на диване с ручкой и листком бумаги. Итогом такого времяпрепровождения стало то, что я придумал алгоритм генерации одной перестановки на основе уже имеющейся, который позволяет, располагая начальной перестановкой, построить всю цепочку перестановок, вплоть до последней.

Впоследствии оказалось, что придумал я ни что иное, как алгоритм Нарайаны, изобретённый одноимённым индийским математиком. Эх, мне бы поторопиться! Взялся бы я за решение задачи чуть раньше, веков этак на 7, и, глядишь, алгоритм сейчас назывался бы иначе.

Алгоритм достаточно простой, да и реализующую его программу на языке C99, которую мы напишем, сложной тоже не назовёшь, поэтому будем считать, что данная статья адресована новичкам.

О перестановках

Сначала разберёмся с тем, что такое перестановка. Перестановкой из n элементов ( n-элементной перестановкой, перестановкой порядка n), где n — натуральное число, будем называть упорядоченный набор, состоящий из n объектов произвольной природы. Сами эти объекты, при этом, будем называть элементами данной перестановки. Набор, не содержащий ни одного объекта, будем назвать пустой, 0-элементной перестановкой или перестановкой нулевого порядка.

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

Перестановки n-го порядка будем записывать в виде пары открывающейся и закрывающейся квадратных скобок, внутри которой через запятую перечисляются элементы перестановки в том порядке, в котором они в ней расположены. Вот пример двух перестановок 4-го порядка: [1, 2, 3, 4], [3, 2, 4, 1]. Пустую перестановку будем обозначать так: [].

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

Любые 2 перестановки n-го порядка состоят из одних и тех же элементов. Если порядок элементов при этом совпадает, то такие перестановки будем называть равными или совпадающими. А если не совпадает, то такие перестановки будем называть неравными, различными или несовпадающими. Можно показать, что количество всех попарно различных перестановок из n элементов равно n!.

Равенство двух n-элементных перестановок a и b будем обозначать так: a = b.

Формулировка задачи

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

Написать программу, генерирующую все n! перестановок из n элементов.

А теперь можно приступать к решению.

Построение алгоритмов

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

Рассмотрим 2 несовпадающие перестановки a = [a₁, a₂, …, a_n] и b = [b₁, b₂, …, b_n]. Будем говорить, что перестановка a больше перестановки b или, что то же самое, перестановка b меньше перестановки a, если выполнено одно из следующих двух условий:

Факт заключающийся в том, что перестановка a больше перестановки b, будем обозначать так: a > b или b b или a b и b > с, будет выполнено a > c, то любой набор перестановок n-го порядка можно единственным образом упорядочить так, что за каждая последующая перестановка превышает предыдущую.

А теперь давайте рассмотрим алгоритм получения на основе n-элементной перестановки a = [a₁, a₂, …, a_n] превышающей её перестановки b, при условии, что она существует (т. е. a не является наибольшей перестановкой). Это тот самый алгоритм Нарайаны, упоминавшийся в начале статьи. Вот он:

Эти 2 утверждения об упорядоченности элементов перестановок a и b, имеющих номера с i + 1-го по n-й, нам ещё пригодятся в дальнейшем.

Как мы видим, перестановка b, полученная в результате выполнения алгоритма, удовлетворяет неравенству b > a, т. к. первые i − 1 элементов перестановок a и b совпадают (при условии, что i > 1), а a_j > a_i, т. е. i-й элемент b больше i-го элемента a.

Таким образом, если мы возьмём в качестве начальной n-элементной перестановки наименьшую, то, многократно генерируя по приведённому рекуррентному алгоритму новые перестановки, в итоге придём к наибольшей перестановке, получив, в итоге, цепочку перестановок n-го порядка. Но можно ли утверждать, что любая n-элементная перестановка будет являться одним из звеньев в полученной цепочке?

Ответ на это вопрос утвердителен. Давайте докажем это от противного. Предположим, что найдётся перестановка c = [c₁, c₂, …, c_n], которая не является звеном в упомянутой выше цепочке. Тогда, поскольку c не совпадает ни с наименьшей n-элементной перестановкой, ни с наибольшей, найдутся две перестановки a и b, являющиеся соседними звеньями в цепочке, такие, что a 1) элементов перестановки c должны совпадать с первыми i − 1 элементами перестановки a (а значит, и с первыми i − 1 элементами перестановки b). Действительно, из [c₁, c₂, …, c_i-1] [a₁, a₂, …, a_i-1] следовало бы, что c > b, но ни того, ни другого быть не может в силу нашего предположения о том, что a a и того, что первые i − 1 элементов (при условии, что i > 1) перестановок a и c совпадают, следует, что c_i > a_i.

Аналогично: из того, что все элементы перестановки b, начиная с i + 1-го, расположены в ней по возрастанию, следует, что среди всех перестановок, первые i элементов которых совпадают с первыми i элементами перестановки b, перестановка b является наименьшей. Отсюда, с учётом того, что с 1) перестановок b и c совпадают, следует, что c_i 1. Но чисел, стоящих в перестановке a правее числа a_i, заключённых между a_i и a_j, не существует, т. к. a_j — это наименьшее из чисел, стоящих в a правее числа a_i, превосходящих a_i (см. 3-й шаг алгоритма). Значит, все числа, заключённые между a_i и a_j, расположены в a левее a_i (т. е. имеют индексы меньшие i). Однако, в силу того, что первые i − 1 элементов перестановки c совпадают с первыми i − 1 элементами перестановки a, все эти числа (заключённые между a_i и a_j) и в перестановке c также имеют индексы меньшие i, т. е. число c_i одним из таких чисел быть никак не может. Значит, и в этом случае числа c_i, удовлетворяющего неравенству a_i

Таким образом, мы пришли к следующему алгоритму генерации всех n-элементных перестановок:

А теперь переходим к программированию.

Создание программы

Для хранения перестановок будем использовать единственный массив, который будем модернизировать по мере генерации перестановок. Как только в массив будет помещена очередная перестановка, так сразу же она будет выведена на печать.

Каждый элемент массива будет содержать один элемент перестановки. Порядок элементов в массиве, разумеется, будет соответствовать порядку элементов в перестановке.

Программа будет состоять из единственного файла, начинающегося со следующих директив #include :

В случае удачи, в соответствии с шагом 5 алгоритма, меняем порядок элементов массива, имеющих индексы, превышающие i (стр. 15-16).

Во-вторых, в алгоритме Нарайаны порядок двух действий, одно из которых описано в шагах 3, 4, а другое — в шаге 5, неважен. Мы воспользовались этим, и, реализуя алгоритм, изменили порядок этих действий (т. е. сначала реализовали шаг 5, а затем — шаги 3, 4). Причина этого — в том, что, если мы движемся от начала массива к концу, то немного проще искать наименьший элемент массива, не превосходящий заданное значение, если элементы упорядочены по убыванию, а не по возрастанию. Из-за этого полученное значение j оказывается вообще никак не связанным с числом j из алгоритма.

Кстати, упорядоченность элементов массива, среди которых мы проводим поиск в строках 18-19, позволяет использовать бинарный поиск. Но в нашем случае это лишнее, поскольку экономия времени будет минимальной.

В следующей функции реализован второй алгоритм предыдущего раздела.

Функция generate() принимает в качестве параметра неотрицательное целое число и выводит на печать все перестановки, порядок которых равен этому числу.

В противном случае создаём массив perm размера n (стр. 8) и заполняем его числами от 1 до n включительно (стр. 9-10). Теперь в perm хранится наименьшая перестановка. Далее в цикле do while многократно распечатываем текущую перестановку и генерируем посредством вызова функции next() следующую, до тех пор, пока очередной вызов next() не вернёт false (см. стр. 11-18).

Последняя функция нашей программы — это функция main() :

Функция очень простая. В ходе одной итерации бесконечного цикла while() пользователю предлагается ввести число от 0 до 9 или символ ‘q’ (стр. 5). При вводе ‘q’ работа программы завершается (стр. 8, 9), а при вводе числа посредством вызова функции generate() на консоль выводятся все перестановки, степень которых равна этому числу (стр. 10, 11), после чего происходит переход к следующей итерации. Если пользователь вводит символ, отличный от 11-ти допустимых, на консоль выводится сообщение об ошибке (стр. 12, 13) и также осуществляется переход к следующей итерации.

Выполнение программы

В результате запуска программы на выполнение может состояться, например, следующий диалог с пользователем:

Как мы видим, программа работает корректно. Задача решена!

Заключение

Добавлю кое-что напоследок. Когда-то очень давно я написал программу на Java, генерирующую все сочетания из n элементов по m. Теперь у нас есть программа, генерирующая все перестановки из n элементов.

А как генерировать все размещения из n элементов по m? Для этого нужно совместить обе программы. Сначала перебираем все сочетания из n элементов по m. Затем для каждого сочетания строим все перестановки из m элементов, входящих в это сочетание. Все построенные таким образом перестановки в совокупности и будут образовывать все размещения из n элементов по m.

Источник

Зона кода

Задача, разумеется, оказалась сложной именно для меня. Но, при этом, и очень интересной. Вот её условие, обнаруженное на просторах Интернета:

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

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

Второе условие содержит понятие «сложность». Под сложностью можно понимать количество элементарных операций, которое требуется совершить, чтобы решить задачу для конкретного n. К таким операциям можно отнести, например, перемещение элемента с одной позиции на другую или транспозицию элементов. Те операции, количество которых фиксировано и не зависит от n, при подсчёте сложности можно не учитывать.

Поскольку размер дополнительной памяти не может зависеть от размера массива, то придётся ограничиться или циклическими перестановками элементов, или транспозициями, которые, впрочем, являются частным случаем циклических перестановок.

Циклические перестановки — тупиковый путь?

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

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

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

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

В итоге, я решил отказаться от идеи циклических перестановок, что, впрочем, не означает, что решения, на них основанного, не существует.

Рекурсивный алгоритм. Частный случай

Следующая идея, посетившая меня, — свести задачу для массива к двумя задачам для полумассивов. Это можно сделать с помощью последовательно выполняемых транспозиций — операций, меняющих местами два элемента массива.

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

В результате описанной операции каждый из элементов массива оказывается расположенным в «своей» половине массива. Таким образом, каждую из половин можно теперь обрабатывать независимо от другой. Именно такая обработка и является следующим шагом. Каждую из половин массива снова подвергаем операциям, описанным для исходного массива. Это продолжается до тех пор, пока не дойдёт дело до обработки 4-элементных «подмассивов», после которой элементы исходного массива оказываются расположенными в нужном нам порядке.

Кстати, тот же принцип (сведение исходной задачи для массива к идентичным задачам для двух его частей) лежит и в основе алгоритма быстрой сортировки.

Давайте рассмотрим действие описанного алгоритма на примере массива, состоящего из m = 16 элементов (при этом n = 8). Схематично весь процесс изображён на рисунке ниже.

Схема обработки 16-элементного массива

Элементы массива изображены в виде кружков, причём белый цвет соответствует элементам, обозначенным в условии буквой a с индексом, а чёрный — обозначенным буквой b с индексом. Под каждым кружком имеется число, «жёстко» с ним связанное (т. е. кружки будут перемещаться вместе с соответствующими им числами). Это число представляет собой место элемента, которое он должен занимать в окончательно преобразованном массиве. Таким образом, в результате работы алгоритма цвета кружков должны чередоваться, а связанные с ними числа должны располагаться в порядке возрастания от 1 до 16.

На схеме имеются 4 изображения массива, соединённых стрелками. Стрелки означают шаги, посредством которых изменяются порядки расположения элементов в массиве. Как мы видим, наша задача решается в три шага.

На первом шаге элементы массива, стоящие на местах 5, 6, 7, 8 меняются местами с элементами 9, 10, 11, 12 соответственно. На первом изображении массива все 8 элементов, подлежащих перемещению, обведены прямоугольной пунктирной рамкой. На втором изображении они расположены на новых местах, а сам массив разделён короткой вертикальной чертой на две равные части, которые, в дальнейшем, будут преобразовываться независимо друг от друга.

На втором шаге элементы, стоящие на местах 3, 4 меняются местами с элементами, стоящими на местах 5, 6 соответственно, а стоящие на местах 11, 12 — соответственно со стоящими на местах 13, 14 (все эти 8 элементов выделены двумя прямоугольными рамками на втором изображении). На третьем изображении эти элементы уже стоят на новых местах, а сам массив разбит вертикальными чертами на 4 равных части.

На третьем шаге транспозиции подвергаются 2-й и 3-й элементы, 6-й и 7-й, 10-й и 11-й, 15-й и 14-й. Эти элементы выделены на третьем изображении уже четырьмя прямоугольными рамками. Как можно заметить, третий шаг приводит нас к искомому результату (см. четвёртое изображение массива).

Давайте за сложность c_n алгоритма, обрабатывающего массив из m = 2n элементов примем количество необходимых для такой обработки транспозиций. Получаем:

Здесь мы использовали хорошо известный из математического анализа факт, состоящий в том, что n является бесконечно большой более высокого порядка, чем ln n. Итак, как мы видим, сложность алгоритма удовлетворяет требованию задачи. Кстати, саму сложно можно оценить следующим образом: c_n = O(n ln n).

А будет ли при реализации алгоритма выполнено требование к дополнительной памяти? Об этом мы поговорим ближе к концу статьи.

Реализация алгоритма для частного случая

Как мы видим, код достаточно простой. Если массив содержит только 2 элемента, то обработка не требуется, поэтому функция заканчивает работу (см. строки 3, 4). В противном случае в цикле for выполняются необходимые транспозиции элементов. Предварительно в переменной p сохраняется индекс первого обрабатываемого элемента (строка 5), который совпадает с числом выполняемых транспозиций.

В результате работы программы на консоль выводится следующий текст:

Как видим, массив, состоящий из 16 элементов, был обработан корректно.

Рекурсивный алгоритм для исходной задачи

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

В процессе модификации уже готового алгоритма нам нужно решить две проблемы.

Решение первой проблемы заключается в дополнении массива, состоящего из нечётного числа элементов, одним «фиктивным» элементом. В итоге, функция transform() всегда будет получать для обработки массив из чётного числа элементов.

Опишем принцип, по которому происходит дополнение. Понятно, что нечётные массивы образуются парами после разбиения массива, имеющего чётное, но не делящееся на 4 число элементов, на две равные части. Так вот, массив, содержащий элементы из первой половины исходного массива, нужно дополнить фиктивным элементом справа, а массив, содержащий элементы из второй половины, нужно дополнить фиктивным элементом слева.

Далее массивы, имеющие, благодаря фиктивным элементам, чётное число элементов, подвергаются дальнейшей обработке. Заметим, что, поскольку она никогда не затрагивает крайних элементов, то фиктивные элементы в ходе обработки перемещаться не буду.

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

Продемонстрируем работу новой версии алгоритма на примере обработки массива, состоящего из 10 элементов. Схема обработки приведена ниже.

Схема обработки 10-элементного массива

Как мы видим, вторая проблема возникает ещё перед первым шагом. Решение её продемонстрировано посредством прямоугольной пунктирной рамки, охватывающей 4 элемента, которые на первом шаге будут перемещены. Разбиение на 4 части проводится таким образом, что первая и четвёртая включают в себя по 3 элемента, а вторая и третья — по 2.

После выполнения первого шага возникает уже первая проблема: полумассивы содержат по 5 элементов. Она решается введением двух фиктивных элементов, обозначенных на схеме кружками с крестиками внутри.

В ходе выполнения второго шага снова уже понятным образом решается вторая проблема. После реализации второго шага мы приходим к необходимости обработки 4-х подмассивов по 3 элемента в каждом. Снова прибегаем к дополнению этих массивов 4-мя фиктивными элементами.

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

Реализация алгоритма для общего случая

Изменим функцию transform() таким образом, чтобы она работала с массивами любых чётных размеров. Главный вопрос, который может волновать читателя — «Каким образом вводить в массив фиктивные элементы?». Ответ на него очень прост: никаких фиктивных элементов в массив мы добавлять не будем. Роль фиктивных элементов в подмассивах будут играть соседние по отношению к соответствующим крайним элементам этих подмассивов элементы, принадлежащие исходному массиву. Фактически, мы будем просто «расширять» подмассивы в ту или иную сторону. Ни к каким неприятным последствиям такой подход не приведёт, поскольку фиктивные элементы, как мы помним, в ходе выполнения алгоритма никуда не перемещаются.

Если n нечётно, то в цикле for начальное значение переменной цикла i устанавливается на единицу большим, чем целая часть от n / 2. Таким образом решается вторая проблема, описанная в предыдущем размере.

Для решения первой проблемы (опять же, при нечётном n) мы, во-первых, на единицу увеличиваем размер массивов, который будет передаваться в функцию transform() при двух рекурсивных вызовах (см. строку 12). Во-вторых, мы смещаем левую границу второго массива на один элемент влево (см. строку 16 и ср. с 15-й строкой предыдущей версии). Правая граница первого массива и так будет смещена на один элемент вправо благодаря увеличению размера массива на единицу.

Выполнение тестовой программы приводит к следующему выводу на консоль:

С обработкой массива из 10 элементов наша программа справилась успешно. Читатель, при желании, сам сможет протестировать работу программы при других значениях размера массива.

А решена ли задача?

Итак, алгоритм, выполняющий необходимые перестановки элементов массива, построен и реализован. Но, чтобы ответить на вопрос, вынесенный в заголовок раздела, нам нужно понять, выполнены ли требования, касающиеся сложности алгоритма и размера дополнительной памяти.

Что касается сложности, то было показано, что для количества элементов массива, являющегося степенью двойки, она представляет собой O(n lnn). Можно показать, что то же утверждение будет справедливо и для произвольного чётного количества элементов. Таким образом, требование к сложности алгоритма выполнено.

Обратимся к самому первому примеру — обработке 16-элементного массива. Максимальное количество одновременно запущенных на выполнение экземпляров функции transform() (назовём его глубиной рекурсии) совпадает с количеством шагов алгоритма; в данном случае оно равна 3.

Итак, наше решение имеет сложность O(n ln n) и задействует дополнительную память объёмом O(ln n). Получить решение, имеющее ту же сложность, но использующее дополнительную память, объём которой не зависит от n, не удалось. Возможно, существует решение, принципиально отличающееся от предложенного мною, удовлетворяющее всем требованиям задачи. А можно ли переделать рекурсивную функцию в нерекурсивную, т. е. реализующую наш алгоритм посредством итераций, причём такую, которая не задействует память, объём которой зависит от n? На этот вопрос у меня ответа нет.

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

Добавлю, что первый вариант функции transform() (работающий только для случаев m = 2 k ) я смог бы переделать в приемлемый (т. е. не потребляющий память, зависящую от n) итерационный. Но как переделать второй, «универсальный» вариант, я пока не знаю.

Если в дальнейшем мне удастся улучшить полученное решение, то статья будет обновлена. А кто знает, может улучшенное решение предложит читатель? Если это случится, то я буду очень рад!

Источник