Digamos que tienes un dado de 20 lados. Empiezas a tirar ese dado y tienes que tirarlo unas docenas de veces antes de tirar finalmente los 20 valores. Te preguntas, ¿cuántos rollos necesito antes de tener un 50% de posibilidades de ver los 20 valores? ¿Y cuántas tiradas de n
dado muero necesito lanzar antes de tirar todos los n
lados?
Después de investigar un poco, descubre que existe una fórmula para calcular la posibilidad de obtener todos los n
valores después de los resultados r
.
P(r, n) = n! * S(r, n) / n**r
donde S(a, b)
denota los números de Stirling del segundo tipo , el número de formas de dividir un conjunto de n objetos (cada rollo) en k subconjuntos no vacíos (cada lado).
También encontrará la secuencia OEIS , que llamaremos R(n)
, que corresponde a la más pequeña r
donde P(r, n)
es al menos el 50%. El desafío es calcular el n
término th de esta secuencia lo más rápido posible.
El reto
- Dado un
n
, encuentre el más pequeñor
dondeP(r, n)
sea mayor o igual0.5
o 50%. - Teóricamente, su código debería manejar cualquier número entero no negativo
n
como entrada, pero solo probaremos su código en el rango de1 <= n <= 1000000
. - Para la puntuación, estaremos tomar el tiempo total necesario para funcionar
R(n)
en las entradas1
a través10000
. - Verificaremos si sus soluciones son correctas ejecutando nuestra versión de
R(n)
en su salida para ver siP(your_output, n) >= 0.5
yP(your_output - 1, n) < 0.5
, es decir, que su salida es realmente la más pequeñar
para un determinadon
. - Puede usar cualquier definición para
S(a, b)
en su solución. Wikipedia tiene varias definiciones que pueden ser útiles aquí. - Puede utilizar las funciones integradas en sus soluciones, incluidas las que calculan
S(a, b)
o incluso las que calculanP(r, n)
directamente. - Puede codificar hasta 1000 valores
R(n)
y un millón de números de Stirling, aunque ninguno de estos son límites estrictos, y puede cambiarse si puede presentar un argumento convincente para aumentarlos o disminuirlos. - No es necesario que compruebes cada posible
r
entren
y lor
que estamos buscando, pero sí necesitas encontrar el más pequeñor
y no cualquierr
lugarP(r, n) >= 0.5
. - Su programa debe usar un lenguaje que se pueda ejecutar libremente en Windows 10.
Las especificaciones de la computadora que probará sus soluciones son i7 4790k, 8 GB RAM
. Gracias a @DJMcMayhem por proporcionar su computadora para la prueba. Siéntase libre de agregar su propio tiempo no oficial para referencia, pero el tiempo oficial se proporcionará más tarde una vez que DJ pueda probarlo.
Casos de prueba
n R(n)
1 1
2 2
3 5
4 7
5 10
6 13
20 67 # our 20-sided die
52 225 # how many cards from a huge uniformly random pile until we get a full deck
100 497
366 2294 # number of people for to get 366 distinct birthdays
1000 7274
2000 15934
5000 44418
10000 95768
100000 1187943
1000000 14182022
Avíseme si tiene alguna pregunta o sugerencia. ¡Buena suerte y buena optimización!
fuente
Respuestas:
Python + NumPy, 3.95 segundos
Pruébalo en línea!
Cómo funciona
Esto utiliza la serie de forma cerrada para P ( r , n ), y su derivada con respecto a r , reorganizada para la estabilidad numérica y la vectorización, para hacer una búsqueda del método de Newton para r tal que P ( r , n ) = 0.5, redondeando r a un número entero antes de cada paso, hasta que el paso se mueva r en menos de 3/4. Con una buena suposición inicial, esto generalmente toma solo una o dos iteraciones.
x i = log (1 - i / n ) = log (( n - i ) / n ) cx i = log ( n ! / (( n - i - 1)! ⋅ n i + 1 ) y i = cx i + cx n - i - 2 - cx n - 1 = log binom ( n , i + 1) z i = (-1) i + 1 ⋅ binom ( n ,i + 1) ⋅ (( n - i - 1) / n ) r
1 + ∑ z i = n! ⋅ S ( r , n ) / n r = P ( r , n )
z i ⋅ x i + 1 = (-1) i + 1 ⋅ binom ( n , i + 1) ⋅ (( n - i - 1) / n ) r log (( n - i - 1) / n)
∑ z i ⋅ x i + 1 = d / d r P ( r , n )
fuente
0.366512
eralog
algo de hace años. Lo usaré-log(log(2)
en mi próxima iteración. En segundo lugar, la idea de utilizar el método de Newton también es muy inteligente y me alegra ver que esto funciona tan bien. Tercero, casi definitivamente voy a robarexp(log(binom(n, i+1)) + r * log((n-i-1)/n))
: ¡P Kudos con una gran respuesta! : Dnumpy
importaciónfrom numpy import *
y, por alguna razón, el tiempo se redujo básicamente a 0 ... ¿ Probar en línea ?r
, ya que tu aproximación inicial ya es bastante buena. Espero verte en PPCG una vez más, y lo siento por todo.