Sobre la serie
En primer lugar, puede tratar esto como cualquier otro desafío de golf de código y responderlo sin preocuparse por la serie. Sin embargo, hay una tabla de clasificación en todos los desafíos. Puede encontrar la tabla de clasificación junto con más información sobre la serie en la primera publicación .
Aunque tengo un montón de ideas para la serie, los desafíos futuros aún no están establecidos en piedra. Si tiene alguna sugerencia, hágamelo saber en la publicación de sandbox relevante .
Hoyo 3: Particiones enteras
Es hora de aumentar un poco la dificultad.
Una partición de un entero positivo n
se define como un conjunto múltiple de enteros positivos que suman n
. Como ejemplo si n = 5
, existen las siguientes particiones:
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}
Tenga en cuenta que estos son conjuntos múltiples, por lo que no hay un orden para ellos {3,1,1}
, {1,3,1}
y {1,1,3}
todos se consideran idénticos.
Su tarea es, dada n
, generar una partición aleatoria de n
. Aquí están las reglas detalladas:
La distribución de las particiones producidas debe ser uniforme . Es decir, en el ejemplo anterior, cada partición debe devolverse con probabilidad 1/7.
Por supuesto, debido a las limitaciones técnicas de los PRNG, será imposible una uniformidad perfecta. Para evaluar la uniformidad de su envío, se considerará que las siguientes operaciones producen distribuciones perfectamente uniformes:
- Obtener un número de un PRNG (sobre cualquier rango), que está documentado como (aproximadamente) uniforme.
- Mapear una distribución uniforme sobre un conjunto más grande de números en un conjunto más pequeño mediante módulo o multiplicación (o alguna otra operación que distribuya valores de manera uniforme). El conjunto más grande tiene que contener al menos 1024 veces tantos valores posibles como el conjunto más pequeño.
Dado que las particiones son multisets, puede devolverlas en cualquier orden, y este orden no tiene que ser coherente. Sin embargo, para el propósito de la distribución aleatoria, el orden se ignora. Es decir, en el ejemplo anterior
{3,1,1}
,{1,3,1}
y{1,1,3}
juntos deben tener una probabilidad de 1/7 de ser devueltos.- Su algoritmo debe tener un tiempo de ejecución determinista. En particular, no puede generar múltiples conjuntos aleatorios y rechazarlos si no suman
n
. - La complejidad del tiempo de su algoritmo debe ser polinómica
n
. En particular, no puede simplemente generar todas las particiones y seleccionar una aleatoria (ya que el número de particiones crece exponencialmente conn
). Puede suponer que el PRNG que está utilizando puede devolver valores distribuidos uniformemente en O (1) por valor. - No debe utilizar ninguna función integrada que resuelva esta tarea.
Puede escribir un programa completo o una función y tomar la entrada a través de STDIN o la alternativa más cercana, argumento de línea de comando o argumento de función y producir salida a través del valor de retorno o imprimiendo en STDOUT (o la alternativa más cercana).
Puede suponer eso n ≤ 65
(de modo que el número de particiones sea menor que 2 21 ). La salida puede estar en cualquier formato de lista o cadena conveniente y sin ambigüedades.
Si envía una función, considere también proporcionar un pequeño programa de prueba que llame a la función varias veces e imprima los resultados. Está bien si los parámetros tienen que ser modificados en el código. Esto es solo para que la gente pueda verificar que la solución sea al menos aproximadamente uniforme.
Este es el código de golf, por lo que gana el envío más corto (en bytes). Y, por supuesto, la presentación más corta por usuario también entrará en la tabla de clasificación general de la serie.
Tabla de clasificación
La primera publicación de la serie genera una tabla de clasificación.
Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:
# Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntuación, se puede mantener viejas cuentas en el título, golpeándolos a través. Por ejemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(El idioma no se muestra actualmente, pero el fragmento requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).
fuente
u/\. y
plazo?GolfScript, 90 bytes
Demostración en línea
Esta es una adaptación de mi código de conteo de partición (más simple) que en lugar de simplemente rastrear un conteo rastrea tanto un conteo como uno de los elementos contados seleccionados uniformemente.
Comparación lado a lado de los dos:
Diferencias:
~
es porque este es un programa en lugar de un fragmento.[1.]
reemplazo1
corresponde al cambio en lo que se rastrea.{(\{)}%+}%
incrementos adicionales de cada elemento en esa partición y los{1+}%
agregados1
a la partición.0
se convierte[0]
(en golf1,
) como parte del cambio en lo que se rastrea, pero debido a que necesita permanecer como una matriz cuando se antepone a otra, necesita el extra[ ]
.{+}*
convierte en una selección ponderada de las particiones, combinada con una suma de su recuento.(;`
quita el recuento de la salida y hace que la partición en un formato agradable.Marco de prueba
Ajuste el 7000 inicial si desea ejecutar un número diferente de pruebas. Tenga en cuenta que esto es demasiado lento para una demostración en línea.
fuente
Java,
285267 bytesEste es el mismo método que la respuesta de TheBestOne, pero utiliza una matriz simple en lugar de un mapa. Además, en lugar de devolver la partición aleatoria como a
List
, las imprime en la consola.A continuación se muestra un programa de prueba que lo ejecuta 100000 veces. Por ejemplo
n=5
, todos los conjuntos estuvieron dentro del 0.64% de un 1/7 perfecto en mi última ejecución.fuente
Math.min
llamada a(k<n?k:n)
, puede ir más allá, abandonando por completo y sólo hacer dos comprobaciones:b<k&b++<n
. También puede deshacerse fácilmente de lan>0
parte del bucle condicional (ya que sen>0&b<n
reduce ab<n
cuándob
se garantiza que no sea negativo).int
declaración por separado también.CJam,
6456 bytesPuedes probarlo con este script:
Explicación
fuente
Pyth, 64 bytes
Utiliza /programming//a/2163753/4230423 excepto que a) No hay caché ya que Pyth se memoriza automáticamente, b) Imprime cada uno en lugar de agregarlo a la lista, yc) se traduce a Pyth.
Publicaré una explicación de esto cuando tenga tiempo, pero aquí está el código de Python correspondiente:
Editar: Finalmente llegué a hacer la explicación:
fuente
Octava, 200
Sin golf:
Construya una matriz cuadrada donde cada celda (m, n) refleje el número de particiones
m
cuyo número más grande esn
, según el extracto de Knuth @feersum tan amablemente citado. Por ejemplo,5,2
nos da 2 porque hay dos particiones válidas2,2,1
y2,1,1,1
.6,3
nos da 3 para3,1,1,1
,3,2,1
y3,3
.Ahora podemos determinar determinísticamente la pth partición. Aquí, estamos generando
p
como un número aleatorio, pero puede modificar ligeramente el script, por lo quep
es un parámetro:Ahora podemos demostrar de manera determinista que cada resultado depende únicamente de p:
Por lo tanto, volviendo al original donde p se genera aleatoriamente, podemos estar seguros de que cada resultado es igualmente probable.
fuente
(2,2,1)
y(2,1,1,1,1)
(ya que los dos que ha enumerado tienen números mayores que2
).2
. Me refería a lo último.R, 198 bytes
Sin golf:
Sigue la misma estructura que la gran solución de @ dcsohl en Octave y, por lo tanto, también se basa en el extracto de Knuth publicado por @feersum.
Lo editaré más adelante si puedo encontrar una solución más creativa en R. Mientras tanto, cualquier entrada es bienvenida.
fuente
Java, 392 bytes
Llamar con
a(n)
. Devuelve unList
deInteger
sSangrado:
Adaptado de /programming//a/2163753/4230423 y golfizado
Cómo funciona esto: podemos calcular cuántas particiones de un número entero n hay en el tiempo O ( n 2 ). Como efecto secundario, esto produce una tabla de tamaño O ( n 2 ) que luego podemos usar para generar la k partición de n , para cualquier entero k , en O ( n ).
Deje que total = el número de particiones. Escoja un número aleatorio k de 0 a total de - 1. Generar el k ésimo partición.
Como de costumbre , las sugerencias son bienvenidas :)
fuente
Python 2, 173 bytes
Realiza recursivamente un diccionario
d
, con claves quek
representan un par(n,m)
mediantek=67*n+m
(utilizando el garantizadon<=65
). La entrada es la tupla del número de particionesn
enm
partes, y una partición aleatoria. Los recuentos se calculan mediante la fórmula recursiva (gracias a feersum por señalarlo)f(n,m) = f(n-1,m-1) + f(n,n-m)
,y la partición aleatoria se actualiza seleccionando una de sus dos ramas con probabilidad proporcional a su recuento. La actualización se realiza agregando se realiza agregando un
1
para la primera rama e incrementando cada elemento para la segunda.Tuve muchos problemas para obtener valores fuera de límites
m
yn
dar recuentos de cero. Al principio, usé un diccionario que por defecto es un recuento de 0 y una lista vacía. Aquí, estoy usando una lista y rellenándola con esta entrada predeterminada en su lugar. Los índices negativos hacen que la lista se lea desde su final, lo que da una entrada predeterminada que no se acerca al final como se ha alcanzado nunca, y los parámetros envolventes solo tocan una región dondem>n
.fuente
80386 código máquina, 105 bytes
Hexdump del código:
Como una función C:
void random_partition(int n, int result[]);
. Devuelve el resultado como una lista de números en el búfer proporcionado; no marca el final de la lista de ninguna manera, pero el usuario puede descubrir el final acumulando los números; la lista termina cuando la suma es igual an
.Cómo usar (en Visual Studio):
Ejemplo de salida (con n = 64):
Esto requiere muchas explicaciones ...
Por supuesto, utilicé el algoritmo que todos los demás también usaron; No había ninguna opción con el requisito sobre la complejidad. Entonces no tengo que explicar demasiado el algoritmo. De todas formas:
Denoto por
f(n, m)
el número de particiones den
elementos que usan partes no mayores quem
. Los almaceno en una matriz 2-D (declarada en C comof[65][64]
), donde está el primer índicen
y el segundom-1
. Decidí que apoyarn=65
era demasiado problema, así que lo abandoné ...Aquí hay un código C que calcula esta tabla:
Este código tiene un estilo ofuscado, por lo que se puede convertir a lenguaje ensamblador fácilmente. Calcula los elementos hasta
f(n, n)
, que es el número de particiones den
elementos. Cuando finaliza este código, la variable temporalc
contiene el número necesario, que puede usarse para seleccionar una partición aleatoria:Más tarde, esto
index
se convierte al formato requerido (lista de números) usando la tabla generada.Este código también está optimizado para la conversión al lenguaje ensamblador. Hay un pequeño "error": si la partición no contiene ningún
1
número al final, el último bucle se encuentran = 0
y genera un1
elemento innecesario . Sin embargo, no duele, porque el código de impresión rastrea la suma del número y no imprime este número extraño.Cuando se convierte en ensamblaje en línea, este código se ve así:
Algunas cosas divertidas a tener en cuenta:
rdrand
instrucción)ah
, lo que me da una multiplicación automática por 256. Para aprovechar esto, sacrifiqué el soporte paran = 65
. Espero poder ser excusado por este pecado ...La asignación de espacio en la pila se realiza restando 0x4100 del registro del puntero de la pila
esp
. ¡Esta es una instrucción de 6 bytes! Al volver a agregar este número, logré hacerlo en 5 bytes:¡Al depurar esta función en MS Visual Studio, descubrí que se bloquea cuando escribe datos en el espacio que asignó en la pila! Después de investigar un poco, descubrí algún tipo de protección de desbordamiento de pila: el sistema operativo parece asignar solo un rango muy limitado de direcciones virtuales para la pila; Si una función accede a una dirección demasiado lejos, el SO asume que es una saturación y mata el programa. Sin embargo, si una función tiene muchas variables locales, el sistema operativo hace algo de "magia" adicional para que funcione. Entonces tengo que llamar a una función vacía que tiene una gran matriz asignada en la pila. Después de que esta función regrese, se asignan páginas VM de pila adicionales y se pueden usar.
fuente