К рекурсии через перестановки

Поскольку речь пойдет о рекурсии, начну с конца — со списка использованной литературы:

1) Хорошая общая статья о рекурсии: habrahabr.ru/post/256351 (в ней автор говорит, что рекурсивный код легче для восприятия. Честно говоря, пока я не готов согласиться с таким выводом, именно поэтому появилась эта заметка).

2) Разбор работы рекурсии на “самом низком уровне”, тут много ассемблера, но всё достаточно понятно: club.shelek.ru/viewart.php?id=205 (особенно советую обратить внимание на тот момент, где идет речь об адресе возврата. Этот эпизод сильно облегчает понимание).

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


А теперь приступим.
Такой вот код генерации перестановок был найден мной на Stackovereflow. Памятуя о законе потери информации о том, что многие любят видеть всё в одной статье, перепечатаю код здесь (ссылка есть, алгоритм из учебника). На мой взгляд нижеприведенная конструкция имеет важную особенность – её очень легко понять и разобрать по кусочкам. Кроме того, скрипт можно значительно упростить, чтобы добраться до семечка – рекурсии. Начнём откусывать от кода.

Сам код:



Время выполнения исходного скрипта для n = 9: 4.14418798685 .
Исходный код выводит перестановки почти в лексикографическом порядке, а хотелось бы строго в нём.
Приступим к декомпозиции.
Откусим второй вызов функции обмена – swap
Смысл второго вызова в том, чтобы за один цикл сделать два обмена.

Но почему два счётчика, шеф?!

Количество циклов от этого не сокращается, только увеличивается количество операций.
Откусываем… и вдруг чудо! Вывод перестановок теперь в лексикографическом порядке.
А для одного вызова swap с тем же n = 9 время выполнения =2.76783800125.
Отмечу, что разница заметна даже для n = 8. Отлично!
Чего бы с какой бы стороны еще откусить?
Откусим вызов функции и отправим операции обмена прямо в цикл.

function permute($str,$i,$n) {

if ($i == $n)
print “$str<br/>”;
else {
for ($j = $i; $j < $n; $j++) {

$temp = $str[$i];
$str[$i] = $str[$j];
$str[$j] = $temp;

permute($str, $i+1, $n);
}
}
}

$str = “123”;
permute($str,0,strlen($str));

Да как же ж так можно?! Да где же это видано, чтобы функции брали и откусывали?!
Если Вы когда-нибудь покупали подержанный автомобиль на рынке, то часто на свои замечания по поводу состояния машины могли слышать фразу: «Э, брат, на скорость не влияет!»
А вот и нет! Все-таки влияет. И пролить свет на это может статья по второй ссылке.
Результат времени выполнения нашего огрызка улучшился. 1.91801601648.
А код теперь совсем как на ладони.

Уберём единственную проверку из функции. Вывода станет заметно больше, (немножко припевов/повторов скрасит путь к рекурсии). При n = 9 с выводом в браузер уже возникают проблемы. И это всего лишь при 986409 циклах. Здесь уместно вызвать функцию напоминания напомнить про ссылку на первую статью.

Но мы добрались до главного, до нашего семечка — рекурсии. Посмотрим, какие значения принимают переменные i и j. К этому мы и подбирались.

Я думаю, момент с изменениями значений переменных и есть основная трудность в понимании рекурсивного алгоритма перестановок. Уберём вывод и обмен, сократим n до 2.

Но как же понять, что происходит с переменными?!
Напечатаем их в цикле. Добавим в цикл для наглядности вывод i и j:

function permute($str,$i,$n) {

for ($j = $i; $j < $n; $j++) {
echo ‘i=’.$i.’ j=’.$j.'<br/>’;

permute($str, $i+1, $n);
 }
}

$str = “01”;
permute($str,0,strlen($str));

Получим вот такой вывод:

i=0 j=0
i=1 j=1
i=0 j=1
i=1 j=1

В котором всё сразу становится понятно. Так и хочется назвать это таблицей истинности.
Наш взгляд, привыкший к циклическим выводам, “запутывается в листьях и ветках”.
Только веток у нас всего две, так что постараемся выбраться.
На самом деле все не просто, а очень просто: там где i =0 – это первая ветка, т.е. i =0 j=0 и i=0 j=1 – это первый вызов функции – наш ствол. Но поскольку вся программа рекурсивная, то при n = 2 вывод естественно через строчку.

А если n будет больше?

Тогда вначале мы увидим кусочек нашего ствола (i=0), а потом листья, листья, листья и где-то через n+x строчек снова мелькнет наш ствол. При выводе это может создать путаницу.
Заметим также в случае с перестановками, что поскольку в самом начале j принимает значение i, то на первых этапах выполнения программы видимой транспозиции элементов не происходит, хотя фактически обмен выполняется.

Какой же из всего этого вывод?
А вывод уже был в конце статьи, что по первой ссылке в начале этой заметки.: )

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

Весь алгоритм кратко в виде анимации ( будем удерживать в голове тот факт, что в один момент времени выполняется один участок программы — один шаг. В качестве вспомогательной мнемоники можно представить себе, что «указатель процессора» в один момент времени находится в такой-то точке — участке программы. Поскольку при новом вызове функции всегда хранится адрес возврата, то можно проследить, как наш условный указатель доходит до первого «листа» — n=4, а потом возвращается на несколько шагов и счётчик цикла -j увеличивается):



Послесловие или небольшое добавление
А что же наша нерекурсивная реализация на PHP? После ряда существенных доработок алгоритм, близкий к алгоритму Нараяны Пандиты, выдал для n =9 время выполнения 1.76553100348
И надо сказать, что сама реализация стала довольно прозрачной:


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