Découvrez à qui revient l'achat des croissants

Une équipe a décidé que chaque matin, quelqu'un devrait apporter des croissants pour tout le monde. Ce ne devrait pas être la même personne à chaque fois, donc il devrait y avoir un système pour déterminer de quel tour il s'agit. Le but de cette question est de déterminer un algorithme pour décider à qui ce sera le tour d'apporter des croissants demain.

Contraintes, hypothèses et objectifs:

• Dont le tour est d'apporter des croissants sera déterminé l'après-midi précédent.
• Chaque jour, certaines personnes sont absentes. L'algorithme doit choisir quelqu'un qui sera présent ce jour-là. Supposons que toutes les absences soient connues un jour à l'avance, afin que l'acheteur de croissant puisse être déterminé l'après-midi précédent.
• Dans l'ensemble, la plupart des gens sont présents la plupart du temps.
• Dans un souci d'équité, chacun devrait acheter des croissants autant de fois que les autres. (Fondamentalement, supposez que chaque membre de l'équipe ait le même montant d'argent à dépenser pour des croissants.)
• Ce serait bien d'avoir un élément de caractère aléatoire, ou du moins de caractère aléatoire perçu, afin d'alléger l'ennui d'une liste. Ce n'est pas une contrainte dure: c'est plus un jugement esthétique. Cependant, la même personne ne doit pas être choisie deux fois de suite.
• La personne qui apporte les croissants doit le savoir à l'avance. Donc, si la personne P doit apporter des croissants le jour J, alors ce fait devrait être déterminé un jour précédent où la personne P est présente. Par exemple, si le porteur de croissants est toujours déterminé la veille, il doit s'agir de l'une des personnes présentes la veille.
• Le nombre de membres de l'équipe est suffisamment petit pour que les ressources de stockage et de calcul soient effectivement illimitées. Par exemple, l'algorithme peut s'appuyer sur une histoire complète de qui a apporté des croissants par le passé. Jusqu'à quelques minutes de calcul sur un PC rapide chaque jour seraient acceptables.

Il s'agit d'un modèle d'un problème réel, vous êtes donc libre de contester ou d'affiner les hypothèses si vous pensez qu'elles modélisent mieux le scénario.

Origine: Découvrez qui va acheter les croissants de Florian Margaine . Ma reformulation ici a des exigences légèrement différentes.

Il existe deux catégories de solutions à ce type de problème que je connais: les loteries biaisées et les séquences aléatoires filtrées / générées .

Tout d'abord, supprimons les solutions simples mais erronées qui ne gardent aucun état. Toute solution de style loterie qui ne maintient aucun état aura le nombre de victoires dans une distribution binomiale, qui échoue au critère "autant de fois". Vous pouvez sélectionner une séquence aléatoire qui sélectionne toutes les personnes de la même manière (le simple fait de faire le tour de la liste; les permutations fournissent un caractère aléatoire), mais une fois que les gens commencent à partir en vacances, votre séquence a maintenant des trous. À moins que vous ne gardiez une trace, vous vous retrouverez à nouveau avec des distributions binomiales au lieu de maintenir un effort égal.

Engageons-nous également à avoir un caractère aléatoire réel. Vous voudrez peut-être que, par exemple, une personne ne puisse pas planifier ses vacances sur la base d'un algorithme déterministe afin qu'elle ne soit jamais présente quand c'est son tour d'acheter des croissants (jusqu'à ce qu'elle utilise tous ses jours de vacances, je suppose) .

Passons donc aux deux types de solutions.

1. Pour construire une loterie biaisée, notons d'abord que nous pouvons choisir à peu près n'importe quelle distribution continue (avec un écart fini) pour générer des numéros pour notre loterie. Le perdant peut alors être la personne ayant le plus petit nombre. Ensuite, le biais le plus simple consiste à savoir si chaque individu a acheté plus ou moins que sa part. Vous pouvez mesurer le biais en unités de croissants. Vous pouvez régler le degré de caractère aléatoire en modifiant la largeur et la forme de la distribution - cela déterminera également la distance à laquelle un individu peut s'éloigner du "même nombre de fois". Les gaussiens sont faciles; ils permettent une surprise raisonnable sans avoir des queues trop longues ("injustes"). La forme de base de la solution est donc (en code Scala)

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

   Vous pouvez garder une trace de qui a acheté le dernier et leur donner un bonus de biais important (par exemple 10*stdev) pour empêcher les gens d'acheter deux fois de suite, sauf dans le cas où la structure de vacances permettait à tout le monde d'avoir acheté "la dernière" fois. (c'est-à-dire que vous achetez, puis partez en vacances.) Même chose pour ne pas être présent le jour de leur sélection. (Si quelqu'un est absent tous les deux jours, il finira par apparaître en brûlant son bonus de biais; je considère cela comme une fonctionnalité plutôt qu'un bug.)

   Ainsi, vous collectez votre liste d'employés actuels pour la journée, les faites tous rouler pour la loterie, choisissez le plus bas et mettez à jour. Vous pouvez choisir si la prime d'achat doit être égale au nombre d'employés (bon lorsque le coût est négligeable mais que le voyage pour obtenir des croissants est lourd), le nombre d'employés présents (bon si le voyage est facile mais le coût est lourd) ), ou quelque chose entre les deux (pour reconnaître les deux charges). Il est probablement préférable de n'avoir que la pénalité «manger» pour les personnes présentes, mais vous pouvez le faire dans les deux cas si vous sentez que le simple fait de partir en vacances ne vous donne pas un bon emplacement en moins.

2. Pour construire une séquence aléatoire filtrée, vous devez d'abord générer une séquence aléatoire. Mélanger une liste des employés est une bonne façon de commencer. Parcourez simplement la liste, dans l'ordre, au jour le jour. Si quelqu'un ne peut pas acheter parce qu'il est absent ou qu'on ne peut pas le dire ou acheter avant, sautez-le. Maintenant, vous avez un problème: vous accumulez des personnes qui ont été ignorées. Mais ça va. Lorsque vous arrivez à la fin de votre séquence, ajoutez la liste des employés ignorés à la liste complète avant de mélanger. Maintenant, la probabilité d'apparaître est proportionnelle au nombre de fois où vous avez été ignoré, ce qui conserve la propriété "même nombre de fois".

   $\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$

Personnellement, je préfère la solution de loterie biaisée car le contrôle sur le caractère aléatoire est meilleur. Avec des séquences filtrées, vous pouvez trouver des moyens plus complexes de générer des séquences. Par exemple, plutôt que de prendre une permutation aléatoire, effectuez des échanges locaux à une certaine distance, ou autorisez l'échange de personnes hors du pool entièrement (mais elles vont sur la liste ignorée) - mais ces choses nécessitent plus d'efforts algorithmiques. Avec la loterie, vous ajustez simplement l'écart type.

Soit l'ensemble des octets du croissant. Soit le montant dépensé par en croissant jusqu'au jour (cela peut être le nombre de fois qu'il achète un croissant s'ils dépensent toujours le même argent quel que soit le nombre de personnes présentes, ce qui ne regardez assez intelligent pour notre amoureux des croissants); le est pour l'initialisation et pour éviter la division par .$\{P_1,...,P_n\}$${v_i}^k-1$$P_i$$k$$-1$$0$

Pour un paramètre , soit .$l$$v^k=\sum_{i=1}^n ({v_i}^k)^l$

Au jour , ils choisissent l'acheteur du croissant du lendemain en tirant une variable aléatoire qui produit avec une probabilité de . Si l'élu n'est pas là (aujourd'hui ou après-demain), il lance à nouveau la pièce jusqu'à ce qu'il en trouve une qui lui convient (il existe, car ils sont surtout ici tous les jours ...).$k$$i$$1-\frac{(v_i^k)^l}{v^k}$

Et ils ont vécu heureux jusqu'à ce qu'ils découvrent que , ce lâche, était là, seulement un jour sur deux, et donc, n'achète jamais de croissant!$P_1$

Après réflexion (et peut-être un peu de torture sur pour qu'il rembourse le croissant qu'il a mangé sans payer), ils modifient leur algorithme.$P_1$

Ils calculent le prix moyen des croissants qu'ils paient chaque jour et l'appellent .$v$

Le premier jour, ils calculent une planification des acheteurs pour les jours à venir. Pour ce faire, ils font comme auparavant avec la variable aléatoire, et mettent à jour le par le prix qu'ils auraient dû payer le jour , c'est-à-dire en ajoutant chaque fois qu'il est prévu d'aller chez le boulanger. Parce qu'ils sont intelligents et qu'ils ne veulent pas payer trop cher, ils se souviennent également de ce qu'ils ont vraiment payé au jour pour que lorsqu'ils mettent à jour le planning, personne ne soit pénalisé.$v_i^k$$k$$v$$k$

Ils prévoient, jusqu'à ce que chaque ait une date dans le futur où il devrait acheter un croissant.$P_i$

Si devait acheter un croissant le jour mais annonce qu'il ne peut pas le jour (ou s'il n'a pas été réchauffé), il donne sa place à une personne présente qui n'a aucune obligation le lendemain, par exemple et lui prenez le tour suivant de .$P_i$$k+1$$k$$P_j$$P_j$

Le jour où le premier des n'est pas prévu d'acheter des croissants à l'avenir, ils prolongent leur planification (avec la variable aléatoire calculée avec le mis à jour pour le montant réel qu'ils ont payé et le montant prévu) jusqu'à ce que tout le monde soit de retour sur la ligne.$P_i$$v_i^k$

Et quand cela va pour toujours, ils vivent heureux, partageant également le prix du croissant.

Mais n'est pas content. En effet, il pense que le choisi est trop petit et donc la probabilité de payer deux fois de suite trop grande. Quoi qu'il en soit ... Les autres le laissèrent choisir aussi grand qu'il le voulait. Parce qu'il est grincheux mais pas stupide, il a choisi cette façon au fil du temps, même si le rapport entre les gros payeurs et les petits joueurs a tendance à ne pas être vu, le gros tendance à le souligner.$P_1$$l$$l$$l=k$$l$

Pourtant n'est pas si content, il n'est là que la moitié des jours (donc la moitié du croissant) et doit payer autant que qui est là tous les jours. Injuste!$P_1$$P_2$

Mais parce qu'ils sont fatigués de grincheux , ils courent loin. Mais au coin de la tête, ils pensent toujours à changer la dans la différence entre ce qu'ils ont payé et ce qu'ils mangent (normalisé pour obtenir des valeurs positives) mais ils sont trop paresseux et trop pleins de croissants.$P_1$$v_i^k$

Ps: Désolé pour le mauvais anglais mais je ne suis pas natif et il est tard ... n'hésitez pas à corriger les erreurs (et peut-être ajouter des épices à l'histoire ...)

Chaque itération que vous avez

• Une liste des personnes présentes et disponibles à l'achat
• L'acheteur précédent

Si vous choisissez une personne au hasard parmi les personnes de la liste et excluez l'acheteur précédent, vous atteignez vos objectifs:

1. L'algorithme est "au maximum" aléatoire car nous utilisons la quantité minimale d'informations de l'itération précédente et choisissons au hasard.
2. En moyenne, les gens paient (N / (N-1)) croissants chaque fois qu'ils participent à une extraction, ce qui rend l'algorithme le plus équitable possible.
3. Je suggérerais d'éliminer la règle de non-répétition pour rendre ce maximum aléatoire.

D'autres algorithmes que j'ai vus proposés sont moins aléatoires ou moins équitables:

1. Les algorithmes de "shuffle de deck" ne sont pas vraiment aléatoires dans le sens où la probabilité d'avoir à payer n'est pas constante (1 / N dans le premier choix, 1 / (N-1) dans le second ... 1 au Nème choix - - si un n'a pas encore été choisi). De plus, si vous êtes sélectionné en premier, vous avez exactement zéro chance d'être sélectionné pour les N fois suivantes. Le système est facilement brisé en entrant rarement jusqu'à ce qu'il soit cueilli, puis en permanence.

2. Les algorithmes «compensatoires» qui essaient de faire en sorte que tout le monde obtienne le même nombre de croissants au lieu de se fier aux propriétés des nombres aléatoires ne sont pas aléatoires ou équitables (ou les deux).