Non-recursive algorithm for generating all partitions and compositions of an integer
Hi, Habr! Suddenly again I wanted to write here! Since there was time on the weekend, I again decided to play around with the algorithmization and wrote this article here. I even wanted to send to some peer-reviewed journal, but I cannot assess the triviality / non-triviality of this material, since programming is just my hobby and that is episodic, therefore, as usual, I apologize in advance if everything is too simple and painful familiar.
Thanks to the administration of Habr for responsiveness and lightning speed when restoring an account!
So, the fruits of long effort ...
Non-recursive algorithm for generating all partitions of an integer in the lexicographic
the order when all elements are arranged in descending order is alternative; at
The Internet provides several ways to generate combinatorial data.
objects, however, as is true of other combinatorial algorithms,
implementations are reduced to two types - non-recursive and recursive. You can often meet
implementations that do not take into account the order of output of objects or carry out
output on the principle of splitting numbers.
')
The following implementation works in the opposite way: the initial number is initially divided into units, the algorithm works until the number in the zero index of the array becomes equal to the sum of the initial number. A feature of this algorithm is that it is extremely easy to understand, but this does not deprive it of some specific features:
1) The first object is simply displayed on the screen at the very beginning, so it is moved beyond the limits of the cycles, in fact it is initializing;
2) There are several ways to implement unit transfer, which can both simplify the code and make it more confusing;
3) This non-recursive implementation can serve as a good example to explain the generation of combinatorial objects on multiple processors, after minor modifications. To divide generation into processors, it is enough: a) to determine the element by its number and make it initializing; b) determine the time to stop work. For example, if the number of objects generated on a single processor is known, then it is enough to enter another incremental variable in the upper cycle and change the condition for exiting the uppermost cycle when the required number is reached.
The PHP code is shown only to demonstrate the correctness of the algorithm and may contain unnecessary language features that add redundancy implementations.
Algorithm Description
It is given: the initial array in the form of units - (1,1,1,1,1).
Steps
0) If we get the sum (in the case of implementation below, if the zero index is equal to the sum of the number), then the algorithm stops.
1) Moving along the array from left to right, look in array A for the first minimal element - x,
the last element is not taken into account (does not participate in the search for the minimum).
2) Move the unit from the end (last element) to the minimum element x found
(equivalent to increasing x by one and decreasing by one the last element).
3 ) If in array A there is zero - 0, then delete the last element.
4) Decompose the sum of all elements after the changed element - x - into units.
Example
A = (1,1,1,1,1)
2,1,1,1
2,2,1
3.1,1
Update:
The operation with search and delete 0 in the array is superfluous (since array_splice is used, and then the new array filling), as was correctly noted in the comment by the dev26 member
findings
I would like to share one observation at the end, I tried for a very long time to understand why some algorithms are immediately clear and easy to encode, while others make you suffer ... and sometimes for a long time. I should note that I managed to encode this algorithm almost immediately, but only after I received an unambiguously clear description of each step. And there is an important point, to understand the algorithm and to describe - the tasks of one another are not easier. However, in the algorithmization and compilation of the description, it is especially important what verbs describe the actions in the algorithm - this (subjectively) ultimately can also affect the final implementation.
Literature
[1] Donald E. Knuth. The Art of Programming. Vol. 4. 2008.
[2] Dennis Ritchie and Brian Kernighan. The C Programming Language. 1978
[3] Aleksandr Shen. Algorithms and Programming: Problems and Solutions.
[4] en.wikipedia.org/wiki/The breaking up
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
PS Despite the list of references, the algorithm had to be displayed anew.
Another addition:
The removal of the first element from the cycles with this approach is valid both for generating partitions and for generating combinations and permutations. In principle, this approach (although somewhat redundant in implementations) is quite generalized for the generation of other combinatorial objects.
UPDATE
The algorithm of partitions in conjunction with the algorithm of permutations allows you to generate all the compositions of a number. The idea is simple: for each partition, the function of generating all permutations for this partition is called.
Thanks to the administration of Habr for responsiveness and lightning speed when restoring an account!
So, the fruits of long effort ...
Non-recursive algorithm for generating all partitions of an integer in the lexicographic
the order when all elements are arranged in descending order is alternative; at
The Internet provides several ways to generate combinatorial data.
objects, however, as is true of other combinatorial algorithms,
implementations are reduced to two types - non-recursive and recursive. You can often meet
implementations that do not take into account the order of output of objects or carry out
output on the principle of splitting numbers.
')
The following implementation works in the opposite way: the initial number is initially divided into units, the algorithm works until the number in the zero index of the array becomes equal to the sum of the initial number. A feature of this algorithm is that it is extremely easy to understand, but this does not deprive it of some specific features:
1) The first object is simply displayed on the screen at the very beginning, so it is moved beyond the limits of the cycles, in fact it is initializing;
2) There are several ways to implement unit transfer, which can both simplify the code and make it more confusing;
3) This non-recursive implementation can serve as a good example to explain the generation of combinatorial objects on multiple processors, after minor modifications. To divide generation into processors, it is enough: a) to determine the element by its number and make it initializing; b) determine the time to stop work. For example, if the number of objects generated on a single processor is known, then it is enough to enter another incremental variable in the upper cycle and change the condition for exiting the uppermost cycle when the required number is reached.
The PHP code is shown only to demonstrate the correctness of the algorithm and may contain unnecessary language features that add redundancy implementations.
Algorithm Description
It is given: the initial array in the form of units - (1,1,1,1,1).
Steps
0) If we get the sum (in the case of implementation below, if the zero index is equal to the sum of the number), then the algorithm stops.
1) Moving along the array from left to right, look in array A for the first minimal element - x,
the last element is not taken into account (does not participate in the search for the minimum).
2) Move the unit from the end (last element) to the minimum element x found
(equivalent to increasing x by one and decreasing by one the last element).
4) Decompose the sum of all elements after the changed element - x - into units.
Example
A = (1,1,1,1,1)
2,1,1,1
2,2,1
3.1,1
PHP Algorithm Code
<?php /* . Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1, 1, 1 ); $n = count($a); while (1) { /* . Print end exit.*/ print_r($a); if ($a[0] == $n) break; /* . First element of our dynamic array*/ $first_elem = $a[0]; /* . Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /* . Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /* "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /* . We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /* . Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /* . Unset min_elem.*/ unset($min_elem); } ?> Update:
The operation with search and delete 0 in the array is superfluous (since array_splice is used, and then the new array filling), as was correctly noted in the comment by the dev26 member
findings
I would like to share one observation at the end, I tried for a very long time to understand why some algorithms are immediately clear and easy to encode, while others make you suffer ... and sometimes for a long time. I should note that I managed to encode this algorithm almost immediately, but only after I received an unambiguously clear description of each step. And there is an important point, to understand the algorithm and to describe - the tasks of one another are not easier. However, in the algorithmization and compilation of the description, it is especially important what verbs describe the actions in the algorithm - this (subjectively) ultimately can also affect the final implementation.
Literature
[1] Donald E. Knuth. The Art of Programming. Vol. 4. 2008.
[2] Dennis Ritchie and Brian Kernighan. The C Programming Language. 1978
[3] Aleksandr Shen. Algorithms and Programming: Problems and Solutions.
[4] en.wikipedia.org/wiki/The breaking up
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
PS Despite the list of references, the algorithm had to be displayed anew.
Another addition:
The removal of the first element from the cycles with this approach is valid both for generating partitions and for generating combinations and permutations. In principle, this approach (although somewhat redundant in implementations) is quite generalized for the generation of other combinatorial objects.
UPDATE
The algorithm of partitions in conjunction with the algorithm of permutations allows you to generate all the compositions of a number. The idea is simple: for each partition, the function of generating all permutations for this partition is called.
Generation of compositions. Php
<?php /* . Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1 ); $n = count($a); $h=0; while (1) { /* . Permutations and exit.*/ permute($a, $h); if ($a[0] == $n) break; /* . First element of our dynamic array*/ $first_elem = $a[0]; /* . Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /* . Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /* "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /* . We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /* . Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /* . Unset min_elem.*/ unset($min_elem); } /* . Permutations function.*/ function permute($b,&$h) { /* . * . * Here we make a copy and reverse our array. It is necessary to * stop the algorithm.*/ $a = $b; $b = array_reverse($b); while (1) { /* . Here we print and exit.*/ print_r($a); print "\n"; if ($a == $b) break; /* . * Here we search next permutation.*/ $i = 1; while ($a[$i] >= $a[$i - 1]) { $i++; } $j = 0; while ($a[$j] <= $a[$i]) { $j++; } /*. Here we change.*/ $c = $a[$j]; $a[$j] = $a[$i]; $a[$i] = $c; /* . Tail reverse.*/ $c = $a; $z = 0; for ($i-= 1; $i > - 1; $i--) $a[$z++] = $c[$i]; } } ?> Source: https://habr.com/ru/post/329948/
All Articles