Finden Sie heraus, wer an der Reihe ist, die Croissants zu kaufen

Ein Team hat beschlossen, dass jeden Morgen jemand Croissants für alle mitbringen sollte. Es sollte nicht jedes Mal dieselbe Person sein, daher sollte es ein System geben, das bestimmt, wer als nächstes an der Reihe ist. Der Zweck dieser Frage ist es, einen Algorithmus zu bestimmen, mit dem entschieden wird, wer morgen Croissants bringen soll.

Einschränkungen, Annahmen und Ziele:

• Wer an der Reihe ist, Croissants mitzubringen, wird am vergangenen Nachmittag festgelegt.
• An einem bestimmten Tag fehlen einige Personen. Der Algorithmus muss jemanden auswählen, der an diesem Tag anwesend sein wird. Angenommen, alle Abwesenheiten sind einen Tag im Voraus bekannt, sodass der Croissant-Käufer am vorherigen Nachmittag ermittelt werden kann.
• Insgesamt sind die meisten Menschen an den meisten Tagen anwesend.
• Im Interesse der Fairness sollte jeder Croissants so oft kaufen wie die anderen. (Nehmen Sie grundsätzlich an, dass jedes Teammitglied den gleichen Geldbetrag für Croissants hat.)
• Es wäre schön, ein Element der Zufälligkeit oder zumindest der wahrgenommenen Zufälligkeit zu haben, um die Langeweile eines Dienstplans zu lindern. Dies ist keine harte Einschränkung, sondern eher ein ästhetisches Urteil. Dieselbe Person sollte jedoch nicht zweimal hintereinander ausgewählt werden.
• Die Person, die die Croissants mitbringt, sollte dies im Voraus wissen. Wenn also Person P am Tag D Croissants mitbringen soll, sollte diese Tatsache an einem früheren Tag festgestellt werden, an dem Person P anwesend ist. Wenn zum Beispiel der Croissantbringer immer am Vortag bestimmt wird, sollte es eine der Personen sein, die am Vortag anwesend sind.
• Die Anzahl der Teammitglieder ist so gering, dass die Speicher- und Computerressourcen praktisch unbegrenzt sind. Zum Beispiel kann sich der Algorithmus auf eine vollständige Historie stützen, wer in der Vergangenheit Croissants gebracht hat. Bis zu ein paar Minuten Berechnung auf einem schnellen PC pro Tag wären in Ordnung.

Dies ist ein Modell eines realen Problems. Sie können die Annahmen also in Frage stellen oder verfeinern, wenn Sie der Meinung sind, dass sie das Szenario besser modellieren.

Herkunft: Finden Sie heraus, wer die Croissants von Florian Margaine kaufen wird . Meine Neuformulierung hat hier etwas andere Anforderungen.

Es gibt zwei Kategorien von Lösungen für diese Art von Problem, die mir bekannt sind: voreingenommene Lotterien und gefilterte / generierte Zufallssequenzen .

Lassen Sie uns zunächst auf einfache, aber falsche Lösungen verzichten, die keinen Status behalten. Jede Lösung im Lotteriestil, die keinen Status beibehält, hat die Anzahl der Gewinne in einer Binomialverteilung, die das Kriterium "so oft" nicht erfüllt. Sie können eine zufällige Sequenz auswählen, die alle Personen gleich auswählt (wenn Sie nur die Liste durchgehen; Permutationen sorgen für Zufälligkeit), aber sobald die Leute in den Urlaub fahren, hat Ihre Sequenz jetzt Löcher. Wenn Sie nicht den Überblick behalten, werden Sie wieder mit Binomialverteilungen konfrontiert sein, anstatt den gleichen Aufwand aufrechtzuerhalten.

Lassen Sie uns auch die tatsächliche Zufälligkeit festlegen. Vielleicht möchten Sie dies, damit beispielsweise eine Person ihren Urlaub nicht auf der Grundlage eines deterministischen Algorithmus planen kann, sodass sie nie anwesend ist, wenn sie an der Reihe ist, Croissants zu kaufen (bis sie alle Urlaubstage verbraucht haben, nehme ich an). .

Also weiter zu den beiden Arten von Lösungen.

1. Um eine voreingenommene Lotterie zu konstruieren, beachten Sie zunächst, dass wir aus nahezu jeder kontinuierlichen Verteilung (mit endlicher Abweichung) auswählen können , um Zahlen für unsere Lotterie zu generieren. Der Verlierer kann dann die Person mit der niedrigsten Nummer sein. Dann besteht die einfachste Tendenz darin, zu verfolgen, ob jeder Einzelne mehr oder weniger als seinen Anteil gekauft hat. Sie können die Vorspannung in Einheiten von Croissants messen. Sie können den Grad der Zufälligkeit einstellen, indem Sie die Breite und Form der Verteilung ändern. Dies bestimmt auch, wie weit eine Person von "der gleichen Anzahl von Malen" entfernt sein kann. Gaußsche sind einfach; Sie ermöglichen eine angemessene Überraschung, ohne zu lange Schwänze zu haben ("unfair"). Die Grundform der Lösung lautet also (im Scala-Code).

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

   Sie können nachverfolgen, wer zuletzt gekauft hat, und ihnen einen kräftigen Bias-Bonus geben (z. B. 10*stdev), um zu verhindern, dass Leute zweimal hintereinander kaufen, außer in dem Fall, in dem die Urlaubsstruktur es jedem ermöglichte, "das letzte" Mal gekauft zu haben. (dh Sie kaufen und fahren dann in den Urlaub.) Dasselbe gilt, wenn Sie an dem Tag, an dem sie ausgewählt wurden, nicht anwesend sind. (Wenn jemand abwesend jeden zweiten Tag ist sie schließlich wird kommen , wenn sie durch ihren Bias - Bonus verbrennen;. Ich halte das für eine Funktion eher als ein Fehler)

   Sie sammeln also Ihre Liste der anwesenden Mitarbeiter für diesen Tag, lassen sie alle für die Lotterie rollen, wählen die niedrigste aus und aktualisieren sie. Sie können wählen, ob der Kaufbonus gleich der Anzahl der Mitarbeiter sein soll (gut, wenn die Kosten vernachlässigbar sind, aber die Reise, um Croissants zu bekommen, lästig ist), der Anzahl der anwesenden Mitarbeiter (gut, wenn die Reise einfach ist, aber die Kosten belastend sind) ) oder etwas dazwischen (um beide Belastungen anzuerkennen). Es ist wahrscheinlich besser, nur die "Essens" -Bestrafung für anwesende Personen zu haben, aber Sie können es so oder so tun, wenn Sie das Gefühl haben, dass ein bloßer Urlaub Ihnen nicht den richtigen Pitch in weniger bringt.

2. Um eine gefilterte Zufallssequenz zu erstellen, müssen Sie zuerst eine Zufallssequenz generieren. Das Mischen einer Liste der Mitarbeiter ist so gut wie jeder andere. Gehen Sie einfach die Liste der Reihe nach von Tag zu Tag durch. Wenn jemand nicht kaufen kann, weil er abwesend ist oder vorher nicht informiert oder gekauft werden kann, überspringen Sie ihn. Jetzt haben Sie ein Problem: Sie sammeln Leute, die übersprungen wurden. Das ist aber okay. Wenn Sie am Ende Ihrer Sequenz angelangt sind, hängen Sie die Liste der übersprungenen Mitarbeiter vor dem Mischen an die vollständige Liste an. Jetzt ist die Wahrscheinlichkeit, dass Sie auftauchen, proportional zu der Häufigkeit, mit der Sie übersprungen wurden, wodurch die Eigenschaft "gleich oft" beibehalten wird.

   Wenn Sie ein Standard-Shuffle verwenden, ist es auch besonders einfach, die Zufälligkeit zu quantifizieren, wenn keine Ferien vorhanden sind. Wenn Sie Personen völlig zufällig würden, würde das Wissen darüber, wer als nächstes mitbringen sollte, Informationen enthalten, wenn es Mitarbeiter gäbe . Stattdessen jedoch nurAnstelle von mögliche Sequenzen zulässig, daher werden die Informationen um reduziert. - Bits (für große ; für es ist ).$\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$

Persönlich bevorzuge ich die voreingenommene Lotterielösung, da die Kontrolle über die Zufälligkeit besser ist. Mit gefilterten Sequenzen können Sie komplexere Methoden zum Generieren von Sequenzen finden. Anstatt beispielsweise eine zufällige Permutation vorzunehmen, führen Sie lokale Auslagerungen bis zu einer bestimmten Entfernung durch oder erlauben Sie das vollständige Auslagern von Personen aus dem Pool (sie gehen jedoch auf die übersprungene Liste) - diese Dinge erfordern jedoch mehr algorithmischen Aufwand. Bei der Lotterie passen Sie einfach die Standardabweichung an.

Sei die Menge der Croissant-Byers. Sei der Betrag, den bis zum Tag für Croissants (es kann die Häufigkeit sein, mit der er Croissants kauft, wenn sie immer das gleiche Geld ausgeben, unabhängig von der Anzahl der anwesenden Personen, die dies nicht tun schau klug genug für unseren Croissant-Liebhaber); Das dient zur Initialisierung und zur Vermeidung der Division durch .$\{P_1,...,P_n\}$${v_i}^k-1$$P_i$$k$$-1$$0$

Für einige Parameter sei .v k = ∑ n i = 1 ( v i k ) $l$$v^k=\sum_{i=1}^n ({v_i}^k)^l$

Am Tag wählen sie den Käufer des Croissants des nächsten Tages aus, indem sie eine Zufallsvariable abfeuern, die mit der Wahrscheinlichkeit . Wenn der Auserwählte nicht hier ist (heute oder übermorgen), werfen sie die Münze erneut, bis sie eine passende finden (er existiert, weil sie meistens jeden Tag hier sind ...).$k$$i$$1-\frac{(v_i^k)^l}{v^k}$

Und sie lebten glücklich, bis sie herausfanden, dass , dieser Feigling, nur einen Tag über zwei da war und deshalb nie ein Croissant kaufte!$P_1$

Nach einigem Nachdenken (und möglicherweise ein bisschen Folter auf damit er das Croissant, das er isst, ohne zu bezahlen, zurückerstattet) modifizieren sie ihren Algorithmus.$P_1$

Sie berechnen den Durchschnittspreis für Croissants, den sie jeden Tag zahlen, und nennen ihn .$v$

Am ersten Tag berechnen sie eine Käuferplanung für die kommenden Tage. Dazu tun sie wie zuvor mit der Zufallsvariablen und aktualisieren das um den Preis, den sie am Tag hätten zahlen sollen , dh sie fügen jedes Mal hinzu, wenn sie zum Bäcker gehen sollen. Weil sie klug sind und nicht zu viel bezahlen wollen, erinnern sie sich auch daran, wie viel sie am Tag wirklich bezahlt haben, so dass niemand bestraft wird, wenn sie die Planung aktualisieren. k v $v_i^k$$k$$v$$k$

Sie planen, bis jeder einen Termin in der Zukunft hat, an dem er Croissants kaufen soll.$P_i$

Wenn am Tag Croissant kaufen wollte, aber an Tag ankündigt, dass er es am Tag nicht kann (oder wenn er nicht aufgewärmt ist), gibt er seinen Platz an jemanden, der am nächsten Tag nicht verpflichtet ist, z. B. und er Nehmen Sie die nächste Runde von . k + 1 k P j P $P_i$$k+1$$k$$P_j$$P_j$

An dem Tag, an dem der erste in Zukunft kein Croissant mehr kaufen soll, verlängern sie ihre Planung (wobei die mit dem berechnete Zufallsvariable auf den tatsächlich gezahlten Betrag und den geplanten Betrag aktualisiert wird), bis alle zurück sind an der Leitung.v k $P_i$$v_i^k$

Und wenn dies für immer geht, leben sie glücklich und teilen sich den Preis für Croissants.

Aber ist nicht glücklich. In der Tat hält er das gewählte für zu klein und damit für die Wahrscheinlichkeit, zweimal hintereinander zu zahlen, zu groß. Was auch immer ... Die anderen lassen ihn wählen so groß wie er will. Weil er mürrisch, aber nicht dumm ist, hat er im Laufe der Zeit , auch wenn das Verhältnis zwischen großen Zahlern und kleinen Spielern nicht gesehen wird, während das große eher betont. l l l = k $P_1$$l$$l$$l=k$$l$

Trotzdem ist nicht so glücklich, er ist nur die Hälfte der Tage da (also die Hälfte des Croissants) und muss so viel bezahlen wie , das jeden Tag hier ist. Unfair!P $P_1$$P_2$

Aber weil sie das mürrische satt haben , jagen sie weg. Aber in der Ecke ihres Kopfes sie immer noch denken , die von wechselnden in der Differenz zwischen dem, was sie bezahlt und was sie essen (normiert auf positive Werte zu erhalten) , aber sie sind zu faul und zu voll von Croissants.v k $P_1$$v_i^k$

Ps: Entschuldigung für das schlechte Englisch, aber ich bin kein Muttersprachler und es ist spät ... bitte zögern Sie nicht, Fehler zu korrigieren (und fügen Sie der Geschichte möglicherweise Gewürze hinzu ...)

Jede Iteration, die Sie haben

• Eine Liste der Personen, die anwesend sind und zum Kauf angeboten werden
• Der vorherige Käufer

Wenn Sie zufällig eine Person unter den Personen in der Liste auswählen und den vorherigen Käufer ausschließen, erreichen Sie Ihre Ziele:

1. Der Algorithmus ist "maximal" zufällig, da wir die minimale Menge an Informationen aus der vorherigen Iteration verwenden und zufällig auswählen.
2. Im Durchschnitt zahlen die Leute jedes Mal für (N / (N-1)) Croissants, wenn sie an einer Extraktion teilnehmen, um den Algorithmus so fair wie möglich zu gestalten.
3. Ich würde vorschlagen, die No-Repeat-Regel zu streichen, um dies maximal zufällig zu machen.

Andere Algorithmen, die ich vorgeschlagen habe, sind weniger zufällig oder weniger fair:

1. "Deck Shuffle" -Algorithmen sind nicht wirklich zufällig in dem Sinne, dass die Wahrscheinlichkeit, zahlen zu müssen, nicht konstant ist (1 / N bei der ersten Auswahl, 1 / (N-1) bei der zweiten ... 1 bei der N-ten Auswahl - - wenn noch keiner ausgewählt wurde). Wenn Sie zuerst ausgewählt werden, haben Sie außerdem genau null Chancen, für die nächsten N-mal ausgewählt zu werden. Das System kann leicht beschädigt werden, indem es selten bis zur Kommissionierung und dann ständig eingeht.

2. "Kompensative" Algorithmen, die versuchen, alle dazu zu bringen, die gleiche Anzahl von Croissants zu erhalten, anstatt sich auf die Eigenschaften von Zufallszahlen zu verlassen, sind nicht zufällig oder fair (oder beides).