Averigua a quién le toca comprar los cruasanes

Un equipo ha decidido que cada mañana alguien debería traer cruasanes para todos. No debería ser la misma persona cada vez, por lo que debería haber un sistema para determinar a quién le toca el turno. El propósito de esta pregunta es determinar un algoritmo para decidir a quién le tocará traer croissants mañana.

Restricciones, supuestos y objetivos:

• El turno de traer croissants se determinará la tarde anterior.
• En cualquier día, algunas personas están ausentes. El algoritmo debe elegir a alguien que estará presente ese día. Suponga que todas las ausencias se conocen con un día de anticipación, por lo que el comprador de croissant se puede determinar la tarde anterior.
• En general, la mayoría de las personas están presentes la mayoría de los días.
• En aras de la equidad, todos deberían comprar cruasanes tantas veces como los demás. (Básicamente, suponga que cada miembro del equipo tiene la misma cantidad de dinero para gastar en croissants).
• Sería bueno tener algún elemento de aleatoriedad, o al menos percibir aleatoriedad, para aliviar el aburrimiento de una lista. Esto no es una restricción difícil: es más un juicio estético. Sin embargo, no se debe elegir a la misma persona dos veces seguidas.
• La persona que trae los cruasanes debe saberlo de antemano. Entonces, si la persona P debe traer cruasanes el día D, entonces este hecho debe determinarse en algún día anterior donde la persona P esté presente. Por ejemplo, si el portador de croissant siempre se determina el día anterior, entonces debe ser una de las personas que están presentes el día anterior.
• El número de miembros del equipo es lo suficientemente pequeño como para que los recursos informáticos y de almacenamiento sean efectivamente ilimitados. Por ejemplo, el algoritmo puede basarse en una historia completa de quién trajo croissants en el pasado. Hasta unos pocos minutos de cálculo en una PC rápida todos los días estaría bien.

Este es un modelo de un problema del mundo real, por lo que es libre de desafiar o refinar los supuestos si cree que modelan mejor el escenario.

Origen: Descubre quién comprará los cruasanes de Florian Margaine . Mi reformulación aquí tiene requisitos ligeramente diferentes.

Hay dos categorías de soluciones para este tipo de problema que conozco: loterías sesgadas y secuencias aleatorias filtradas / generadas .

Primero, prescindamos de soluciones fáciles pero incorrectas que no mantienen ningún estado. Cualquier solución de estilo de lotería que no mantenga ningún estado tendrá el número de victorias en una distribución binomial, lo que falla el criterio de "tantas veces". Puede seleccionar una secuencia aleatoria que elija a todas las personas por igual (solo recorrer la lista hace eso; las permutaciones proporcionan aleatoriedad), pero una vez que las personas comienzan a irse de vacaciones, su secuencia ahora tiene agujeros. A menos que realice un seguimiento, volverá a encontrarse con distribuciones binomiales en lugar de mantener el mismo esfuerzo.

También comprometámonos a tener aleatoriedad real. Es posible que desee esto para que, por ejemplo, una persona no pueda programar sus vacaciones sobre la base de un algoritmo determinista para que nunca estén presentes cuando sea su turno de comprar cruasanes (hasta que agoten todos sus días de vacaciones, supongo) .

Entonces, a los dos tipos de soluciones.

1. Para construir una lotería sesgada, primero tenga en cuenta que podemos elegir prácticamente cualquier distribución continua (con desviación finita) para generar números para nuestra lotería. El perdedor puede ser la persona con el número más bajo. Entonces, el sesgo más simple es hacer un seguimiento de si cada individuo ha comprado más o menos de su parte. Puedes medir el sesgo en unidades de croissants. Puede ajustar el grado de aleatoriedad cambiando el ancho y la forma de la distribución; esto también determinará qué tan lejos puede llegar un individuo de "la misma cantidad de veces". Los gaussianos son fáciles; permiten una sorpresa razonable sin tener colas demasiado largas ("injustas"). Entonces la forma básica de la solución es (en código Scala)

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

   Puede hacer un seguimiento de quién compró el último y darles un fuerte bono de sesgo (por ejemplo 10*stdev) para evitar que las personas compren dos veces seguidas, salvo en el caso límite donde la estructura de vacaciones permitió que todos hayan comprado la "última" vez. (es decir, usted compra, luego se va de vacaciones). Lo mismo por no estar presente el día que fueron seleccionados. (Si alguien está ausente cada dos días, eventualmente aparecerán a medida que consuman su bonificación por sesgo; considero que esto es una característica en lugar de un error).

   Entonces, reúne su lista de empleados actuales para el día, haga que todos se presenten a la lotería, elija el más bajo y actualice. Puede elegir si el bono de compra es igual al número de empleados (bueno cuando el costo es insignificante pero el viaje para obtener cruasanes es oneroso), el número de empleados presentes (bueno si el viaje es fácil pero el costo es oneroso) ), o algo intermedio (para reconocer ambas cargas). Probablemente sea mejor tener solo la penalidad de "comer" para las personas que están presentes, pero puede hacerlo de cualquier manera si siente que simplemente estar de vacaciones no le da un lanzamiento correcto en menos.

2. Para construir una secuencia aleatoria filtrada, primero debe generar una secuencia aleatoria. Mezclar una lista de los empleados es una buena manera de comenzar. Simplemente revise la lista, en orden, día a día. Si alguien no puede comprar porque está ausente o no se le puede decir o comprar antes, omítelo. Ahora tiene un problema: está acumulando personas que han sido omitidas. Eso está bien, sin embargo. Cuando llegue al final de su secuencia, agregue la lista de empleados omitidos a la lista completa antes de barajar. Ahora la probabilidad de aparecer es proporcional a la cantidad de veces que se ha omitido, lo que mantiene la propiedad "la misma cantidad de veces".

   Si usa una combinación aleatoria estándar, también es particularmente fácil cuantificar la aleatoriedad cuando no hay vacaciones. Si seleccionó personas completamente al azar, el conocimiento de quién traería a continuación contendría bits de información si hubiera empleados. En cambio, sin embargo, soloen lugar de permiten secuencias posibles, por lo que la información se reduce en bits (para grande ; para es ).$\log_2(N)$$N$$N!$$N^N$NN=10$\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$

Personalmente, estoy a favor de la solución de lotería sesgada ya que el control sobre la aleatoriedad es mejor. Con secuencias filtradas, puede encontrar formas más complejas de generar secuencias. Por ejemplo, en lugar de realizar una permutación aleatoria, realice intercambios locales a una cierta distancia o permita el intercambio completo de personas fuera del grupo (pero van a la lista omitida), pero estas cosas requieren más esfuerzo algorítmico. Con la lotería, solo ajusta la desviación estándar.

Deje que sea ​​el conjunto de byers de croissant. Sea la cantidad gastada por en croissant hasta el día (puede ser la cantidad de veces que compra croissant si siempre gastan el mismo dinero, independientemente de la cantidad de personas presentes, que no mira lo suficientemente inteligente para nuestro amante de los cruasanes); el es para la inicialización y para evitar la división por .$\{P_1,...,P_n\}$${v_i}^k-1$$P_i$$k$$-1$$0$

Para algunos parámetros , deje .v k = ∑ n i = 1 ( v i k ) $l$$v^k=\sum_{i=1}^n ({v_i}^k)^l$

En el día , eligen al comprador del croissant del día siguiente disparando una variable aleatoria que resulte con probabilidad . Si el elegido no está aquí (hoy o el día después), arrojan la moneda nuevamente hasta que encuentren una adecuada (existe, porque en su mayoría están aquí todos los días ...).i 1 - ( v k i ) $k$$i$$1-\frac{(v_i^k)^l}{v^k}$

Y vivieron felices hasta que descubrieron que , ese cobarde, estaba allí, solo un día más de dos, y así, ¡nunca compra ningún cruasán!$P_1$

Después de reflexionar (y puede ser un poco de tortura en para que le reembolse el croissant que come sin pagar), modifican su algoritmo.$P_1$

Calculan el precio promedio del cruasán que pagan todos los días y lo llaman .$v$

El primer día calculan una planificación de compradores para los próximos días. Para hacerlo, hacen lo mismo que antes con la variable aleatoria y actualizan por el precio que deberían haber pagado el día , es decir, agregan cada vez que planean ir al panadero. Debido a que son inteligentes y no quieren pagar demasiado, también recuerdan cuánto pagaron realmente en el día para que cuando actualicen la planificación, nadie sea penalizado. k v $v_i^k$$k$$v$$k$

$P_i$

$P_i$$k+1$$k$$P_j$$P_j$

$P_i$$v_i^k$

Y cuando esto se acaba para siempre, viven felices, compartiendo por igual el precio del croissant.

$P_1$$l$$l$$l=k$$l$

$P_1$$P_2$

$P_1$$v_i^k$

PD: Perdón por el mal inglés, pero no soy hablante nativo y es tarde ... por favor, siéntase libre de corregir los errores (y puede agregarle especias a la historia ...)

Cada iteración que tienes

• Una lista de personas que están presentes y disponibles para comprar.
• El comprador anterior

Si elige una persona al azar entre las personas de la lista y excluye al comprador anterior, logrará sus objetivos:

1. El algoritmo es "máximo" al azar, ya que usamos la cantidad mínima de información de la iteración anterior y elegimos al azar.
2. En promedio, las personas pagan por (N / (N-1)) cruasanes cada vez que participan en una extracción, lo que hace que el algoritmo sea lo más justo posible.
3. Sugeriría eliminar la regla de no repetir para hacer esto al azar al máximo.

Otros algoritmos que he visto propuestos son menos aleatorios o menos justos:

1. Los algoritmos "Deck shuffle" no son realmente aleatorios en el sentido de que la probabilidad de pagar no es constante (1 / N en la primera selección, 1 / (N-1) en la segunda ... 1 en la enésima selección - - si aún no se ha elegido uno). Además, si te eligen primero, tienes exactamente cero posibilidades de ser elegido para las próximas N veces. El sistema se rompe fácilmente al entrar raramente hasta que se selecciona y luego constantemente.

2. Los algoritmos "compensatorios" que intentan hacer que todos obtengan activamente la misma cantidad de cruasanes en lugar de depender de las propiedades de los números aleatorios no son aleatorios o justos (o ambos).