Split number into 4 random numbers
You could create all possible combinations and pick a random array.
function get4() {
function iter(temp) {
return function (v) {
var t = temp.concat(v);
if (t.length === 4) {
if (t.reduce(add) === 10) {
result.push(t);
}
return;
}
values.forEach(iter(t));
};
}
const
add = (a, b) => a + b,
values = [1, 2, 3, 4],
result = [];
values.forEach(iter([]));
return result;
}
console.log(get4().map(a => a.join(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }
An algorithm for getting random values without a list of all possible combinations
It works by using a factor for the random value and an offset, based on the actual sum, index, minimum sum which is needed for the next index, and the maximum sum.
The offset is usually the minimum sum, or the greater value of the difference of sum and maximum sum. For getting the factor, three values are taken for the minimum for multiplying the random value.
The table illustrates all possible values of the sum and the needed iterations, based on a given value and the iteration for getting all values.
At the beginning the sum is the value for distribution in small parts. The result is the second block with a rest sum of
14
...10
, because it is possible to take a value of1
...5
. The third round follows the same rules. At the end, the leftover sum is taken as offset for the value.
An example with 1
, ..., 5
values and 5
elements with a sum of 15
and all possibilities:
min: 1
max: 5
length: 5
sum: 15
smin = (length - index - 1) * min
smax = (length - index - 1) * max
offset = Math.max(sum - smax, min)
random = 1 + Math.min(sum - offset, max - offset, sum - smin - min)
index sum sum min sum max random offset
------- ------- ------- ------- ------- -------
_ 0 15 4 20 5 1
1 14 3 15 5 1
1 13 3 15 5 1
1 12 3 15 5 1
1 11 3 15 5 1
_ 1 10 3 15 5 1
2 13 2 10 3 3
2 12 2 10 4 2
2 11 2 10 5 1
2 10 2 10 5 1
2 9 2 10 5 1
2 8 2 10 5 1
2 7 2 10 5 1
2 6 2 10 4 1
_ 2 5 2 10 3 1
3 10 1 5 1 5
3 9 1 5 2 4
3 8 1 5 3 3
3 7 1 5 4 2
3 6 1 5 5 1
3 5 1 5 4 1
3 4 1 5 3 1
3 3 1 5 2 1
_ 3 2 1 5 1 1
4 5 0 0 1 5
4 4 0 0 1 4
4 3 0 0 1 3
4 2 0 0 1 2
4 1 0 0 1 1
The example code takes the target 1
, ..., 4
with a length of 4
parts and a sum of 10
.
function getRandom(min, max, length, sum) {
return Array.from(
{ length },
(_, i) => {
var smin = (length - i - 1) * min,
smax = (length - i - 1) * max,
offset = Math.max(sum - smax, min),
random = 1 + Math.min(sum - offset, max - offset, sum - smin - min),
value = Math.floor(Math.random() * random + offset);
sum -= value;
return value;
}
);
}
console.log(Array.from({ length: 10 }, _ => getRandom(1, 4, 4, 10).join(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }
A litte late to the show, but I found this a fun task to think about so here you go. My approach does not need to create all partitions, it also does not rely on pure luck of finding a random match, it is compact and it should be unbiased.
It works efficiently even when large values are used, as long as max
is not too limiting.
const len = 4;
const total = 10;
const max = 4;
let arr = new Array(len);
let sum = 0;
do {
// get some random numbers
for (let i = 0; i < len; i++) {
arr[i] = Math.random();
}
// get the total of the random numbers
sum = arr.reduce((acc, val) => acc + val, 0);
// compute the scale to use on the numbers
const scale = (total - len) / sum;
// scale the array
arr = arr.map(val => Math.min(max, Math.round(val * scale) + 1));
// re-compute the sum
sum = arr.reduce((acc, val) => acc + val, 0);
// loop if the sum is not exactly the expected total due to scale rounding effects
} while (sum - total);
console.log(arr);
The simplest solution is brute force.
- Make a
while
loop to nest your calculations in - In the loop, create an empty array and fill it with random values until length is reached
- Check if the sum of the array is your desired value, and if it is then break the loop
The above should run until you have a result.
Two things worth considering though.
- Your can easily test if a solution is at all possible by calculating, that length-of-array times minimum-value isn't more than the sum and length-of-array times maximum-value isn't less than the sum.
- A loop based on random conditions could potentially run forever, so a maximum amount of iterations might be desirable.
Both of these points are considered in the snippet below:
function randomNumber(max, min) {
while (true) {
var r = Math.round(Math.random() * max);
if (r >= min) {
return r;
}
}
}
function splitXintoYComponentsBetweenMaxAndMin(numberToSplit, numberOfSplits, maxValue, minValue, onUpdate) {
if (minValue === void 0) {
minValue = 1;
}
//Test that a result can exist
if (maxValue * numberOfSplits < numberToSplit || minValue * numberOfSplits > numberToSplit) {
return new Promise(function(resolve, reject) {
resolve(false);
});
}
//Create returner array
var arr = [];
var accumulator = 0;
while (arr.length < numberOfSplits) {
var val = randomNumber(Math.floor(numberToSplit / numberOfSplits), minValue);
accumulator += val;
arr.push(val);
}
return new Promise(function(resolve, reject) {
function runTest() {
var d = Date.now();
var localMaxValue = Math.min(maxValue, Math.ceil((numberToSplit - accumulator) / 4));
//Combination loop
while (accumulator < numberToSplit && Date.now() - d < 17) {
var index = Math.round(Math.random() * (arr.length - 1));
if (arr[index] >= maxValue) {
continue;
}
var r = randomNumber(localMaxValue, minValue);
while (arr[index] + r > maxValue || accumulator + r > numberToSplit) {
if (Date.now() - d >= 17) {
break;
}
r = randomNumber(localMaxValue, minValue);
}
if (arr[index] + r > maxValue || accumulator + r > numberToSplit) {
continue;
}
arr[index] += r;
accumulator += r;
}
if (accumulator < numberToSplit) {
if (onUpdate !== void 0) {
onUpdate(arr);
}
requestAnimationFrame(runTest);
} else {
resolve(arr);
}
}
runTest();
});
}
//TEST
var table = document.body.appendChild(document.createElement('table'));
table.innerHTML = "<thead><tr><th>Number to split</th><th>Number of splits</th><th>Max value</th><th>Min value</th><th>Run</th></tr></thead>" +
"<tbody><tr><th><input id=\"number-to-split\" value=\"10\" type=\"number\" min=\"1\"/></th><th><input id=\"number-of-splits\" value=\"4\" type=\"number\" min=\"1\"/></th><th><input id=\"max-value\" type=\"number\" min=\"1\" value=\"4\"/></th><th><input id=\"min-value\" type=\"number\" min=\"1\" value=\"1\"/></th><th><input id=\"run\" type=\"button\" value=\"Run\"/></th></tr></tbody>";
var output = document.body.appendChild(document.createElement('pre'));
output.style.overflowX = "scroll";
document.getElementById("run").onclick = function() {
splitXintoYComponentsBetweenMaxAndMin(parseInt(document.getElementById("number-to-split").value, 10), parseInt(document.getElementById("number-of-splits").value, 10), parseInt(document.getElementById("max-value").value, 10), parseInt(document.getElementById("min-value").value, 10))
.then(function(data) {
if (data !== false) {
output.textContent += data.join("\t") + '\n';
} else {
output.textContent += 'Invalid data\n';
}
});
};
EDIT 1 - Big calculations
Using requestAnimationFrame and Promises the code can now execute asynchronously, which allows for longer calculation time without bothering the user.
I also made the random
function scale with the remaining range, greatly reducing the amount of calculations needed for big numbers.