October 6, 2016 at 17:32Reflections on algorithms and methods. Presentation of the complete algorithm for generating combinations + placements with repetition
This article contains a number of observations regarding algorithmic problems, minimizing errors, understanding and studying someone else's code, as well as discussions about the complete presentation of algorithms and a small experiment.
You can’t do without discovering America: a complete algorithm is the sequence of actions on objects that is 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 ancillary. Thus, a full description is not a formula and not even a pseudo-code, and moreover, not a block diagram. From this obvious thesis, the same very simple, but important thing follows - understanding the implementation of even a fairly simple algorithm can be hampered by its reduction or brevity of the formula. In this regard, I really liked the opinion of Herb Wilf that “the formula is actually an algorithm”, reprinted in this articleIgor Pak. Perhaps the presentation of the same algorithms in the form of different formulas and observation of their own perception of these representations can shed light on why some algorithms we understand better and others worse.
I have noticed several times how often algorithms are copied from language to language purely mechanically. Probably, this can be good in commercial development, when there is not much time to delve into each step, but just 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 thought out an algorithm for himself, minimized it as much as possible, and thus virtually hid the step-by-step implementation for other programmers, whose attention is often paid more to implementation tools, and all efforts are aimed at finding analogues of these tools that are necessary for transcoding into a language they know.
Thus, the implementation and a brief formal description of the algorithm sometimes looks like a cipher, immediately understandable only to the author. As for the description of algorithms in a natural language, probably the answer to the complexity is sometimes in the author’s language itself, since in the description everyone relies on his knowledge and understanding of terminology and uses the set and combination of speech tools that he is used to operating on. The conclusion that I made for myself as a result of studying some algorithms and observing the translation from one language to another is that the perception of formulas and algorithms can be a topic for a series of very serious studies involving developments from completely different areas of human activity.
Of course, implementations, for example, of complete combinatorial algorithms can work many times slower and can be more confusing and ugly than their shortened 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 not mechanically rewritten code from one language to another, but an understanding of all the steps, which, by the way, in the future can serve as a way to understand all abbreviations and ornateness in faster and shorter counterparts.
Modification of the representation of the combination algorithm without repetition
It's no secret that when printed out on paper, many combinatorial algorithms seem quite simple. For example, the algorithm for generating combinations without repetitions (or combinations without repetitions - differ by at least one element) can be deduced almost immediately without much understanding, actually intuitively. True, when writing out all the combinations for n = 5 for k = 3 on the sheet, I made the same mistake a couple of times, ignoring one of the numbers and got the wrong result; this led me to think 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 that has not yet reached its greatest value; then we’ll 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 bit and add a few additional steps, in order to compensate for my inattention to numbers and make the description more detailed.
Using this algorithm turns out to be more time-consuming, but storing an additional array avoids attention-related errors and makes more concise implementations understandable. As a result, after decomposing the algorithm into a larger number of steps, I managed to encode it almost immediately.
However, I must warn you that the implementation is not on paper, but in a language, for example, in PHP, it may seem very confusing. But, nevertheless, formally, the algorithm works correctly.
Step-by-step operation of the code (the interval between frames is 20 seconds).
Adding
It is interesting that this algorithm is quite easily modified into an algorithm for generating combinations
with repetitions. To do this, it is enough to specify arrays C and B in a different way, after deleting duplicate values, add an element with number N to C at each pass. Instead of sorting array B in ascending order, it is enough to fill array B after element K with the same enlarged element once.
Addition. 06/05/2017
This algorithm can also be used to generate placements without repetitions or with repetitions. To generate all placements with repetitions, we generate all combinations and for each combination all permutations. The permutation algorithm modified for this task is given from the previous article:
Lyric-practical addition.
After writing this article, I ended up in the library to them. Lenin with a volume of "Transactions in Non-Mathematics" (vol. I) V.A. Ouspensky, who in the chapter on Wittgenstein left such lines, quoting himself: “Activity, activity, and again activity — this is Wittgenstein's credo. For him, the process is more important than the result. “I do not discover the result, but the way in which it is achieved.” V.A.Uspensky (Wittgenstein).
Post Scriptum
I published my last article on the generation of combinations prematurely, without noticing several errors at once, so I apologize for my haste. Implementations of non-recursive and recursive combinations generating algorithms in different languages were discovered by me at rosettacode.org. There are also implementations of the algorithm from Lipsky’s book.
What do I mean by a full description of the algorithm and why might this be necessary?
You can’t do without discovering America: a complete algorithm is the sequence of actions on objects that is 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 ancillary. Thus, a full description is not a formula and not even a pseudo-code, and moreover, not a block diagram. From this obvious thesis, the same very simple, but important thing follows - understanding the implementation of even a fairly simple algorithm can be hampered by its reduction or brevity of the formula. In this regard, I really liked the opinion of Herb Wilf that “the formula is actually an algorithm”, reprinted in this articleIgor Pak. Perhaps the presentation of the same algorithms in the form of different formulas and observation of their own perception of these representations can shed light on why some algorithms we understand better and others worse.
I have noticed several times how often algorithms are copied from language to language purely mechanically. Probably, this can be good in commercial development, when there is not much time to delve into each step, but just 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 thought out an algorithm for himself, minimized it as much as possible, and thus virtually hid the step-by-step implementation for other programmers, whose attention is often paid more to implementation tools, and all efforts are aimed at finding analogues of these tools that are necessary for transcoding into a language they know.
Thus, the implementation and a brief formal description of the algorithm sometimes looks like a cipher, immediately understandable only to the author. As for the description of algorithms in a natural language, probably the answer to the complexity is sometimes in the author’s language itself, since in the description everyone relies on his knowledge and understanding of terminology and uses the set and combination of speech tools that he is used to operating on. The conclusion that I made for myself as a result of studying some algorithms and observing the translation from one language to another is that the perception of formulas and algorithms can be a topic for a series of very serious studies involving developments from completely different areas of human activity.
Are implementations of complete algorithms necessary ?!
Of course, implementations, for example, of complete combinatorial algorithms can work many times slower and can be more confusing and ugly than their shortened 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 not mechanically rewritten code from one language to another, but an understanding of all the steps, which, by the way, in the future can serve as a way to understand all abbreviations and ornateness in faster and shorter counterparts.
Modification of the representation of the combination algorithm without repetition
It's no secret that when printed out on paper, many combinatorial algorithms seem quite simple. For example, the algorithm for generating combinations without repetitions (or combinations without repetitions - differ by at least one element) can be deduced almost immediately without much understanding, actually intuitively. True, when writing out all the combinations for n = 5 for k = 3 on the sheet, I made the same mistake a couple of times, ignoring one of the numbers and got the wrong result; this led me to think 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 a complete combination search algorithm
Briefly, the algorithm for generating combinations is formulated as follows: “... in the current combination we find the rightmost element that has not yet reached its greatest value; then we’ll 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 bit and add a few additional steps, in order to compensate for my inattention to numbers and make the description more detailed.
Description
At the input, array A = 123456 (for example), sorted in ascending order; N = 6 (number of characters in the array); Suppose 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) and to K (inclusive) and in C everything else, that is, B [123] and C [456].
1) In the outer loop, iterates over the element at position K in B, that is, B [K], searches for an element larger by one in the array C and exchanges. Output on display.
2) Further, the condition is that if B [K] is N - the last element of the array, then the search cycle for the element to the left of K starts, for which the array C is greater by one. If the index reaches 0 and there are no such elements, then the algorithm ends.
3) If the element in C is found, then its index is searched to further reduce the element in C by one, and the element in B increases by one. Then the array B is divided into two (you can without it, see abbr. Option); before the current item and after. Everything after the current element is transferred to array C.
Array B increases to index K in ascending order, and excess elements are removed from array C. The nested loop ends. Operations are repeated anew.
Using this algorithm turns out to be more time-consuming, but storing an additional array avoids attention-related errors and makes more concise implementations understandable. As a result, after decomposing the algorithm into a larger number of steps, I managed to encode it almost immediately.
However, I must warn you that the implementation is not on paper, but in a language, for example, in PHP, it may seem very confusing. But, nevertheless, formally, the algorithm works correctly.
A complete non-recursive algorithm for generating combinations without repetitions. Php
= 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--;
}
}
}
Abridged version with comments
= 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 operation of the code (the interval between frames is 20 seconds).
Adding
It is interesting that this algorithm is quite easily modified into an algorithm for generating combinations
with repetitions. To do this, it is enough to specify arrays C and B in a different way, after deleting duplicate values, add an element with number N to C at each pass. Instead of sorting array B in ascending order, it is enough to fill array B after element K with the same enlarged element once.
A complete non-recursive algorithm for generating combinations with repetitions. Php
Content
= 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. 06/05/2017
This algorithm can also be used to generate placements without repetitions or with repetitions. To generate all placements with repetitions, we generate all combinations and for each combination all permutations. The permutation algorithm modified for this task is given from the previous article:
Algorithm for generating all placements with repetitions. Php
';
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--;
}
}
}
?>
Lyric-practical addition.
After writing this article, I ended up in the library to them. Lenin with a volume of "Transactions in Non-Mathematics" (vol. I) V.A. Ouspensky, who in the chapter on Wittgenstein left such lines, quoting himself: “Activity, activity, and again activity — this is Wittgenstein's credo. For him, the process is more important than the result. “I do not discover the result, but the way in which it is achieved.” V.A.Uspensky (Wittgenstein).
Post Scriptum
I published my last article on the generation of combinations prematurely, without noticing several errors at once, so I apologize for my haste. Implementations of non-recursive and recursive combinations generating algorithms in different languages were discovered by me at rosettacode.org. There are also implementations of the algorithm from Lipsky’s book.