Reflections on algorithms and methods. Presentation of the full algorithm for generating combinations + placements with repetition
This article contains a number of observations on the problems of algorithmization, error minimization, understanding and studying someone else's code, as well as discourse on the complete presentation of algorithms and a small experiment.
We cannot do without the discovery of America: the complete algorithm is the sequence of operations with objects carried out with a pen on paper. A complete description is every step described in natural language, possibly with the use of additional mathematical notation, but only as an auxiliary one. Thus, a complete description is not a formula, and even not yet pseudocode, and, moreover, not a block diagram. From this obvious thesis follows the same very simple, but important thing - the understanding of the implementation of even a rather simple algorithm can be complicated by its shortening or brevity of the formula. In this regard, I really liked the opinion of Herb Wilf that “the formula is in fact an algorithm”, reprinted in this article by Igor Pak. It is possible that the representation of the same algorithms in the form of different formulas and the observation of the intrinsic perception of these representations may shed light on why we understand some algorithms better and others worse.
I noticed several times how often algorithms are copied from language to language purely mechanically. Probably, this may be good in commercial development, when there is no particular time to delve into each step, but only need to quickly get the result in the right language, but for educational purposes, this method is not very suitable.
Having observed myself, I noticed that there are situations when you look at someone else's code and seem to understand the algorithm, you know the language in which it is implemented, but you do not see all the steps. The author has thought through an algorithm for himself, reduced as much as possible and thus actually hid the step-by-step implementation for other programmers, whose attention is often more focused on the means of implementation, and all efforts are directed to finding analogues of these tools necessary for transcoding to the language they know.
')
Thus, the implementation and brief formal description of the algorithm sometimes looks like a cipher, which is immediately understandable only to the author. As for the description of algorithms in natural language, then, probably, the solution to the complexity sometimes lies in the author’s language, as in the description, each relies on his knowledge and understanding of terminology and uses the set and combination of speech tools with which he used to operate. The conclusion I made for myself as a result of studying some algorithms and observing the translation from language to language is that the perception of formulas and algorithms can be a topic for a whole series of very serious research involving developments from completely different areas of human activity.
Of course, implementations of, for example, complete combinatorial algorithms may work several times slower and may be more confusing and ugly than their reduced counterparts. In my opinion, such step-by-step implementations can serve as an instrument of a kind of reverse engineering, when you need to get code that is not mechanically rewritten from language to language, and an understanding of all steps, which, by the way, can serve as a way to understand all abbreviations in faster and shorter counterparts.
Modification of the representation of the algorithm combinations without repetitions
It is no secret that when combining on paper, many combinatorial algorithms seem fairly simple. For example, the algorithm for generating combinations without repetitions (or combinations without repetitions — they differ by at least one element) can be derived almost directly without much understanding, in fact, intuitively. I, however, when writing out all combinations for n = 5 to k = 3 on a sheet, made the same mistake a couple of times, ignoring one of the numbers and got the wrong result; This led me to believe that the presentation of the algorithm on paper should be carried out more systematically, with maximum visualization, with a large number of checks when moving from one step to another, otherwise what can be implemented in a few minutes can be stretched for several hours or even days.
Briefly, the algorithm for generating combinations is formulated as follows: “... in the current combination, we find the rightmost element, which has not yet reached its maximum value; then we will increase it by one, and assign the smallest values ​​to all subsequent elements. ”
A source.
Neither the description nor the implementation is very clear to me, so I decided to complicate things a little and add a few additional steps in order to compensate for my inattention to the numbers and make the description more detailed.
Using this algorithm turns out to be more time consuming, but storing an additional array avoids attention errors and makes more concise implementations understandable. As a result, after the algorithm was decomposed into a larger number of steps, I managed to encode it almost immediately.
However, I have to warn you that the implementation is not on paper, but in a language, for example, in PHP, can seem very confusing. But, nevertheless, formally the algorithm works correctly.
Step-by-step code operation (interval between frames 20 sec.)
Add
Interestingly, this algorithm is quite easily modified into the algorithm for generating combinations
with repetitions. To do this, it is enough to specify arrays C and B in another way, after removing duplicate values, add element N to C on each pass. Instead of sorting array B in ascending order, it is enough to fill array B after element K with the same element once enlarged.
Addition. 05.06.2017
This algorithm can also be used to generate placements without repetitions or with repetitions. To generate all arrangements with repetitions, we generate all combinations and for each combination all permutations. The permutation algorithm modified for this problem is given from the previous article:
Lyrical and practical addition
After writing this article, I was in the library to them. Lenin with the volume “Works in non-mathematics” (Vol. I) V.A. Ouspensky, who left such lines in the chapter on Wittgenstein, quoting him himself: “Activities, activities and again activities are Wittgenstein's credo. For him, the process is more important than the result. "I am not discovering the result, but the way in which it is achieved." ". V.A. Uspensky (Wittgenstein).
Post Scriptum
I published my last article about the generation of combinations prematurely, without noticing several errors at once, so I apologize for my haste. The implementations of non-recursive and recursive algorithms for generating combinations in different languages ​​were discovered by me on the site rosettacode.org. There is also a realization of the algorithm from the book Lipsky.
What do I understand as a complete description of the algorithm and why it may be necessary?
We cannot do without the discovery of America: the complete algorithm is the sequence of operations with objects carried out with a pen on paper. A complete description is every step described in natural language, possibly with the use of additional mathematical notation, but only as an auxiliary one. Thus, a complete description is not a formula, and even not yet pseudocode, and, moreover, not a block diagram. From this obvious thesis follows the same very simple, but important thing - the understanding of the implementation of even a rather simple algorithm can be complicated by its shortening or brevity of the formula. In this regard, I really liked the opinion of Herb Wilf that “the formula is in fact an algorithm”, reprinted in this article by Igor Pak. It is possible that the representation of the same algorithms in the form of different formulas and the observation of the intrinsic perception of these representations may shed light on why we understand some algorithms better and others worse.
I noticed several times how often algorithms are copied from language to language purely mechanically. Probably, this may be good in commercial development, when there is no particular time to delve into each step, but only need to quickly get the result in the right language, but for educational purposes, this method is not very suitable.
Having observed myself, I noticed that there are situations when you look at someone else's code and seem to understand the algorithm, you know the language in which it is implemented, but you do not see all the steps. The author has thought through an algorithm for himself, reduced as much as possible and thus actually hid the step-by-step implementation for other programmers, whose attention is often more focused on the means of implementation, and all efforts are directed to finding analogues of these tools necessary for transcoding to the language they know.
')
Thus, the implementation and brief formal description of the algorithm sometimes looks like a cipher, which is immediately understandable only to the author. As for the description of algorithms in natural language, then, probably, the solution to the complexity sometimes lies in the author’s language, as in the description, each relies on his knowledge and understanding of terminology and uses the set and combination of speech tools with which he used to operate. The conclusion I made for myself as a result of studying some algorithms and observing the translation from language to language is that the perception of formulas and algorithms can be a topic for a whole series of very serious research involving developments from completely different areas of human activity.
Do you need implementations of complete algorithms ?!
Of course, implementations of, for example, complete combinatorial algorithms may work several times slower and may be more confusing and ugly than their reduced counterparts. In my opinion, such step-by-step implementations can serve as an instrument of a kind of reverse engineering, when you need to get code that is not mechanically rewritten from language to language, and an understanding of all steps, which, by the way, can serve as a way to understand all abbreviations in faster and shorter counterparts.
Modification of the representation of the algorithm combinations without repetitions
It is no secret that when combining on paper, many combinatorial algorithms seem fairly simple. For example, the algorithm for generating combinations without repetitions (or combinations without repetitions — they differ by at least one element) can be derived almost directly without much understanding, in fact, intuitively. I, however, when writing out all combinations for n = 5 to k = 3 on a sheet, made the same mistake a couple of times, ignoring one of the numbers and got the wrong result; This led me to believe that the presentation of the algorithm on paper should be carried out more systematically, with maximum visualization, with a large number of checks when moving from one step to another, otherwise what can be implemented in a few minutes can be stretched for several hours or even days.
Further, my experiment is the presentation of the full algorithm for sorting combinations.
Briefly, the algorithm for generating combinations is formulated as follows: “... in the current combination, we find the rightmost element, which has not yet reached its maximum value; then we will increase it by one, and assign the smallest values ​​to all subsequent elements. ”
A source.
Neither the description nor the implementation is very clear to me, so I decided to complicate things a little and add a few additional steps in order to compensate for my inattention to the numbers and make the description more detailed.
Description
At the entrance, the array A = 123456 (for example), sorted in ascending order; N = 6 (number of characters in the array); let's say K = 3 ,.
Before entering the loop, the input array is proposed to be divided into two - B and C, B stores values ​​from 1 element (inclusive) to K (inclusive) and everything else in C, that is, B [123] and C [456].
1) In the outer loop, the element is searched at the position K in B, i.e. B [K], the search for an element larger by one in the array C and exchange. Output on display.
2) Further, the condition - if B [K] is equal to N - the last element of the array, then the search cycle for the element to the left of K is started, for which in the array C there is a larger one. If the index reaches 0 and there are no such elements, the algorithm ends.
3) If an element in C is found, then its index is searched in order to further reduce the element in C by one, and the element in B is increased by one. Then array B is split into two (without this, see the abbreviated version); before and after the current item. Everything after the current element is transferred to array C.
Array B is increased to an index K in ascending order, and excess elements are removed from array C. The nested loop ends. Operations are repeated again.
Using this algorithm turns out to be more time consuming, but storing an additional array avoids attention errors and makes more concise implementations understandable. As a result, after the algorithm was decomposed into a larger number of steps, I managed to encode it almost immediately.
However, I have to warn you that the implementation is not on paper, but in a language, for example, in PHP, can seem very confusing. But, nevertheless, formally the algorithm works correctly.
A complete non-recursive algorithm for generating combinations without repetitions. Php
<?php $a=array(1,2,3,4,5); $k=3; $n=5; $c=array_splice($a, $k); $b=array_splice($a, 0, $k); $j=$k-1; print_r($b); while (1) { if (in_array($b[$j]+1, $c)) { $m=array_search($b[$j]+1,$c); if ($m!==false) $c[$m]-=1; $b[$j]=$b[$j]+1; print_r($b); } if ($b[$k-1]==$n) { $i=$k-1; while ($i >= 0) { if ($i == 0 && !in_array($b[$i]+1, $c)) { break 2; } if (in_array($b[$i]+1, $c)) { $m=array_search($b[$i]+1,$c); if ($m!==false) $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $f=array_splice($b, $i+1); $b=array_splice($b, 0, $i+1); $c=array_merge($c,$f); $g=$i; while ($g != $k-1) { $b[$g+1]=$b[$g]+1; $g++; } $c=array_diff($c,$b); print_r($b); break; } $i--; } } } Short version with comments
<?php $a=array(1,2,3,4,5); $k=3; $n=5; $c=array_splice($a, $k); $b=array_splice($a, 0, $k); $j=$k-1; // function printt($b,$k) { $z=0; while ($z < $k) print $b[$z++].' '; print "\n"; } printt ($b,$k); while (1) { // K N $m=array_search($b[$j]+1,$c); if ($m!==false) { $c[$m]-=1; $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ($i == 0 && $b[$i] == $n-$k+1) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$g]+1; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); break; } $i--; } } } ?>
Step-by-step code operation (interval between frames 20 sec.)
Add
Interestingly, this algorithm is quite easily modified into the algorithm for generating combinations
with repetitions. To do this, it is enough to specify arrays C and B in another way, after removing duplicate values, add element N to C on each pass. Instead of sorting array B in ascending order, it is enough to fill array B after element K with the same element once enlarged.
A complete non-recursive algorithm for generating combinations with repetitions. Php
Content
<?php $k=3; $n=5; $c=array(2,3,4,5); $b=array(1,1,1); $j=$k-1; // function printt($b,$k) { $z=0; while ($z < $k) print $b[$z++].' '; print "\n"; } printt ($b,$k); while (1) { // K N if (array_search($b[$j]+1,$c)!==false ) { $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ( $i == 0 && $b[$i] == $n) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$i]; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); array_unshift ($c, $n); break; } $i--; } } } ?>
Addition. 05.06.2017
This algorithm can also be used to generate placements without repetitions or with repetitions. To generate all arrangements with repetitions, we generate all combinations and for each combination all permutations. The permutation algorithm modified for this problem is given from the previous article:
The algorithm for generating all placements with repetitions. Php
<?php set_time_limit(0); // function perm($b) { $a=array_reverse($b); while (1) { print_r($a); print '<br/>'; if ($a ==$b) break; $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=array_merge(array_reverse(array_slice($a, 0, $i)),array_slice($a, $i)); } } // // n $k=5; $n=5; // $c=array(1,2,3,4,5); // b , k $b=array(1,1,1,1,1); $j=$k-1; // function printt($b,$k) { // perm($b); } printt ($b,$k); while (1) { // K N if (array_search($b[$j]+1,$c)!==false ) { $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ( $i == 0 && $b[$i] == $n) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$i]; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); array_unshift ($c, $n); break; } $i--; } } } ?>
Lyrical and practical addition
After writing this article, I was in the library to them. Lenin with the volume “Works in non-mathematics” (Vol. I) V.A. Ouspensky, who left such lines in the chapter on Wittgenstein, quoting him himself: “Activities, activities and again activities are Wittgenstein's credo. For him, the process is more important than the result. "I am not discovering the result, but the way in which it is achieved." ". V.A. Uspensky (Wittgenstein).
Post Scriptum
I published my last article about the generation of combinations prematurely, without noticing several errors at once, so I apologize for my haste. The implementations of non-recursive and recursive algorithms for generating combinations in different languages ​​were discovered by me on the site rosettacode.org. There is also a realization of the algorithm from the book Lipsky.
Source: https://habr.com/ru/post/311934/
All Articles