The algorithm proposed in my another answer is functional but it’s not righteous (i.e. does not distribute the value evenly between lines). If there are many lines, the latter tend to be all with 0
. If there are few, the latter tend to get very large values. I will propose an alternative solution, limited to the case where the number to be distributed is whole and not excessively large, based on the "roulette" of genetic algorithms:
- Once again, you have
200
(which I will call alvo
) to be distributed between N lines. For simplification, this time let’s assume that the lines have no minimum, only maximum (if you have, refer to the first part of my other answer to a means of distributing the minimum).
- Let’s make a loop in which at each iteration one of the lines will be chosen and receive
1
more. That is, the loop will execute 200
iterations.
- A "roulette" is first created in which the area of each line in the roulette is proportional to its maximum value.
- Then draw a line at roulette; add the value of
1
and reduces its maximum also in 1
. If it reaches zero, the roulette area intended for that line will become zero and it will no longer be drawn.
Example:
var alvo = 200;
var linhas = [{min: 0, max: 150}, {min:0, max: 130}];
var resultado = [0, 0];
function criarRoleta() {
var ret = [];
var soma = 0;
for ( var i = 0 ; i < linhas.length ; i++ ) {
var valor = linhas[i].max - resultado[i];
ret.push(valor+soma);
soma += valor;
}
return [ret,soma];
}
for ( var i = 0 ; i < alvo ; i++ ) {
var roleta = criarRoleta();
var sorteio = Math.floor(Math.random()*roleta[1]);
for ( var t = 0 ; t < linhas.length ; t++ )
if ( sorteio < roleta[0][t] ) {
resultado[t]++;
break;
}
}
Example in jsFiddle. Note that in this case the distribution tends to be uniform, and proportional to the maximum of each line. Extreme distributions are possible, but rare - the fact that lines already drawn have their areas reduced contributes to the other lines increase their chance of being chosen in the following rounds.
Updating: this method is equivalent to opening an urn, putting in it N balls of different colors (1 for each space available in each row), and go out removing balls until you reach the total. That is, the probability of each line being drawn changes during the draw, so that it is more likely that they will all be X% full than a 100% full and other more empty.
If on the other hand what you care about is that the chance of the elements falling on a line is proportional to the size initial of each line, then it is necessary to "put the drawn balls back into the urn": this is done by creating the roulette once, instead of recreating them at each iteration (i.e. move the call to criarRoleta()
out of the loop). In this case, it is necessary to verify at each draw whether a line has reached its maximum and - if it has - "remove all the balls from that line from the urn" (i.e. upgrade the roulette so that the area of that line is zero, and the sum is adjusted accordingly).
Are always two values that should result in a third? Or do you have N values each with a different limit and that the sum should give a fixed total?
– Guilherme Bernal
I can have N lines/values @Guilhermebernal
– Alessandro Gomes
I don’t know java and I’m not sure I understand your example. But I think this link will help you answer your question. http://stackoverflow.com/a/5623492
– Marcos Banik
@Marcosbanik It’s a great link, you might want to put as an answer (although it doesn’t include any Javascript code - since the doubt of the OP is in the algorithm, not in the encoding). I just don’t know if it’ll solve the problem whole - because the "partitions" in this case would have to be dirty to upper limits.
– mgibsonbr
@mgibsonbr, I’m not sure yet to write an answer. The problem has 3 parameters. Sum, N and max. If $Sum <= N * max$ the link algorithm solves the problem. If $Soma > N * max$ it can appeal to one, and only one, element greater than max. That’s it?
– Marcos Banik
@Marcosbanik By my understanding of the question, if the sum is greater than the maxima then each line should have the maximum value and ready (even if the sum is lower than the desired one). The difficulty here is that there is a different maxim per line - and not a
max
global.– mgibsonbr
In fact that algorithm does not solve even the case $Soma <= N * max$, but I still think it can be adapted. Just can’t guarantee that the first vector will solve the problem.
– Marcos Banik