Finden Sie heraus, wer an der Reihe ist, um die Croissants zu kaufen und mögliche Abwesenheiten zu berücksichtigen

Ein Team hat beschlossen, jeden Morgen Croissants für jedermann mitzubringen. Es sollte nicht jedes Mal dieselbe Person sein, daher sollte es ein System geben, mit dem bestimmt werden kann, 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 bringt.

Einschränkungen, Annahmen und Ziele:

• Wessen Croissants an der Reihe sind, wird am Vortag bekannt gegeben.
• An einem bestimmten Tag sind einige Leute abwesend. 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 Vortag ermittelt werden kann.
• Insgesamt sind die meisten Menschen an den meisten Tagen anwesend.
• Im Interesse der Fairness sollte jeder so oft Croissants kaufen wie die anderen. (Grundsätzlich wird davon ausgegangen, dass jedes Teammitglied den gleichen Betrag für Croissants ausgeben kann.)
• 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 eine ästhetische Beurteilung. 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 an Tag D Croissants mitbringen soll, sollte dies an einem früheren Tag festgestellt werden, an dem Person P anwesend ist. Wenn beispielsweise der Croissant-Bringer immer am Vortag ermittelt wird, sollte es sich um eine der Personen handeln, die am Vortag anwesend sind.
• Die Anzahl der Teammitglieder ist so gering, dass Speicher- und Rechenressourcen praktisch unbegrenzt sind. Beispielsweise kann sich der Algorithmus auf eine vollständige Historie derjenigen stützen, die in der Vergangenheit Croissants mitgebracht haben. Bis zu ein paar Minuten Rechenzeit auf einem schnellen PC pro Tag wären in Ordnung.

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

_{Herkunft 1: Finden Sie heraus, wer die Croissants von Florian Margaine kauft.
Herkunft 2: Finden Sie heraus, wer die Croissants von Gilles kaufen wird.
Diese Frage ist dieselbe Version wie die von Gilles und wurde als Experiment erneut bei Programmierern veröffentlicht, um zu sehen, wie die verschiedenen Communities einer Programmierherausforderung begegnen.}

Ich würde einen Bewertungsalgorithmus verwenden. Jede Person beginnt mit einer Punktzahl von Null. Bei jedem Mitbringen von Croissants wird die Punktzahl um 1 erhöht. Die Punktzahl aller Teammitglieder, die keine Croissants mitgebracht haben, wird um 1 / N verringert. Eine Punktzahl von 0 bedeutet also, dass ein Teammitglied weder zu viel noch zu wenig gekauft hat.

Wählen Sie ohne Zufall die Person mit der niedrigsten Punktzahl aus der Liste der anwesenden Personen aus.

Um die Zufälligkeit zu erhöhen, sortieren Sie die Liste nach Punktzahl und wählen Sie zufällig aus der Liste aller Teammitglieder mit einer negativen Punktzahl aus. Durch die Beschränkung auf negative Ergebnisse stellen Sie sicher, dass über viele Wochen niemand zu viel Glück hat.

Der Vorteil dieses Algorithmus besteht darin, dass er sich nicht auf historische Aufzeichnungen stützt und das Hinzufügen neuer Teammitglieder zu jedem Zeitpunkt problemlos ermöglicht.

Es könnte angepasst werden, um zu ermöglichen, dass Abwesenheiten relativ häufig sind, indem die Punktzahlen nur der Anwesenden verringert werden, um die Croissants zu genießen.

Was ich tun würde, wenn ich dies auswählen müsste, wäre, einen Hut zu holen und alle Namen einmal auf kleine Zettel in den Hut zu stecken. Dann habe ich jeden Tag nach dem Zufallsprinzip einen Namen aus dem Hut gezogen, und das ist die Person, die am nächsten Tag die Croissants bringt. Dieses Papier wird dann unter "BRINGING CROISSANTS TOMORROW" auf eine Tafel geheftet. Das aktuell auf der Tafel befindliche Papier wird weggeworfen.

Ich hätte auch eine Kiste. Es beginnt leer. Jeden Tag, bevor ich die Namen zeichne, schütte ich den Inhalt der Schachtel in den Hut, gehe die Papiere im Hut durch und entferne alle, die morgen abwesend sein werden. Ihre Namen gehen in die Schachtel.

Wenn es an der Zeit ist, einen Namen zu zeichnen und der Hut leer ist, würde ich noch etwas Papier zerreißen und den Namen aller Personen, die morgen abwesend sein werden, einmal hinzufügen.

Aufgrund dieser beiden letzten Schritte kann derselbe Name mehrere Male gleichzeitig im Hut sein. Wenn der Name, den ich gerade zeichne, mit dem Namen auf der Tafel übereinstimmt, lege ich das Papier in die Schachtel und zeichne erneut.

Es sollte nicht allzu schwierig sein, dieses System in einen Algorithmus in der Sprache Ihrer Wahl zu übersetzen.

Algorithmus, kleiner Algorithmus. Verwenden Sie eine DB.

create table team_members 
(
    id integer auto_increment,
    name varchar(255),
    purchase_count integer,
    last_purchase_date datetime,
    present integer,
    prefers_donuts integer default 0,
    primary key( id)
)

Wer kauft?

select id from team_members where (present = 1) and (prefers_donuts = 0) order by purchase_count, last_purchase_date limit 1;

Nach dem Kauf:

update team_members set purchase_count = purchase_count + 1, last_purchase_date = now() where id = ?

Und dann setze:

insert into team_members (name, prefers_donuts) values ('GrandmasterB', 1);

... weil ich alte Schule bin.

Es sollte nicht allzu schwierig sein, eine kleine Zufälligkeit hinzuzufügen, indem Sie die erste Abfrage optimieren - möglicherweise durch Hinzufügen von random () anstatt nach last_purchase-Datum zu sortieren.

Eigentlich musste ich dieses Problem in der realen Welt etwas lösen:

remember how many times people have gotten donuts
every day:
  var candidates = everyone
  toss out people who aren't here tomorrow
  toss out people who aren't here today 
  toss out the person who got them today (unless they're the only one left)
  toss out everyone where "times they got donuts"/"times everyone has got donuts"
    is more than 1/number of people (unless that would eliminate everyone)

  pick someone at random from the candidates

Was passiert ist, dass Leute, die Donuts "zu viel" gekauft haben (wegen Pech, zur Arbeit gehen, wenn andere im Urlaub sind, usw.), aus dem Pool ausgeschlossen werden, bis genügend Anschaffungen getätigt wurden, um sie wieder unter den "richtigen" Prozentsatz von zu bringen Einkäufe.

Dies müsste jedoch erweitert werden, um die Einstellung neuer Mitarbeiter besser bewältigen zu können ...

Wie auch immer, dieses Design hat sich sehr gut für das Ändern von Variablen (wer ist in, wer ist out) und wenn der Zeitplan (praktisch) unendlich sein muss. Als zusätzlichen Bonus ist es einfach, Determinismus zu erzeugen, indem Sie Ihr RNG setzen.

Nicht so gut wie einige der anderen Antworten, aber eine andere Sichtweise auf das Problem:

1. Machen Sie eine Liste aller teilnehmenden Mitarbeiter
2. Duplizieren Sie die Liste häufig (z. B. 1.000).
3. Mische die Liste

Wählen Sie jeden Nachmittag den nächsten verfügbaren Croissant-Bringer aus. Jeden Morgen streicht der Croissant-Bringer seinen Namen von der Liste ab.

Die tägliche Verarbeitung ist mit Stift und Papier einfach.

Neueinstellungen und Kündigungen Alumni sollten am besten eine neue Liste erstellen. Wenn CPU-Zyklen jemals wieder teuer werden (oder Sie haben 100 Millionen Mitarbeiter und nur ein Arduino der 1. Generation), ist es einfach, die ursprüngliche Liste mit einer angemessenen Anzahl von Platzhaltern zu salzen.

Mehr Infos (auf Anfrage).

Wenn Sie diesen Ansatz mit einer beliebig langen Liste verwenden, profitieren Sie von Transparenz.

Sie wissen nicht nur, wer morgen Croissants bringt, sondern auch, wer sie am nächsten Tag bringen soll, und so weiter. Natürlich ist die Genauigkeit aufgrund von Abwesenheiten usw. umso geringer, je weiter Sie in der Zeit hinausschauen.

Hinterhältige Entwickler, die herausfinden, wie sie ihre Zettel mit einem Hut beschweren können, haben weniger Gelegenheit, ihren Croissant-Bring-Pflichten zu entgehen.

Jammernde Nicht-Entwickler, die behaupten, die Daten seien manipuliert, können die Daten leicht überprüfen, zu falschen Schlussfolgerungen kommen und trotzdem jammern.

Nicht zufällig

Pflegen Sie eine geordnete Liste. Wenn eine Person an dem Tag abwesend ist, an dem sie kaufen soll, tauschen Sie sie gegen die nächste verfügbare Person aus. Schließlich wird die Person anwesend sein und somit Croissants kaufen. Der Inhalt der Liste bleibt also derselbe, aber Personen können je nach Abwesenheit nach oben oder unten verschoben werden.

Neue Personen werden nach der aktuellen Position in die Liste eingefügt. Personen, die gekündigt oder gekündigt haben, werden von der Liste entfernt. Die aktuelle Position wird jeden Tag um 1 erhöht. Wenn sie das Ende erreicht, kehrt sie zum Anfang zurück.

Dies setzt voraus, dass genügend Personen in der Liste vorhanden sind, um die durchschnittliche Abwesenheitszeit zur Förderung der Fairness zu berücksichtigen.

Zufällig

Wir können nicht einfach jeden Tag zufällige Personen auswählen, da es kurzfristige Abweichungen gibt, z. B. wirf eine Münze zehnmal, und du könntest auf Kopf 8 und Schwanz 2 kommen, sodass die Köpfe kurzfristig verschraubt würden. Wir müssen also Eimer mit Menschen schaffen, um fair zu bleiben.

Der Eimer wird durch die Häufigkeit bestimmt, mit der in der Vergangenheit Crossiants gekauft wurden. In diesem Fall würden wir also ein Wörterbuch mit Personen und Kaufinteressenten speichern. Am ersten Tag sind alle im Eimer Null. Wenn Leute Croissants kaufen, werden sie dem nächsten Eimer zugeordnet, dh 1, 2 usw. Der zufällige Teil ist die Auswahl aus dem Pool verfügbarer Leute im Eimer. Der erste verfügbare Eimer ist der mit den wenigsten Käufen. Wenn sich 10 Personen im Eimer befinden, wählen Sie eine Zufallszahl von 1 bis 10 und denjenigen, der Croissants kauft. Neuen Leuten wird der niedrigste aktuelle Bucket zugewiesen, damit sie keine zusätzlichen Runden Crossianten kaufen (obwohl sie sofort im Buy-Pool sind). Wenn niemand im untersten Bucket verfügbar ist (alle fehlen), wechseln Sie zum nächsthöheren Bucket. Zum Beispiel lassen Sie ' s sagen, es gibt eine Liste von 10 Personen. An Tag 8 befinden sich 8 Personen in Eimer 1 und 2 in Eimer 0. Die beiden Personen in Eimer 0 sind abwesend. In diesem Fall wird der Eimer 1 verwendet und eine Person landet im Eimer 2. Die Personen befinden sich jedoch immer innerhalb weniger Crossiant Buys (Eimer) ineinander, da die Person, die jetzt im Eimer 2 ist, höchstwahrscheinlich nicht im Eimer 2 ist der Kaufpool für eine Weile.

Es könnten Verbesserungen hinzugefügt werden, um sicherzustellen, dass dieselbe Person nicht zwei Tage hintereinander kauft und dass einige Randfälle zu behandeln sind, aber dies würde ein Element der Zufälligkeit hinzufügen und es fair halten. Außerdem kann es sinnvoll sein, die tatsächlichen Croissant-Käufe im Vergleich zum aktuellen Eimer getrennt zu halten. Wenn Leute gehen, werden sie aus dem Eimer entfernt, indem sie entweder permanent als abwesend markiert oder ganz gelöscht werden.