Algorithme pour une interface utilisateur affichant X curseurs de pourcentage dont les valeurs liées totalisent toujours 100%

Un système que je construis comprend un ensemble de curseurs d'interface utilisateur (le nombre varie) chacun avec une échelle de 0 à 100. Par curseur, je veux dire une interface utilisateur où vous saisissez un élément et le faites glisser de haut en bas, comme un contrôle de volume. Ils sont connectés par un algorithme qui garantit qu'ils totalisent toujours 100. Ainsi, lorsqu'un curseur est déplacé vers le haut, les autres se déplacent tous vers le bas, éventuellement jusqu'à zéro. Quand l'un est descendu, les autres montent. En tout temps, le total doit être de 100. Donc, ici, les curseurs ont différentes valeurs, mais ils totalisent 100%:

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

Si le premier curseur monte ensuite de 40 à 70, les autres doivent descendre en valeur (lorsque le curseur est déplacé). Notez que trois curseurs sont passés de 20 à 10, et un est resté à zéro car il ne peut pas descendre plus bas.

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

Bien sûr, lorsqu'un curseur atteint 0 ou 100, il ne peut plus bouger, c'est là que ma tête commence vraiment à me faire mal. Donc, si un curseur monte plus haut, les autres descendent plus bas, mais quand l'un d'eux atteint zéro, seuls les autres qui n'ont pas encore atteint zéro peuvent descendre plus bas.

Je pose cette question ici car cette question est spécifique à l'algorithme et non à l'implémentation. La plateforme FWIW est Android Java, mais ce n'est pas particulièrement pertinent.

L'approche que j'ai adoptée avec mon premier coup de couteau a été de calculer le pourcentage de variation du curseur qui s'est déplacé. J'ai ensuite divisé ce changement et l'ai appliqué (dans l'autre sens) aux autres valeurs du curseur. Le problème est cependant qu'en utilisant des pourcentages et en multipliant, si un curseur arrive à zéro, il ne peut jamais être augmenté à nouveau à partir de zéro - le résultat net est que les curseurs individuels restent bloqués à zéro. J'ai utilisé des curseurs avec une plage de 0 à 1 000 000 pour éviter les problèmes d'arrondi et cela semble être utile, mais je n'ai pas encore créé d'algorithme qui gère bien tous les scénarios.

Algorithme gourmand

Lorsqu'un curseur monte (descend), tous les autres doivent descendre (monter). Chacun a un espace qu'il peut déplacer (pour le bas - leur position, pour le haut: 100 positions).

Ainsi, lorsqu'un curseur se déplace, prenez les autres curseurs, triez-les en fonction de l'espace qu'ils peuvent déplacer et parcourez-les simplement.

À chaque itération, déplacez le curseur dans la direction souhaitée de (total à déplacer à gauche / curseurs à gauche dans la file d'attente) ou de la distance qu'il peut parcourir, selon la plus petite des deux.

La complexité est linéaire (puisque vous pouvez utiliser la même file d'attente ordonnée à plusieurs reprises, une fois qu'elle a été triée).

Dans ce scénario, aucun curseur ne reste bloqué, tous essaient de bouger autant qu'ils le peuvent, mais uniquement jusqu'à leur juste part.

Mouvement pondéré

Une approche différente consisterait à pondérer le mouvement qu'ils doivent faire. Je pense que c'est ce que vous avez essayé de faire, à en juger par votre déclaration "les curseurs sont bloqués à 0". À mon humble avis, c'est plus naturel, il vous suffit de faire plus de réglages.

En spéculant à nouveau, je dirais que vous essayez de pondérer les mouvements des différents curseurs par leur position (cela se traduirait directement par votre problème bloqué à 0). Cependant, notez que vous pouvez afficher la position du curseur dans différentes directions - du début ou de la fin. Si vous pesez par position depuis le début lorsque vous diminuez et la position depuis la fin lorsque vous augmentez, vous devriez éviter votre problème.

Ceci est assez similaire en terminologie à la partie précédente - ne pondérez pas le mouvement à faire par la position des curseurs, pondérez-le par l'espace qu'ils ont laissé pour se déplacer dans cette direction.

L'approche que je prendrais est légèrement différente et implique l'utilisation d'une représentation interne différente de chaque curseur.

1. chaque curseur peut prendre n'importe quelle valeur de 0 à 100 (X) qui est utilisée comme facteur de pondération pour ce curseur (pas un%)

2. additionnez toutes les valeurs du curseur pour obtenir le chiffre total (T)

3. pour déterminer la valeur affichée de chaque curseur, utilisez ROUND (X * 100 / T)

4. lorsqu'un curseur est déplacé vers le haut ou vers le bas, vous ne modifiez que la valeur d'un curseur ; la pondération de ce curseur augmentera ou diminuera par rapport à tous les autres curseurs, et le calcul ci-dessus garantira que la modification de tous les autres curseurs sera répartie aussi uniformément que possible.

Je pense que vous compliquez trop les choses en essayant d'ajuster la valeur actuelle d'un pourcentage du changement du curseur `` déplacé '', ce qui vous donne des pourcentages de pourcentages, ce qui introduit des erreurs d'arrondi.

Puisque vous savez que vous ne traitez qu'avec une valeur totale de 100, je garderais les choses sous forme d'entiers et je reculerais à partir de 100, en évitant tout problème sérieux avec l'arrondi. (Dans l'exemple ci-dessous, je gère tous les arrondis sous forme d'entiers entiers à la fin)

Ma technique serait de régler les curseurs sur un simple 0-100. Soustrayez la `` nouvelle '' valeur de 100 pour déterminer la quantité à redistribuer, répartissez-la entre les autres curseurs en fonction de leur poids, puis nettoyez)

Ce n'est pas, à ma connaissance, un code Android valide: 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 

Cela devrait gérer intrinsèquement toute valeur 0 ou 100

Qu'en est-il de l'approche Round Robin? Créez une transaction qui garantit que l'ajout de valeur à un curseur sera réduit par rapport à son homologue. et vice versa.

Ensuite, chaque fois qu'un changement de curseur exécute la transaction avec un curseur de pair différent (je créerais un itérateur qui retournerait le curseur de pair à tour de rôle). Si le curseur d'homologue est nul, passez au suivant.

Juste pour développer la grande réponse Greedy Algorithm de @Ordous. Voici une ventilation des étapes.

1. Déplacer le curseur
2. Enregistrer la différence Montant qu'il a déplacé en tant que newValue - oldValue (Une valeur positive signifie qu'il a augmenté et que d'autres curseurs doivent descendre et vice versa)
3. Triez les autres dans la liste du moins au plus de la distance qu'ils PEUVENT déplacer dans la direction requise par le montant de la différence étant positif ou négatif.
4. Définissez le montantToMove = differenceAmount / restant OthersCount
5. Boucle à travers et déplacer chaque curseur par soit le montant qu'il peut déplacer ou amountToMove . Quelle que soit la plus petite
6. Soustrayez le montant que le curseur a déplacé de amountToMove et divisez par le nouveau OthersCount restant
7. Une fois terminé, vous avez réussi à répartir le differenceAmount entre les autres curseurs.

Une technique simple consiste à calculer les pourcentages des valeurs de curseur par rapport à la somme des valeurs de curseur, puis à réaffecter les valeurs de curseur aux pourcentages calculés respectifs. de cette façon, les valeurs des curseurs seront réajustées, par exemple

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

Bien qu'il introduise une erreur d'arrondi, il peut être géré au cas où nous aurions besoin que les valeurs des curseurs totalisent exactement et toujours jusqu'à 100.

J'ai installé un violon pour le démontrer en utilisant angularjs. Veuillez visiter la démo