To recursion through permutations
As far as recursion is concerned, I will start from the end - from the list of references:
1) A good general article about recursion: habrahabr.ru/post/256351 (the author says that the recursive code is easier to read. Honestly, until I am ready to agree with this conclusion, this is why this note appeared).
2) Analysis of the work of recursion at the “lowest level”, there is a lot of assembler, but everything is quite clear: club.shelek.ru/viewart.php?id=205 (I especially advise you to pay attention to the point where the return address is involved. 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 the one hundred percent understanding of this topic.
Now let's get started.
Such a permutation generation code was found by me on Stackovereflow . Mindfulof the law of loss of information that many people like to see everything in one article, I rewrite the code here (there is a link, an algorithm from the textbook). In my opinion, the following construction has an important feature - it is very easy to understand and disassemble it in pieces. In addition, the script can be greatly simplified to get to the seed - recursion. Let's start biting off the code.
The code itself:
The execution time of the source script for n = 9: 4.14418798685.
The source code displays permutations almost in lexicographical order, but I would like to strictly in it.
We proceed to decomposition.
Bite off the second call to the swap function.
The meaning of the second call is to make two exchanges in one cycle.
But why two counters, the chief ?!
The number of cycles from this is not reduced, only the number of operations increases.
Bite off ... and suddenly a miracle! Displays permutations are now in lexicographical order.
And for one swap call with the same n = 9 runtime = 2.76783800125.
I note that the difference is noticeable even for n = 8. Excellent!
What from what party still to bite off?
Let's bite the function call and send the exchange operations directly to the loop.
But how is it possible so ?! But where is it seen that the functions were taken and bitten off ?!
If you have ever bought a used car on the market, then you may often hear your comments about the condition of the car: “Eh, brother, it does not affect speed!”
And no! Still affected. And shed light on this article on the second link.
The result of the execution time of our stub improved. 1.91801601648.
And the code is now quite clear.
Remove the single check from the function. The output will be noticeably more (a little chorus / repetition will brighten the path to recursion). When n = 9, problems are already appearing in the browser. And this is only at 986409 cycles. Here it is appropriate tocall the reminder function to remind about the link to the first article.
But we got to the main, 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 the output and exchange, reduce n to 2.
But how to understand what is happening with variables?
Print them in a loop. Add to the loop for clarity output i and j:
We get this conclusion:
In which everything immediately becomes clear. One would like to call it the truth table.
Our view, accustomed to cyclical conclusions, is "entangled in leaves and branches."
We only have 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, 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 the n + x lines our trunk will flash again. When outputting this can create confusion.
We also note in the case of permutations that since at the very beginning j takes the value i, there is no visible transposition of elements at the first stages of the program, although the exchange is actually performed.
What is the conclusion of all this?
And the conclusion was already at the end of the article, which is the first link at the beginning of this note .:)
Eventually
We managed to accomplish several tasks: reduce the original script, conduct some speed tests. Return permutations true order. And, I hope, managed to deal with recursion. It would be possible to draw a recursive tree for clarity, but leave it to the reader's imagination. Finally, let me remind you about the second link at the beginning of the note, for a completely irrevocable understanding of recursive permutations, you can use this code as an example when working with the specified material.
The whole algorithm is briefly in the form of animation (we’ll keep in mind the fact that at one time moment one program section is executed - one step. As an auxiliary mnemonic, you can imagine that the "processor pointer" is at one time - the program section. Since the return address is always stored in the function call, we can see how our conditional pointer reaches the first “sheet” - n = 4, and then goes back several steps and the loop counter -j increases):
Epilogue or small addition
And what about our non-recursive php implementation? After a number of significant improvements, an algorithm close to the algorithm of Narayana Pandita issued for n = 9 execution time 1.76553100348
And I must say that the implementation itself has become quite transparent:
On the question of methods for simplifying the code, in the above implementation, you can remove the extra variables:
1) A good general article about recursion: habrahabr.ru/post/256351 (the author says that the recursive code is easier to read. Honestly, until I am ready to agree with this conclusion, this is why this note appeared).
2) Analysis of the work of recursion at the “lowest level”, there is a lot of assembler, but everything is quite clear: club.shelek.ru/viewart.php?id=205 (I especially advise you to pay attention to the point where the return address is involved. 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 the one hundred percent understanding of this topic.
Now let's get started.
Such a permutation generation code was found by me on Stackovereflow . Mindful
The code itself:
Spoiler header
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 source script for n = 9: 4.14418798685.
The source code displays permutations almost in lexicographical order, but I would like to strictly in it.
We proceed to decomposition.
Bite off the second call to the swap function.
The meaning of the second call is to make two exchanges in one cycle.
But why two counters, the chief ?!
The number of cycles from this is not reduced, only the number of operations increases.
Bite off ... and suddenly a miracle! Displays permutations are now in lexicographical order.
And for one swap call with the same n = 9 runtime = 2.76783800125.
I note that the difference is noticeable even for n = 8. Excellent!
What from what party still to bite off?
Let's bite the function call and send the exchange operations directly to the loop.
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)); But how is it possible so ?! But where is it seen that the functions were taken and bitten off ?!
If you have ever bought a used car on the market, then you may often hear your comments about the condition of the car: “Eh, brother, it does not affect speed!”
And no! Still affected. And shed light on this article on the second link.
The result of the execution time of our stub improved. 1.91801601648.
And the code is now quite clear.
Remove the single check from the function. The output will be noticeably more (a little chorus / repetition will brighten the path to recursion). When n = 9, problems are already appearing in the browser. And this is only at 986409 cycles. Here it is appropriate to
But we got to the main, 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 the output and exchange, reduce n to 2.
But how to understand what is happening with variables?
Print them in a loop. Add to the loop for clarity output i and 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)); We get this 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 the truth table.
Our view, accustomed to cyclical conclusions, is "entangled in leaves and branches."
We only have 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, 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 the n + x lines our trunk will flash again. When outputting this can create confusion.
We also note in the case of permutations that since at the very beginning j takes the value i, there is no visible transposition of elements at the first stages of the program, although the exchange is actually performed.
What is the conclusion of all this?
And the conclusion was already at the end of the article, which is the first link at the beginning of this note .:)
Eventually
We managed to accomplish several tasks: reduce the original script, conduct some speed tests. Return permutations true order. And, I hope, managed to deal with recursion. It would be possible to draw a recursive tree for clarity, but leave it to the reader's imagination. Finally, let me remind you about the second link at the beginning of the note, for a completely irrevocable understanding of recursive permutations, you can use this code as an example when working with the specified material.
The whole algorithm is briefly in the form of animation (we’ll keep in mind the fact that at one time moment one program section is executed - one step. As an auxiliary mnemonic, you can imagine that the "processor pointer" is at one time - the program section. Since the return address is always stored in the function call, we can see how our conditional pointer reaches the first “sheet” - n = 4, and then goes back several steps and the loop counter -j increases):
Epilogue or small addition
And what about our non-recursive php implementation? After a number of significant improvements, an algorithm close to the algorithm of Narayana Pandita issued for n = 9 execution time 1.76553100348
And I must say that the implementation itself has become quite transparent:
Non-recursive implementation of the PHP 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 '<br/>'; } On the question of methods for simplifying the code, in the above implementation, you can remove the extra variables:
Non-recursive implementation of the PHP permutation algorithm
<?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"; } ?> Source: https://habr.com/ru/post/275331/
All Articles