Integer partition
This online calculator generates all possible partitions of an entered positive integer.
For an entered number in the range from 1 to 60, this online calculator generates all its representations as a sum of positive integers (all combinations of positive numbers that add up to that number) and displays the number of such representations.
In mathematics, the representation of a number as a sum of positive integers is called the partition of a positive integer n or integer partition. In the canonical notation of the partition, the terms are listed in non-increasing order of summands (note that two combinations that differ only in the order of their summands are considered the same partition). A description of the algorithm for generating all possible partitions can be found under the calculator.
Integer partition
The problem of generating all possible partitions of a number
Most sources that can be easily found by searching provide a recursive algorithm for generating all partitions. This calculator, for technical reasons, uses an iterative algorithm. The logic of the algorithm was taken from the article on Russian.
Since the logic of the algorithm is rather laconic, I will translate it here with some comments:
Given: the original array in the form of 1's - A (1,1,1,1,1).
The dimension of the array corresponds to the number n, all partitions of which we are looking for.
0) If the sum is received, then the algorithm stops.
Like the author of the article, I sum the elements in the array, at the end, there should be only one element with index 0, numerically equal to n.
1) Moving through the array from left to right, search in array A for the first minimum element - x,
the last element is not taken into account (does not participate in the search for the minimum).
We need both the element's value and its position in the array. Therefore, I do not use the built-in Javascript functions like min and findIndexOf, but use one iteration over the array, remembering both the current minimum element and its position, as well as the amount up to and including the current minimum element (the amount will be needed later).
2) Move 1 from the end (last element) to the found minimum element x
(equivalent to increasing x by one and decreasing the last element by one).
This is where one is added and the splice method is used
3) Decompose the sum of all elements after the changed element x into 1's.
Here we add 1's using the previously calculated partial sum.
The Javascript code of the algorithm is shown below (the partitions are being displayed to the console):
function split (n) {
var temp = [];
for (var i = 0; i ＜ n; ++ i) temp.push (1);
while (temp [0]! = n)
{
console.log (temp);
var min = temp [0];
var minindex = 0;
var sum = temp [0];
var tempsum = temp [0];
for (var j = 1; j ＜ temp.length - 1; ++ j) {
tempsum + = temp [j];
if (min ＞ temp [j]) {
min = temp [j];
minindex = j;
sum = tempsum;
}
}
temp [minindex] + = 1;
sum + = 1;
temp.splice (minindex + 1);
for (var k = 0; k ＜ n - sum; ++ k) temp.push (1);
}
console.log ([n]);
}It remains to add that, as with any other combinatorial problem, the number of partitions depends exponentially on the number n. If for 10 it is 42, then for 50 it is already 204 226, and for 100 it is 190 569 292. This calculator has a limit of 60, which gives 966 467 partitions and is calculated on my laptop for about 12 seconds. At 100, the browser ran out of memory and crashed.
The dependence of the number of partitions on n is a numerical sequence A000041 in the online encyclopedia of integer sequences and has some interesting properties.
Comments