Поскольку речь пойдет о рекурсии, начну с конца — со списка использованной литературы:
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. Отлично!
Чего бы с какой бы стороны еще откусить?
Откусим вызов функции и отправим операции обмена прямо в цикл.
Да как же ж так можно?! Да где же это видано, чтобы функции брали и откусывали?!
Если Вы когда-нибудь покупали подержанный автомобиль на рынке, то часто на свои замечания по поводу состояния машины могли слышать фразу: «Э, брат, на скорость не влияет!»
А вот и нет! Все-таки влияет. И пролить свет на это может статья по второй ссылке.
Результат времени выполнения нашего огрызка улучшился. 1.91801601648.
А код теперь совсем как на ладони.
Уберём единственную проверку из функции. Вывода станет заметно больше, (немножко припевов/повторов скрасит путь к рекурсии). При n = 9 с выводом в браузер уже возникают проблемы. И это всего лишь при 986409 циклах. Здесь уместновызвать функцию напоминания напомнить про ссылку на первую статью.
Но мы добрались до главного, до нашего семечка — рекурсии. Посмотрим, какие значения принимают переменные i и j. К этому мы и подбирались.
Я думаю, момент с изменениями значений переменных и есть основная трудность в понимании рекурсивного алгоритма перестановок. Уберём вывод и обмен, сократим n до 2.
Но как же понять, что происходит с переменными?!
Напечатаем их в цикле. Добавим в цикл для наглядности вывод i и j:
Получим вот такой вывод:
В котором всё сразу становится понятно. Так и хочется назвать это таблицей истинности.
Наш взгляд, привыкший к циклическим выводам, “запутывается в листьях и ветках”.
Только веток у нас всего две, так что постараемся выбраться.
На самом деле все не просто, а очень просто: там где 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
И надо сказать, что сама реализация стала довольно прозрачной:
К вопросу о методах упрощения кода, в приведенной выше реализации можно убрать лишние переменные:
1) Хорошая общая статья о рекурсии: habrahabr.ru/post/256351 (в ней автор говорит, что рекурсивный код легче для восприятия. Честно говоря, пока я не готов согласиться с таким выводом, именно поэтому появилась эта заметка).
2) Разбор работы рекурсии на “самом низком уровне”, тут много ассемблера, но всё достаточно понятно: club.shelek.ru/viewart.php?id=205 (особенно советую обратить внимание на тот момент, где идет речь об адресе возврата. Этот эпизод сильно облегчает понимание).
Лирическое отступление:
Данная статья настолько рекурсивная, что написана автором для самого автора, а также для тех пользователей, которые, как и автор, не уверены в стопроцентном понимании данной темы.
А теперь приступим.
Такой вот код генерации перестановок был найден мной на Stackovereflow. Памятуя
Сам код:
Заголовок спойлера
function permute($str, $i, $n)
{
if ($i == $n) print "$str\n";
else
{
for ($j = $i; $j < $n; $j++)
{
swap($str, $i, $j);
permute($str, $i + 1, $n);
swap($str, $i, $j); // backtrack.
}
}
}
// function to swap the char at pos $i and $j of $str.
function swap(&$str, $i, $j)
{
$temp = $str[$i];
$str[$i] = $str[$j];
$str[$j] = $temp;
}
$str = "0123";
permute($str, 0, strlen($str)); // call the function.
Время выполнения исходного скрипта для 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
И надо сказать, что сама реализация стала довольно прозрачной:
Нерекурсивная реализация алгоритма перестановок на языке PHP
$b="0123456";
$a=strrev($b);
while ($a !=$b) {
$i=1;
while($a[$i] > $a[$i-1]) {
$i++;
}
$j=0;
while($a[$j] < $a[$i]) {
$j++;
}
$c=$a[$j];
$a[$j]=$a[$i];
$a[$i]=$c;
$x=strrev(substr($a, 0, $i));
$y=substr($a, $i);
$a=$x.$y;
print '<br/>';
}
К вопросу о методах упрощения кода, в приведенной выше реализации можно убрать лишние переменные:
Нерекурсивная реализация алгоритма перестановок на языке PHP
<?php
$b="0123";
$a=strrev($b);
while ($a !=$b) {
$i=1;
while($a[$i] > $a[$i-1]) {
$i++;
}
$j=0;
while($a[$j] < $a[$i]) {
$j++;
}
$c=$a[$j];
$a[$j]=$a[$i];
$a[$i]=$c;
$a=strrev(substr($a, 0, $i)).substr($a, $i);
print $a. "\n";
}
?>
