System, który buduję, zawiera zestaw suwaków interfejsu użytkownika (liczba jest różna), każdy w skali 0-100. Przez suwak rozumiem interfejs użytkownika, w którym chwytasz element i przeciągasz go w górę iw dół, jak regulator głośności. Są one połączone algorytmem, który zapewnia, że zawsze ich suma wynosi 100. Tak więc, gdy jeden suwak jest przesuwany w górę, pozostałe przesuwają się w dół, ostatecznie do zera. Kiedy jeden jest przesunięty w dół, pozostałe poruszają się w górę. Przez cały czas suma musi wynosić 100. Więc tutaj suwaki mają różne wartości, ale łącznie 100%:
----O------ 40
O---------- 0
--O-------- 20
--O-------- 20
--O-------- 20
Jeśli pierwszy suwak następnie przesunie się W GÓRĘ z 40 do 70, pozostałe muszą przesunąć się W DÓŁ o wartość (w miarę przeciągania suwaka). Zauważ, że trzy suwaki zmieniły się z 20 na 10, a jeden pozostał na zero, ponieważ nie może spaść niżej.
-------O--- 70
O---------- 0
-O--------- 10
-O--------- 10
-O--------- 10
Oczywiście, gdy jakikolwiek suwak osiągnie 0 lub 100, nie może się ruszyć dalej, w tym momencie moja głowa naprawdę zaczyna boleć. Więc jeśli suwak przesuwa się wyżej, pozostałe poruszają się niżej, ale gdy którykolwiek z nich osiągnie zero, tylko pozostałe, które jeszcze nie osiągnęły zera, mogą przesunąć się niżej.
Pytam o to tutaj, ponieważ to pytanie jest specyficzne dla algorytmu, a nie implementacji. FWIW platformą jest Android Java, ale nie jest to szczególnie istotne.
Podejście, które podjąłem przy pierwszym dźgnięciu, polegało na obliczeniu procentowej zmiany przesuniętego suwaka. Następnie podzieliłem tę zmianę i zastosowałem ją (w innym kierunku) do innych wartości suwaka. Problem polega jednak na tym, że przy użyciu wartości procentowych i mnożenia, jeśli jakikolwiek suwak dojdzie do zera, nie można go nigdy zwiększyć od zera - w rezultacie pojedyncze suwaki utkną na zero. Użyłem suwaków z zakresu od 0 do 1 000 000, aby uniknąć problemów z zaokrąglaniem i wydaje się to pomocne, ale jeszcze nie stworzyłem algorytmu, który dobrze radzi sobie ze wszystkimi scenariuszami.
źródło
Odpowiedzi:
Chciwy Algorytm
Gdy suwak przesuwa się w górę (w dół), wszystkie pozostałe muszą przejść w dół (w górę). Każdy ma trochę miejsca, które może przesunąć (dla pozycji w dół - ich pozycja, dla pozycji w górę: 100 pozycji).
Kiedy jeden suwak się porusza, weź pozostałe, posortuj je według miejsca, w którym mogą się poruszać, i po prostu iteruj przez nie.
Na każdej iteracji przesuń suwak w żądanym kierunku o (łącznie, aby przesunąć w lewo / suwaki w lewo w kolejce) lub o odległość, którą może przemieścić, w zależności od tego, która wartość jest mniejsza.
Ma to złożoność liniową (ponieważ można posortować tę samą uporządkowaną kolejkę raz po raz, po jej posortowaniu).
W tym scenariuszu żadne suwaki nie utkną, wszystkie starają się poruszać tak dużo, jak to możliwe, ale tylko do ich sprawiedliwego udziału.
Ważony ruch
Innym podejściem byłoby wyważenie potrzebnego ruchu. Myślę, że to właśnie próbowałeś zrobić, sądząc po swoim oświadczeniu „suwaki utknęły na 0”. IMHO to jest bardziej naturalne, po prostu trzeba zrobić więcej ulepszeń.
Spekulując ponownie, powiedziałbym, że próbujesz wyważyć ruchy różnych suwaków według ich pozycji (bezpośrednio przekłada się to na twój problem z zablokowaniem na 0). Pamiętaj jednak, że pozycję suwaka można wyświetlić z różnych kierunków - od początku lub od końca. Jeśli ważysz według pozycji od początku podczas zmniejszania i pozycji od końca podczas zwiększania, powinieneś unikać swojego problemu.
Pod względem terminologicznym jest to bardzo podobne do poprzedniej części - nie obciążaj ruchu, jaki należy wykonać, pozycją suwaków, obciążaj go przestrzenią, którą pozostawili, aby poruszać się w tym kierunku.
źródło
Podejście, które podjąłem jest nieco inne i wymaga użycia innej wewnętrznej reprezentacji każdego suwaka.
każdy suwak może przyjmować dowolną wartość od 0..100 (X), która jest używana jako współczynnik ważenia dla tego suwaka (nie%)
dodaj wszystkie wartości suwaka, aby uzyskać całkowitą liczbę (T)
aby określić wyświetlaną wartość każdego suwaka, użyj ZAOKR (X * 100 / T)
kiedy suwak jest przesuwany w górę lub w dół, zmieniasz tylko wartość jednego suwaka ; waga tego suwaka zwiększy się lub zmniejszy w stosunku do wszystkich innych suwaków, a powyższe obliczenia zapewnią, że zmiana na wszystkich innych suwakach zostanie rozłożona możliwie równomiernie.
źródło
Myślę, że nadmiernie komplikujesz rzeczy, próbując dostosować bieżącą wartość o procent zmiany suwaka „przeniesionego”, który daje procentowe wartości procentowe, co wprowadza błędy zaokrąglania.
Ponieważ wiesz, że masz do czynienia tylko z całkowitą wartością 100, zachowałbym liczby całkowite i cofałem się od 100, unikając poważnych problemów z zaokrąglaniem. (W poniższym przykładzie obsłużę zaokrąglanie jako całe liczby całkowite na końcu)
Moją techniką byłoby ustawienie suwaków jako prostych 0-100. Odejmij „nową” wartość od 100, aby obliczyć, ile należy redystrybuować, rozłóż ją między innymi suwakami zgodnie z ich wagą, a następnie posprzątaj)
O ile mi wiadomo, nie jest to prawidłowy kod systemu Android: str
To powinno wewnętrznie obsłużyć dowolną wartość 0 lub 100
źródło
Co z podejściem Round Robin? Utwórz transakcję, która zapewni, że dodanie wartości jednemu suwakowi zmniejszy się w porównaniu do jego elementu równorzędnego. i wzajemnie.
Następnie za każdym razem, gdy zmiana suwaka uruchamia transakcję za pomocą innego suwaka równorzędnego (utworzę iterator, który zwróci suwak równorzędny po kolei). Jeśli suwak równorzędny ma wartość zero, przejdź do następnego.
źródło
Aby rozwinąć świetną odpowiedź na Chciwy Algorytm od @Ordous. Oto podział poszczególnych kroków.
źródło
Jedną z prostych technik jest obliczenie wartości procentowych wartości suwaka względem sumy wartości suwaka, a następnie ponowne przypisanie wartości suwaka do odpowiednich obliczonych wartości procentowych. w ten sposób wartości suwaka zostaną ponownie dostosowane np
Wprawdzie wprowadza błąd zaokrąglenia, ale można sobie z tym poradzić na wypadek, gdyby wartości suwaków były dokładnie i zawsze sumowane do 100.
Ustawiłem skrzypce, aby to zademonstrować za pomocą angularjs. Odwiedź demo
źródło