January 18, 2016 at 10:12To recursion through permutations
Since we will talk about recursion, I’ll start from the end - with a list of used literature:
1) A good general article about recursion: habrahabr.ru/post/256351 (the author says that recursive code is easier to understand. Honestly, until I'm ready agree with this conclusion, which is why this article appeared).
2) Analysis of recursion at the “lowest level”, there is a lot of assembler, but everything is clear enough: club.shelek.ru/viewart.php?id=205 (I especially advise you to pay attention to the moment where the return address is concerned. This episode greatly facilitates understanding).
Lyrical digression:
This article is so recursive that it was written by the author for the author himself, as well as for those users who, like the author, are not sure of a complete understanding of this topic.
Now let's get started.
Such a code for generating permutations was found by me on Stackovereflow . Mindfulof the law of loss of information that many people like to see everything in one article, I will retype the code here (there is a link, an algorithm from the textbook). In my opinion, the design below has an important feature - it is very easy to understand and take it apart. In addition, the script can be greatly simplified to get to the seed - recursion. Let's start to bite off the code.
Code itself:
The execution time of the original script for n = 9: 4.14418798685.
The source code displays permutations almost in lexicographic order, but I would like it strictly in it.
We proceed to the decomposition.
Bite off the second call to the exchange function - swap
The meaning of the second call is to make two exchanges in one cycle.
But why two counters, boss ?!
The number of cycles from this is not reduced, only the number of operations increases.
Bite off ... and then a miracle! The output of the permutations is now in lexicographic order.
And for one swap call with the same n = 9, the lead time = 2.76783800125.
I note that the difference is noticeable even for n = 8. Excellent!
Why would you bite on which side?
Bite off the function call and send the exchange operation directly to the loop.
But how can it be so ?! But where is it seen that functions take and bite ?!
If you have ever bought a used car in the market, you often could hear the phrase: “Uh, brother, it doesn’t affect speed!”
And no! Still affected. And the article on the second link can shed light on this.
The runtime result of our core has improved. 1.91801601648.
And the code is now completely in the palm of your hand.
Remove the only check from the function. The output will be noticeably larger (a little refrain / repetition will brighten the path to recursion). With n = 9, there are already problems with the output to the browser. And this is only with 986409 cycles. It is appropriate tocall the reminder function to remind about the link to the first article.
But we got to the main thing, to our seed - recursion. Let's see what values the variables i and j take. To this we were selected.
I think the moment with changes in the values of variables is the main difficulty in understanding the recursive permutation algorithm. Remove output and exchange, reduce n to 2.
But how do you understand what happens to variables ?!
We print them in a loop. Add the output i and j to the loop for clarity :
We get the following conclusion:
In which everything immediately becomes clear. One would like to call it a truth table.
Our view, accustomed to cyclic conclusions, “gets entangled in leaves and branches”.
There are only two branches, so we will try to get out.
In fact, everything is not simple, but very simple: where i = 0 is the first branch , i.e. i = 0 j = 0 and i = 0 j = 1 - this is the first function call - our trunk. But since the whole program is recursive, then for n = 2 the output is naturally through the line.
And if n will be more?
Then at first we will see a piece of our trunk (i = 0), and then leaves, leaves, leaves and somewhere through n + x lines our trunk will flash again. On output, this can create confusion.
We also note in the case of permutations that since at the very beginning j takes on the value i, then in the first stages of the program execution the visible transposition of elements does not occur, although the exchange is actually performed.
What is the conclusion of all this?
And the conclusion was already at the end of the article, that the first link at the beginning of this note.:)
As a result
We were able to carry out several tasks: reduce the source script, conduct some speed tests. Return permutations to true order. And, I hope, managed to deal with recursion. It would be possible to draw a recursive tree for clarity, but I will leave this to the reader’s imagination. Finally, I remind you of the second link at the beginning of the note, for a completely irrevocable understanding of recursive permutations, this code can be used as an example when working with the specified material.
The whole algorithm is briefly in the form of animation (we will keep in mind the fact that at one point in time one part of the program is executed - one step. As an auxiliary mnemonics, we can imagine that the "processor pointer" at one point in time is at such and such a point - part of the program. Since a return address is always stored when a function is called again, we can trace how our conditional pointer reaches the first "sheet" - n = 4, and then returns several steps and the loop counter -j increases):
Afterword or small addition
And what about our non-recursive PHP implementation? After a number of significant improvements, an algorithm close to the Narayana Pandita algorithm issued for n = 9 a runtime of 1.76553100348
And I must say that the implementation itself has become quite transparent:
To the question of code simplification methods, in the above implementation, you can remove unnecessary variables:
1) A good general article about recursion: habrahabr.ru/post/256351 (the author says that recursive code is easier to understand. Honestly, until I'm ready agree with this conclusion, which is why this article appeared).
2) Analysis of recursion at the “lowest level”, there is a lot of assembler, but everything is clear enough: club.shelek.ru/viewart.php?id=205 (I especially advise you to pay attention to the moment where the return address is concerned. This episode greatly facilitates understanding).
Lyrical digression:
This article is so recursive that it was written by the author for the author himself, as well as for those users who, like the author, are not sure of a complete understanding of this topic.
Now let's get started.
Such a code for generating permutations was found by me on Stackovereflow . Mindful
Code itself:
Spoiler heading
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.
The execution time of the original script for n = 9: 4.14418798685.
The source code displays permutations almost in lexicographic order, but I would like it strictly in it.
We proceed to the decomposition.
Bite off the second call to the exchange function - swap
The meaning of the second call is to make two exchanges in one cycle.
But why two counters, boss ?!
The number of cycles from this is not reduced, only the number of operations increases.
Bite off ... and then a miracle! The output of the permutations is now in lexicographic order.
And for one swap call with the same n = 9, the lead time = 2.76783800125.
I note that the difference is noticeable even for n = 8. Excellent!
Why would you bite on which side?
Bite off the function call and send the exchange operation directly to the loop.
function permute($str,$i,$n) {
if ($i == $n)
print “$str
”;
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));
But how can it be so ?! But where is it seen that functions take and bite ?!
If you have ever bought a used car in the market, you often could hear the phrase: “Uh, brother, it doesn’t affect speed!”
And no! Still affected. And the article on the second link can shed light on this.
The runtime result of our core has improved. 1.91801601648.
And the code is now completely in the palm of your hand.
Remove the only check from the function. The output will be noticeably larger (a little refrain / repetition will brighten the path to recursion). With n = 9, there are already problems with the output to the browser. And this is only with 986409 cycles. It is appropriate to
But we got to the main thing, to our seed - recursion. Let's see what values the variables i and j take. To this we were selected.
I think the moment with changes in the values of variables is the main difficulty in understanding the recursive permutation algorithm. Remove output and exchange, reduce n to 2.
But how do you understand what happens to variables ?!
We print them in a loop. Add the output i and j to the loop for clarity :
function permute($str,$i,$n) {
for ($j = $i; $j < $n; $j++) {
echo ‘i=’.$i.’ j=’.$j.'
’;
permute($str, $i+1, $n);
}
}
$str = “01”;
permute($str,0,strlen($str));
We get the following conclusion:
i=0 j=0
i=1 j=1
i=0 j=1
i=1 j=1
In which everything immediately becomes clear. One would like to call it a truth table.
Our view, accustomed to cyclic conclusions, “gets entangled in leaves and branches”.
There are only two branches, so we will try to get out.
In fact, everything is not simple, but very simple: where i = 0 is the first branch , i.e. i = 0 j = 0 and i = 0 j = 1 - this is the first function call - our trunk. But since the whole program is recursive, then for n = 2 the output is naturally through the line.
And if n will be more?
Then at first we will see a piece of our trunk (i = 0), and then leaves, leaves, leaves and somewhere through n + x lines our trunk will flash again. On output, this can create confusion.
We also note in the case of permutations that since at the very beginning j takes on the value i, then in the first stages of the program execution the visible transposition of elements does not occur, although the exchange is actually performed.
What is the conclusion of all this?
And the conclusion was already at the end of the article, that the first link at the beginning of this note.:)
As a result
We were able to carry out several tasks: reduce the source script, conduct some speed tests. Return permutations to true order. And, I hope, managed to deal with recursion. It would be possible to draw a recursive tree for clarity, but I will leave this to the reader’s imagination. Finally, I remind you of the second link at the beginning of the note, for a completely irrevocable understanding of recursive permutations, this code can be used as an example when working with the specified material.
The whole algorithm is briefly in the form of animation (we will keep in mind the fact that at one point in time one part of the program is executed - one step. As an auxiliary mnemonics, we can imagine that the "processor pointer" at one point in time is at such and such a point - part of the program. Since a return address is always stored when a function is called again, we can trace how our conditional pointer reaches the first "sheet" - n = 4, and then returns several steps and the loop counter -j increases):
Afterword or small addition
And what about our non-recursive PHP implementation? After a number of significant improvements, an algorithm close to the Narayana Pandita algorithm issued for n = 9 a runtime of 1.76553100348
And I must say that the implementation itself has become quite transparent:
PHP non-recursive permutation algorithm
$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 '
';
}
To the question of code simplification methods, in the above implementation, you can remove unnecessary variables:
PHP non-recursive permutation algorithm
$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";
}
?>