Dowiedz się, czyja kolej na zakup rogalików

Zespół zdecydował, że każdego ranka ktoś powinien przynieść rogaliki dla wszystkich. Nie powinna to być ta sama osoba za każdym razem, więc powinien istnieć system określający, która kolej będzie następna. Celem tego pytania jest określenie algorytmu decydującego o tym, czyja kolej przyniesie rogaliki jutro.

Ograniczenia, założenia i cele:

• Który z kolei przyniesie rogaliki, zostanie ustalony poprzedniego popołudnia.
• Każdego dnia niektórzy ludzie są nieobecni. Algorytm musi wybrać kogoś, kto będzie obecny tego dnia. Załóżmy, że wszystkie nieobecności są znane z jednodniowym wyprzedzeniem, więc nabywcę rogalika można ustalić poprzedniego popołudnia.
• Ogólnie rzecz biorąc, większość ludzi jest obecna przez większość dni.
• W trosce o sprawiedliwość wszyscy powinni kupować rogaliki tyle razy, ile inni. (Zasadniczo załóżmy, że każdy członek zespołu ma taką samą kwotę do wydania na rogaliki).
• Byłoby miło mieć jakiś element losowości, a przynajmniej postrzegany losowość, aby złagodzić nudę listy. Nie jest to trudne ograniczenie: jest to bardziej osąd estetyczny. Jednak ta sama osoba nie powinna być wybierana dwa razy z rzędu.
• Osoba, która przyniesie rogaliki, powinna wiedzieć wcześniej. Jeśli więc osoba P ma przynieść rogaliki w dniu D, to fakt ten należy ustalić w dniu poprzedzającym, w którym osoba P jest obecna. Na przykład, jeśli przynoszący rogalika jest zawsze określany dzień wcześniej, to powinna to być jedna z osób obecnych dzień wcześniej.
• Liczba członków zespołu jest na tyle mała, że ​​zasoby pamięci i komputera są praktycznie nieograniczone. Na przykład algorytm może polegać na pełnej historii tego, kto przyniósł rogaliki w przeszłości. Nawet kilka minut obliczeń na szybkim komputerze każdego dnia byłoby w porządku.

Jest to model rzeczywistego problemu, więc możesz kwestionować lub udoskonalać założenia, jeśli uważasz, że lepiej modelują scenariusz.

Pochodzenie: Dowiedz się, kto kupi rogaliki od Floriana Margaine . Moje przeformułowanie tutaj ma nieco inne wymagania.

Istnieją dwie kategorie rozwiązań tego rodzaju problemów, o których jestem świadomy: stronnicze loterie i filtrowane / generowane losowe sekwencje .

Po pierwsze, zrezygnujmy z łatwych, ale złych rozwiązań, które nie utrzymują stanu. Każde rozwiązanie w stylu loterii, które nie zachowuje żadnego stanu, będzie miało liczbę wygranych w rozkładzie dwumianowym, co nie spełnia kryterium „tyle razy”. Możesz wybrać losową sekwencję, która wybiera wszystkie osoby jednakowo (po prostu przeglądanie listy to robi; permutacje zapewniają losowość), ale gdy ludzie zaczną wyjeżdżać na wakacje, w Twojej sekwencji są dziury. Jeśli nie będziesz śledzić, znów znajdziesz dwumianowe rozkłady zamiast utrzymywania równego wysiłku.

Zobowiążmy się również do faktycznej losowości. Możesz tego chcieć, aby na przykład osoba nie mogła zaplanować wakacji na podstawie algorytmu deterministycznego, aby nigdy nie byli obecni, gdy nadejdzie ich kolej na zakup rogalików (chyba, że ​​wykorzystają wszystkie dni urlopu, jak sądzę) .

Przejdźmy więc do dwóch rodzajów rozwiązań.

1. Aby skonstruować tendencyjną loterię, najpierw zauważ, że możemy wybierać z praktycznie dowolnej ciągłej dystrybucji (ze skończonym odchyleniem), aby generować liczby dla naszej loterii. Przegrany może być wówczas osoba o najniższym numerze. Następnie najprostszym nastawieniem jest śledzenie, czy każda osoba kupiła więcej czy mniej niż ich udział. Możesz zmierzyć odchylenie w jednostkach rogalików. Możesz dostroić stopień losowości, zmieniając szerokość i kształt rozkładu - to także określi, jak daleko dana osoba może dostać się z „tej samej liczby razy”. Gaussowie są łatwi; pozwalają na rozsądne zaskoczenie bez zbyt długich ogonów („niesprawiedliwe”). Podstawowym kształtem rozwiązania jest (w kodzie Scala)

   case class Employee(var bias: Double) {
     def eat         { bias -= 1 }
     def buy(n: Int) { bias += n }
     def roll        = bias + stdev * Random.nextGaussian
   }
   

   Możesz śledzić, kto kupił jako ostatni i dać im mocną premię za uprzedzenia (np. 10*stdev), Aby ludzie nie kupowali dwa razy z rzędu, z wyjątkiem przypadku, w którym struktura wakacji pozwoliła wszystkim kupić „ostatni” raz. (tzn. kupujesz, a potem jedziesz na wakacje.) To samo, że nie jesteś obecny w dniu ich wyboru. (Jeśli ktoś jest nieobecny co drugi dzień, w końcu pojawi się, gdy wykorzysta swoją premię za stronniczość; Uważam to za cechę, a nie błąd).

   Zbierasz więc listę obecnych pracowników na dany dzień, wszyscy oni rzucają się na loterię, wybierają najniższą i aktualizują. Możesz wybrać, czy premia za zakup będzie równa liczbie pracowników (dobrze, gdy koszt jest znikomy, ale wycieczka po rogaliki jest uciążliwa), liczbie obecnych pracowników (dobrze, jeśli podróż jest łatwa, ale koszt jest uciążliwy ) lub coś pośredniego (w celu uznania obu obciążeń). Prawdopodobnie lepiej jest mieć karę „jeść” tylko dla osób obecnych, ale możesz to zrobić tak czy inaczej, jeśli uważasz, że samo bycie na wakacjach nie daje ci właściwej wysokości w mniejszym stopniu.

2. Aby zbudować odfiltrowaną losową sekwencję, najpierw musisz wygenerować losową sekwencję. Przetasowanie listy pracowników to dobry sposób na rozpoczęcie. Wystarczy przejrzeć listę w kolejności, z dnia na dzień. Jeśli ktoś nie może kupić, ponieważ jest nieobecny lub nie można mu wcześniej powiedzieć ani kupić, pomiń go. Teraz masz problem: gromadzisz osoby, które zostały pominięte. W porządku. Gdy dojdziesz do końca sekwencji, dołącz listę pominiętych pracowników do pełnej listy przed przetasowaniem. Teraz prawdopodobieństwo pojawienia się jest proporcjonalne do liczby pominięć, która zachowuje właściwość „tyle razy”.

   Jeśli używasz standardowego losowania, szczególnie łatwo jest oszacować losowość, gdy nie ma wakacji. Jeśli wybierzesz ludzi całkowicie przypadkowo, wiedza o tym, kto ma przynieść następny, zawiera bitów informacji, jeśli będzie pracowników. Zamiast tego jednak tylkozamiast dozwolone są możliwe sekwencje, więc informacje są zmniejszane o bitów (dla dużych ; dla to ).$\log_2(N)$$N$$N!$$N^N$$\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$$N$$N=10$$~1.14$

Osobiście wolę stronnicze rozwiązanie loterii, ponieważ kontrola nad losowością jest lepsza. Dzięki filtrowanym sekwencjom możesz wymyślić bardziej złożone sposoby generowania sekwencji. Na przykład, zamiast brać losową permutację, wykonuj lokalne zamiany na pewną odległość lub zezwalaj na zamianę ludzi z puli całkowicie (ale trafiają na listę pominiętych) - ale te rzeczy wymagają większego wysiłku algorytmicznego. W loterii dostosowujesz standardowe odchylenie.

Niech będzie zbiorem bajtów rogalika. Niech będzie kwotą wydaną przez na rogalika do dnia (może to być liczba razy, kiedy kupuje rogalika, jeśli zawsze wydają te same pieniądze niezależnie od liczby obecnych ludzi, które nie wyglądają wystarczająco sprytnie dla naszego miłośnika rogalików); dla inicjalizacji i podziału można ich uniknąć przez .$\{P_1,...,P_n\}$${v_i}^k-1$$P_i$$k$$-1$$0$

Dla niektórych parametrów , niech .$l$$v^k=\sum_{i=1}^n ({v_i}^k)^l$

W dniu wybierają nabywcę rogalika następnego dnia, uruchamiając zmienną losową, której wynik jest prawdopodobny . Jeśli wybrańca nie ma tutaj (dziś lub pojutrze), ponownie rzucają monetą, aż znajdą odpowiednią dla siebie (on istnieje, ponieważ przeważnie są tu codziennie ...).$k$$i$$1-\frac{(v_i^k)^l}{v^k}$

I żyli szczęśliwie, dopóki nie dowiedzieli się, że , ten tchórz, był tam tylko jeden dzień po dwóch, a więc nigdy nie kupuje rogalika!$P_1$

Po refleksji (i może to być trochę tortur na aby zwrócić rogalikowi, który je bez płacenia), modyfikują algorytm.$P_1$

Obliczają średnią cenę rogalika, którą płacą codziennie i nazywają to .$v$

Pierwszego dnia obliczają plany kupujących na nadchodzące dni. Aby to zrobić, robią tak jak poprzednio ze zmienną losową i aktualizują o cenę, którą powinni zapłacić w dniu , tj. Dodając każdym razem, gdy planują pójść do piekarza. Ponieważ są sprytni i nie chcą płacić za dużo, pamiętają również, ile naprawdę zapłacili w dniu więc kiedy zaktualizują planowanie, nikt nie zostanie ukarany.$v_i^k$$k$$v$$k$

Planują, aż każdy miał w przyszłości datę, w której powinien kupić rogalika.$P_i$

Jeśli planowano kupić rogalika w dniu ale oznajmił, że nie może w dniu (lub jeśli nie został rozgrzany), oddaje swoje miejsce komuś obecnemu, który nie ma obowiązku następnego dnia, np. i on skręć w następną kolejkę .$P_i$$k+1$$k$$P_j$$P_j$

W dniu, w którym pierwszy z nie planuje kupić rogalika w przyszłości, przedłużają one planowanie (o zmienną losową obliczoną za pomocą zaktualizowanej do rzeczywistej kwoty, którą zapłacili i kwoty planowanej), aż wszyscy wrócą na linii.$P_i$$v_i^k$

A kiedy to trwa wiecznie, żyją szczęśliwi, dzieląc równo cenę rogalika.

Ale nie jest szczęśliwy. Rzeczywiście uważa, że ​​wybrany jest za mały, a więc prawdopodobieństwo zapłacenia dwa razy z rzędu za duże. Cokolwiek ... Pozostali niech wybrać tak duży, jak chce. Ponieważ jest zrzędliwy, ale nie głupi, wybrał w ten sposób , nawet jeśli czas między dużymi płatnikami a małymi graczami zwykle nie jest widoczny, a duży to podkreśla.$P_1$$l$$l$$l=k$$l$

Wciąż nie jest tak szczęśliwy, jest tam tylko połowa dni (czyli połowa rogalika) i musi płacić tyle, ile który jest tu codziennie. Niesprawiedliwy!$P_1$$P_2$

Ale ponieważ mają dość zrzędliwego , gonią za sobą. Ale w kącie głowy wciąż zastanawiają się nad zmianą różnicy między tym, co zapłacili, a tym, co jedzą (znormalizowane, by uzyskać wartości dodatnie), ale są zbyt leniwi i zbyt pełni rogalików.$P_1$$v_i^k$

Ps: Przepraszam za kiepski angielski, ale nie jestem native speakerem i jest już za późno ... nie krępuj się korygować błędów (i być może dodają przypraw do historii ...)

Każda twoja iteracja

• Lista osób obecnych i dostępnych do kupienia
• Poprzedni kupujący

Jeśli wybierzesz losowo osobę spośród osób na liście i wykluczysz poprzedniego nabywcę, osiągniesz swoje cele:

1. Algorytm jest „maksymalnie” losowy, ponieważ wykorzystujemy minimalną ilość informacji z poprzedniej iteracji i wybieramy losowo.
2. Średnio ludzie płacą za (N / (N-1)) rogaliki za każdym razem, gdy biorą udział w ekstrakcji, dzięki czemu algorytm jest jak najbardziej sprawiedliwy.
3. Sugerowałbym wyeliminowanie zasady „powtarzania”, aby uczynić to maksymalnie losowym.

Inne zaproponowane przeze mnie algorytmy są mniej przypadkowe lub mniej uczciwe:

1. Algorytmy „tasowania talii” nie są tak naprawdę losowe w tym sensie, że prawdopodobieństwo zapłaty nie jest stałe (1 / N w pierwszym wyborze, 1 / (N-1) w drugim ... 1 przy N-tym wyborze - - jeśli jeszcze nie został wybrany). Co więcej, jeśli zostaniesz wybrany jako pierwszy, masz dokładnie zero szans na wybór następnego N razy. System łatwo się psuje, przychodząc rzadko, dopóki nie zostanie wybrany, a następnie stale.

2. Algorytmy „kompensacyjne”, które próbują aktywnie zmusić wszystkich do otrzymania takiej samej liczby rogalików, zamiast polegać na właściwościach liczb losowych, nie są losowe lub sprawiedliwe (lub oba).