Algorithm for a UI showing X percentage sliders whose linked values always total 100%

Question

A system I'm building includes a set of UI sliders (the number varies) each with a scale of 0-100. By slider I mean a UI where you grab an element and drag it up and down, like a volume control. They are connected by an algorithm that ensures they always total 100. So when one slider is moved up, the others all move down, eventually to zero. When one is moved down, the others move up. At all times the total must be 100. So here sliders have various values, but they total 100%:

----O------ 40
O----------  0
--O-------- 20
--O-------- 20
--O-------- 20

If the first slider then moves UP from 40 to 70, the others have to move DOWN in value (as the slider is dragged). Note three sliders changed from 20 to 10, and one stayed at zero as it cannot go lower.

-------O--- 70
O----------  0
-O--------- 10
-O--------- 10
-O--------- 10

Of course when any slider reaches 0 or 100, it cannot move any further, which is where my head really starts to hurt. So if a slider moves higher, the others move lower, but when any of them reach zero only the remaining ones that have not yet reached zero can move lower.

I'm asking this here as this question is specific to the algorithm not the implementation. FWIW the platform is Android Java, but that's not especially relevant.

The approach I took with my first stab was to calculate the percentage change of the slider that moved. I then split that change and applied it (in the other direction) to the other slider values. The problem though is that by using percentages and multiplying, if any slider gets to zero, it can never be increased again from zero - the net result of that is that individual sliders get stuck at zero. I've used sliders with a range of 0 - 1,000,000 to avoid rounding issues and that appears to be helpful, but I've yet to create an algorithm that handles all scenarios well.

Answer 1

Greedy Algorithm

When a slider moves up (down), all others need to move down (up). Each one has some space it can move (for down - their position, for up: 100-position).

So when one slider moves, take the other sliders, sort them by the space they can move, and simply iterate through them.

On each iteration, move the slider in the needed direction by (total to move left / sliders left in queue) or the distance it can move, whichever is smaller.

This is linear in complexity (since you can use the same ordered queue over and over, once it has been sorted).

In this scenario, no sliders get stuck, all try to move as much as they can, but only up to their fair share.

Weighted move

A different approach would be to weight the move they need to do. I think this is what you tried to do, judging by your "sliders get stuck at 0" statement. IMHO this is more natural, you just need to do more tweaking.

Speculating again, I would say you try to weight the moves of different sliders by their position (This would directly translate to your stuck at 0 problem). However note that you can view the slider position from different directions - from the start or from the end. If you weight by position from start when decreasing and position from end when increasing, you should avoid your problem.

This is quite similar in terminology to the previous part - don't weight the move to make by the position of the sliders, weight it by the space they have left to move in that direction.

Answer 2

The approach I'd take is slightly different, and involves using a different internal representation of each slider.

1. each slider can take any value from 0..100 (X) which is used as a weighting factor for that slider (not a %)

2. add up all the slider values to get the total figure (T)

3. to determine each slider's displayed value, use ROUND(X * 100 / T)

4. when a slider is moved up or down, you only change the one slider's value; the weighting for that slider will increase or decrease relative to all the other sliders, and the above calc will ensure that the change to all the other sliders will be spread as evenly as possible.

Answer 3

I think you're over-complicating things by trying to adjust the current value by a percentage of the change of the 'moved' slider, which gives you percentages of percentages, which is introducing rounding errors.

Since you know you're only ever dealing with a total value of 100, I'd keep things as integers and work backwards from the 100, avoiding any serious messing about with rounding. (In the below example I handle any rounding as whole integers at the end)

My technique would be to set the sliders as simple 0-100. Subtract the 'new' value from 100 to work out how much to redistribute, spread that between the other sliders according to their weight, then clean up)

This is not, as far as I'm aware, valid Android code :p

// see how much is "left" to redistribute
amountToRedistribute = 100 - movedSlider.value

//What proportion of the original 100% was contained in the other sliders (for weighting)
allOtherSlidersTotalWeight = sum(other slider existing values)

//Approximately redistribute the amount we have left between the other sliders, adjusting for their existing weight
for each (otherSlider)
    otherSlider.value = floor(otherSlider.value/allOtherSlidersWeight * amountToRedistribute)
    amountRedistributed += otherSlider.value

//then clean up because the floor() above might leave one or two leftover... How much still hasn't been redistributed?
amountLeftToRedistribute -= amountRedistributed

//add it to a slider (you may want to be smarter and add in a check if the slider chosen is zero, or add it to the largest remaining slider, spread it over several sliders etc, I'll leave it fairly simple here)
otherSlider1.value += amountLeftToRedistribute 

This should intrinsically handle any 0 or 100 value

Answer 4

What about Round Robin approach? Create a transaction that insure that adding value to one slider will reduce from its peer. and vice versa.

Then every time a slider change run the transaction with a different peer slider (I would create an iterator that return the peer slider in turns). If the peer slider is zero then proceed to the next one.

Answer 5

Just to elaborate on the great Greedy Algorithm answer from @Ordous. Here is a breakdown of the steps.

1. Move Slider
2. Save the differenceAmount it moved as newValue - oldValue (Positive value means it moved up and other sliders need to move down and vice versa)
3. Sort the others in the list from least to most of distance they CAN move in the direction required by the differenceAmount being positive or negative.
4. Set the amountToMove = differenceAmount / remainingOthersCount
5. Loop through and move each slider by either the amount it can move or the amountToMove. Whichever is the smaller
6. Subtract the amount the slider did move from amountToMove and divide by the new remainingOthersCount
7. Once finished, you've successfully distributed the differenceAmount between the other sliders.

Answer 6

One simple technique is to calculate percentages of slider values relative to sum of slider values and then reassign the slider values to respective calculated percentages. this way slider values will be readjusted e.g

slider1.value = (slider1.value / sumOfSliderValues) * 100 ;
slider2.value = (slider2.value / sumOfSliderValues) * 100 ;
slider3.value = (slider3.value / sumOfSliderValues) * 100 ;

Although it introduces round off error but it can be handled in case we need the sliders values to exactly and always sum up to 100.

I have setup a fiddle to demonstrate this using angularjs. Please visit demo