Permutations without formulas. (PHP code)
Looking through the questions and articles on the Internet, I noticed that this seemingly simple topic poses some difficulty in drawing up the algorithm. I will try to explain as simply as possible to myself and to you the algorithm for generating permutations, or rather, one of the possible ones.
Many articles describing the topic of permutations begin with formulas or theories of general combinatorics. We depart from this canonical principle.
There is a task : it is required to print all the permutations of four numbers:
1, 2, 3, 4.
Solution - first on a piece of paper.
')
1) Let's calculate successively permutations for one element, for - 1.
We write the result:
one
It is equal to one, there is no place to rearrange one element, but we will remember the result, it will come in handy.
2) Calculate the permutations for the two elements - 1 and 2
We write the result:
12
2 1
We have two permutations. All permutations of the spirit of the elements are equal to two. Now we need to calculate for three elements - 1, 2, 3. To do this, take our new number - 3 and substitute it in each row for permutations for two elements.
We will substitute for each row sequentially so that this number - 3 - will be at each position, i.e .: at the end of the line, between each element and at the beginning of the line. Start at the end of the line.
For the first row, we get the result (in the form of a square diagonal matrix):
1 2 3
1 3 2
3 1 2
For the second line, the result is:
2 1 3
2 3 1
3 2 1
We write the result.
3) For the four elements - 1, 2, 3, 4, we will do the same thing as in step two. Take the values ​​obtained earlier and substitute the number 4 for each line at the end, between each element and at the beginning of the line.
Start again from the end:
We get 24 permutations. Easy to check - the factorial of 4 is 24:
four! = 1 * 2 * 3 * 4 = 24
Let us pay attention once again: we take the results found at the previous step, take the number higher by one, substitute this number into each line - pull from the end of the line to the beginning. When this number is in the first position, we take the next line and repeat the actions. We obtain a simple algorithm for permutations in a non-lexicographic order, which can be quickly translated into machine language. The result, by the way, strongly resembles the Gray code for permutations, as well as the Johnson-Trotter algorithm. Although I did not penetrate much, but if it is interesting, then you can read about it by typing “Gray Codes for Permutations” in the search engine.
About copyright
By the way, personally, it came to my mind to pull the numbers along the line after one association from life, this association is associated with weaving bast or basket, when each new ring is formed by pulling a hook or willow twig through each vertical arc.
Fix it all with this sequence of pictures:
And now we will try to implement this algorithm in PHP, we will use files to store values. Create two files with the names 1.txt and 2.txt, in the file 1.txt write the unit.
For some practical tasks, the use of the following is not planned, so let's build more in it:
1. We will read the file 1.txt line by line.
3. Break the loop if the string is empty.
4. The string will be split and stored in an array (explode).
5. Add the following number to it (array_push).
It is an unpleasant fact, but at each iteration of the uppermost cycle we will use array_trim, since in the array, we have an unpredictable character of the blanks.
6. In the while loop, we will only use list to offset the number by string.
7. We will write all the results in the 2.txt file, then delete 1.txt and rename 2.txt to 1.txt, refresh the page, everything is very simple.
The main focus of this article is not on the code below the line that you are currently finishing up, but on the algorithm described above.
Post Scriptum, links and some history.
On the non-recursive lexicographic method (in the dictionary order) of generating permutations, you can see the articles that reveal the meaning of the algorithm of the Indian mathematician of the XIV century Narayana Pandita. Apparently, he is one of the first authors of the non-recursive algorithm.
On the history of combinatorics in different countries:
www.williamspublishing.com/PDF/978-5-8459-1158-2/part.pdf
Permutation methods can be found here:
study.sfu-kras.ru/DATA/docs/Program...rs/gn_trans.htm
To study the issue of permutations in php, I would like to mention this article by comrade tvolf, very useful (Thank you very much):
tvolf.blogspot.ru/2013/09/php.html
Pps
In addition, permutations can be generated using pseudo-random numbers - RANDOM, although it is a long time, but there is still such a way.
And one more way to print all permutations for the number n is to first generate all placements with repetition, and then delete the values ​​in which the characters repeat - this is the easiest to program, but the longest. It is usually not even considered, but it is still there, since (recall) permutations are a special case of placements.
Many articles describing the topic of permutations begin with formulas or theories of general combinatorics. We depart from this canonical principle.
There is a task : it is required to print all the permutations of four numbers:
1, 2, 3, 4.
Solution - first on a piece of paper.
')
1) Let's calculate successively permutations for one element, for - 1.
We write the result:
one
It is equal to one, there is no place to rearrange one element, but we will remember the result, it will come in handy.
2) Calculate the permutations for the two elements - 1 and 2
We write the result:
12
2 1
We have two permutations. All permutations of the spirit of the elements are equal to two. Now we need to calculate for three elements - 1, 2, 3. To do this, take our new number - 3 and substitute it in each row for permutations for two elements.
We will substitute for each row sequentially so that this number - 3 - will be at each position, i.e .: at the end of the line, between each element and at the beginning of the line. Start at the end of the line.
For the first row, we get the result (in the form of a square diagonal matrix):
1 2 3
1 3 2
3 1 2
For the second line, the result is:
2 1 3
2 3 1
3 2 1
We write the result.
3) For the four elements - 1, 2, 3, 4, we will do the same thing as in step two. Take the values ​​obtained earlier and substitute the number 4 for each line at the end, between each element and at the beginning of the line.
Start again from the end:
<1 2 3 4> <1 3 2 4> <3 1 2 4> <2 1 3 4> <2 3 1 4> <3 2 1 4> <1 2 4 3> <1 3 4 2> <3 1 4 2> <2 1 4 3> <2 3 4 1> <3 2 4 1> <1 4 2 3> <1 4 3 2> <3 4 1 2> <2 4 1 3> <2 4 3 1> <3 4 2 1> <4 1 2 3> <4 1 3 2> <4 3 1 2> <4 2 1 3> <4 2 3 1> <4 3 2 1> We get 24 permutations. Easy to check - the factorial of 4 is 24:
four! = 1 * 2 * 3 * 4 = 24
Let us pay attention once again: we take the results found at the previous step, take the number higher by one, substitute this number into each line - pull from the end of the line to the beginning. When this number is in the first position, we take the next line and repeat the actions. We obtain a simple algorithm for permutations in a non-lexicographic order, which can be quickly translated into machine language. The result, by the way, strongly resembles the Gray code for permutations, as well as the Johnson-Trotter algorithm. Although I did not penetrate much, but if it is interesting, then you can read about it by typing “Gray Codes for Permutations” in the search engine.
About copyright
By the way, personally, it came to my mind to pull the numbers along the line after one association from life, this association is associated with weaving bast or basket, when each new ring is formed by pulling a hook or willow twig through each vertical arc.
Fix it all with this sequence of pictures:
And now we will try to implement this algorithm in PHP, we will use files to store values. Create two files with the names 1.txt and 2.txt, in the file 1.txt write the unit.
For some practical tasks, the use of the following is not planned, so let's build more in it:
1. We will read the file 1.txt line by line.
3. Break the loop if the string is empty.
4. The string will be split and stored in an array (explode).
5. Add the following number to it (array_push).
It is an unpleasant fact, but at each iteration of the uppermost cycle we will use array_trim, since in the array, we have an unpredictable character of the blanks.
6. In the while loop, we will only use list to offset the number by string.
7. We will write all the results in the 2.txt file, then delete 1.txt and rename 2.txt to 1.txt, refresh the page, everything is very simple.
The main focus of this article is not on the code below the line that you are currently finishing up, but on the algorithm described above.
<?php $handle = fopen("1.txt", "r"); $handle2 = fopen("2.txt", "w+"); while (!feof($handle)) { $ar = array(); $line = fgets($handle); if ($line == '') { break; } $ar = explode('.', $line); $c = count($ar); array_push($ar, $c + 1); $c+= 1; $ar = array_map('trim', $ar); echo '<br />'; $s = implode('.', $ar); echo $s; fwrite($handle2, "$s\r\n"); while ($c != 1) { $c--; list($ar[$c-1], $ar[$c]) = array( $ar[$c], $ar[$c-1] ); echo '<br />'; $s = implode('.', $ar); echo $s; fwrite($handle2, "$s\r\n"); } } fclose($handle); fclose($handle2); unlink("1.txt"); rename("2.txt", "1.txt"); ?> Post Scriptum, links and some history.
On the non-recursive lexicographic method (in the dictionary order) of generating permutations, you can see the articles that reveal the meaning of the algorithm of the Indian mathematician of the XIV century Narayana Pandita. Apparently, he is one of the first authors of the non-recursive algorithm.
On the history of combinatorics in different countries:
www.williamspublishing.com/PDF/978-5-8459-1158-2/part.pdf
Permutation methods can be found here:
study.sfu-kras.ru/DATA/docs/Program...rs/gn_trans.htm
To study the issue of permutations in php, I would like to mention this article by comrade tvolf, very useful (Thank you very much):
tvolf.blogspot.ru/2013/09/php.html
Pps
In addition, permutations can be generated using pseudo-random numbers - RANDOM, although it is a long time, but there is still such a way.
And one more way to print all permutations for the number n is to first generate all placements with repetition, and then delete the values ​​in which the characters repeat - this is the easiest to program, but the longest. It is usually not even considered, but it is still there, since (recall) permutations are a special case of placements.
Source: https://habr.com/ru/post/260111/
All Articles