f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
Pruébalo en línea!
Un enfoque diferente
Desde que publiqué este desafío, traté de encontrar una solución recursiva para este problema. Si bien no pude usar nada más que lápiz y papel, logré convertir la fórmula del golf en un problema práctico, al menos para ciertas definiciones prácticas, lo que hizo que fuera más fácil de analizar.
Imagine un programa de juegos con k + m candidatos que funciona de la siguiente manera.
En la ronda 1, todos los candidatos deben realizar una tarea determinada lo más rápido posible. Los k candidatos que realizan la tarea más rápido ganan 1 k $ (un kilodólar) cada uno y avanzan a la ronda 3.
En la ronda 2, los m candidatos restantes tienen una segunda oportunidad de unirse a los otros k . A cada candidato se le hace una pregunta. Si responden la pregunta correctamente, ganan 1 k $ y avanzan a la ronda 3. Sin embargo, si no responden la pregunta, son eliminados del juego. Esto significa que la ronda 3 tendrá entre k y k + m candidatos, dependiendo de cuántos puedan responder sus preguntas.
La ronda 3 consiste en m más concursos que son similares a la ronda 1. En cada competencia, los participantes tienen que cumplir una determinada tarea. A diferencia de la ronda 1, solo un candidato recibe un premio, pero todos los candidatos pueden participar en el próximo concurso. Cada concurso paga el doble que el concurso anterior; el primero paga 2 k $ y el último 2 m k $ .
Tenga en cuenta que, dado que todos los premios son poderes de dos, saber cuánto dinero en premios ganó un candidato significa que sabemos si avanzaron a la ronda 3 y cuáles de los concursos de la ronda 3 ganaron.
Suponga que está viendo el programa de juegos y que la ronda 1 ya terminó, por lo que sabe qué k candidatos ya llegaron a la ronda 3 y cuáles m candidatos aún están atrapados en la ronda 2. ¿De cuántas maneras se puede distribuir el dinero restante del premio?
Una vez que sabemos cuáles de los candidatos m de la segunda ronda han avanzado a la ronda 3, es fácil calcular los posibles resultados para este escenario específico. Si j candidatos avanzan, hay k + j total de candidatos en la ronda 3 y, por lo tanto, k + j posibles resultados para cada concurso. Con m concursos individuales en la ronda 3, esto produce (k + j) m resultados para todos los m concursos.
Ahora, j puede tomar cualquier valor entre 0 y m , dependiendo de qué candidatos responden correctamente en la ronda 2. Para cada valor fijo de j , hay m C j diferentes combinaciones de j candidatos que podrían haber avanzado a la ronda 3. Si llamamos el número total de resultados posibles para k candidatos de la ronda 3 ym candidatos de la ronda 2 g (m, k) , obtenemos la siguiente fórmula.
Si arreglamos k = 1 , obtenemos el siguiente caso especial, que constituye nuestro nuevo enfoque para resolver el problema original.
Una fórmula recursiva
Ahora, suponga que se quedó dormido durante los comerciales después de la ronda 1, y se despertó justo a tiempo para ver quién ganó el último concurso de la ronda 3 y, por lo tanto, el gran premio de 2 m k $ . No tiene ninguna otra información, ni siquiera cuánto dinero en premios ganó ese candidato en total. ¿De cuántas maneras se puede distribuir el dinero restante del premio?
Si el ganador fue uno de los m candidatos de la ronda 2, ya sabemos que debe haber avanzado a la ronda 3 . Por lo tanto, efectivamente tenemos k + 1 candidatos en la ronda 3, pero solo m - 1 candidatos en la ronda 2. Dado que conocemos al ganador del último concurso, solo hay m - 1 con resultados inciertos, por lo que hay g (m - 1, k + 1) posibles resultados.
Si el ganador es uno de los k candidatos que se saltó la ronda 2, el cálculo se vuelve un poco más complicado. Como antes, solo quedan m - 1 rondas, pero ahora todavía tenemos k candidatos en la ronda 3 ym candidatos en la ronda 2. Dado que el número de candidatos de la ronda 2 y el número de concursos de la ronda 3 son diferentes, los posibles resultados no pueden se calculará con una simple invocación de g . Sin embargo, después de que el candidato de la primera ronda 2 ha respondido, correcta o incorrectamente, el número de candidatos de la segunda ronda coincide una vez más con los concursos m - 1 de la ronda 3. Si el candidato avanza, hay k + 1 ronda 3 candidatos y por lo tanto g (m - 1, k + 1)posibles resultados; Si el candidato es eliminado, el número de candidatos de la ronda 3 permanece en k y hay g (m - 1, k) posibles resultados. Dado que el candidato avanza o no, hay g (m - 1, k + 1) + g (m - 1, k) posibles resultados que combinan estos dos casos.
Ahora, si sumamos los resultados potenciales para todos los candidatos k + m que podrían haber ganado el gran premio, el resultado debe coincidir con g (m, k) . Hay m concursantes de la ronda 2 que conducen a g (m - 1, k + 1) resultados potenciales cada uno, yk concursantes de la ronda 3 que conducen a g (m - 1, k + 1) + g (m - 1, k) unos. En resumen, obtenemos la siguiente identidad.
Junto con el caso base
Estas dos fórmulas caracterizan completamente la función g .
Una implementación de golf
Mientras
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(49 bytes, 0**m
produce 1 una vez que m cae a 0 ) o incluso
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(48 bytes, devuelve True en lugar de 1 ) serían soluciones válidas, todavía hay bytes para guardar.
Si definimos una función f que toma el número n de candidatos de la ronda 1 en lugar del número m de candidatos de la ronda 2 como primer argumento, es decir,
obtenemos la fórmula recursiva
con estuche base
Finalmente tenemos
entonces la implementación de Python
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
( k/n
produce 1 una vez que n = k ) resuelve la tarea en cuestión con indexación basada en 1.