El número de partición de un entero positivo se define como la cantidad de formas en que se puede expresar como una suma de enteros positivos. En otras palabras, el número de particiones enteras que tiene. Por ejemplo, el número 4
tiene las siguientes particiones:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
Por lo tanto, tiene 5
particiones. Este es OEIS A000041 .
Tarea
Dado un entero positivo N, determine su número de partición.
Se aplican todas las reglas estándar.
La entrada y salida pueden manejarse a través de cualquier medio razonable.
Este es el código de golf , por lo que gana el código más corto en bytes.
Casos de prueba
Entrada | Salida 1 | 1 2 | 2 3 | 3 4 | 5 5 5 | 7 7 6 | 11 7 | 15 8 | 22 9 | 30 10 | 42
code-golf
math
number-theory
combinatorics
integer-partitions
Martin Ender
fuente
fuente
Respuestas:
Pyth , 3 bytes
Pruébalo aquí! o Prueba una suite de prueba.
La respuesta tardó mucho más en formatearse que escribir el código en sí: P.
¿Cómo?
Pyth es la herramienta adecuada para el trabajo.
fuente
Mathematica, 11 bytes
Explicación
fuente
Python 2 ,
8583 bytes-2 bytes gracias a @notjagan
Pruébalo en línea!
Usando fórmula recursiva de OEIS A000041 .
fuente
==0
es equivalente a<1
en este caso. EDITAR: Use el enfoque de notjagan<1
lugar de==0
, pero el código TIO no.Emojicode 0.5,
204201 bytesPruébalo en línea!
-3 bytes usando "menor o igual que 1" en lugar de "menor que 2" porque el emoji "menor que" tiene una codificación UTF-8 bastante larga. También hecho
t
un congelado para silenciar una advertencia sin afectar el conteo de bytes.Extiende la clase 🚂 (entero) con un método llamado 🅰️. Puede escribir un programa simple que tome un número de la entrada, llame a 🅰️ en el número e imprima el resultado de esta manera:
Esta parte se puede jugar mucho al omitir los mensajes y el manejo de errores, pero no está incluida en el puntaje, por lo que prefiero mostrar más características de Emojicode, al tiempo que mejora la legibilidad en el camino.
Sin golf
Explicación
Nota: muchas opciones de emoji no tienen mucho sentido en emojicode 0.5. Es 0.x, después de todo. 0.6 solucionará esto.
Emojicode es un lenguaje de programación orientado a objetos que presenta genéricos, protocolos, opcionales y cierres, pero este programa no utiliza cierres y todos los genéricos y protocolos pueden considerarse implícitos, mientras que el único opcional aparece en el código auxiliar de E / S.
El programa funciona solo con unos pocos tipos: 🚂 es el tipo entero, 🔡 es el tipo de cadena y ⏩ es el tipo de rango. También aparecen algunos booleanos (👌), pero solo se usan en condiciones. Los booleanos pueden tomar un valor de 👍 o 👎, que corresponden a verdadero y falso, respectivamente.
Actualmente no hay operadores en Emojicode, por lo que además, las comparaciones y otras operaciones que normalmente son operadores se implementan como funciones, lo que hace que las expresiones utilicen la notación de prefijo . Los operadores también están previstos en 0.6.
Abordemos primero el programa de prueba.
Este es el bloque 🏁, que se puede comparar con main desde otros idiomas.
Las uvas y las sandías declaran bloques de código en emojicode.
Esto declara un nombre "congelado"
str
y establece su valor en una nueva cadena creada usando el inicializador (constructor) 😯, que toma una solicitud como una cadena y luego ingresa una línea del usuario. ¿Por qué usar un congelado en lugar de una variable? No cambiará, por lo que una variable emitirá una advertencia.Vamos a desglosarlo.
🚂str 10
llama al método on en elstr
congelado con el argumento 10. Por convención, los métodos nombrados con el nombre de un tipo convierten el objeto a ese tipo. 10 es la base a utilizar para la conversión de enteros. Este método devuelve un opcional,🍬🚂
. Los opcionales pueden contener un valor del tipo base o nada, ⚡. Cuando la cadena no contiene un número, se devuelve ⚡. Para usar el valor, uno tiene que desenvolver el opcional usando 🍺, lo que genera un error de tiempo de ejecución si el valor es ⚡. Por lo tanto, es una buena práctica verificar la nada antes de desenvolver un opcional. Es tan común, de hecho, que Emojicode tiene una abreviatura para eso. Normalmente,🍊
es un "si".🍊🍦 variable expression
significa: evaluar la expresión. Si lo opcional no contiene nada, la condición se evalúa como 👎 (falso). De lo contrario, un nombre congeladovariable
se crea con el valor desenvuelto de lo opcional y la condición se evalúa como 👍, (verdadero). Por lo tanto, en uso normal,🍇 ... 🍉
se ingresa el bloque que sigue al condicional.🅰️ es el método que el código principal agrega a 🚂 usando 🐋 que calcula el número de particiones. Esto llama a 🅰️ en el
num
congelado que declaramos en el condicional y convierte el resultado en una cadena usando la base 10 por el método 🔡. Entonces, 😀 imprime el resultado.🍓 significa "más", por lo que este bloque se ingresa cuando el usuario no ingresó un número correctamente.
Imprime la cadena literal.
Ahora, veamos el programa principal. Explicaré la versión sin golf; la versión de golf acababa de eliminar el espacio en blanco y las variables cambiaron su nombre a letras individuales.
Extiende la clase 🚂. Esta es una característica que no se encuentra comúnmente en los lenguajes de programación. En lugar de crear una nueva clase con 🚂 como la superclase, 🐋 modifica 🚂 directamente.
Crea un nuevo método llamado 🅰️ que devuelve un 🚂. Devuelve el número de particiones calculadas usando la fórmula
a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)
🐕 es similar a
this
oself
de otros idiomas y se refiere al objeto del método se llama en. Esta implementación es recursiva, por lo que esta es la condición de finalización: si el número al que se llamó el método es menor o igual a 1, devuelve 1.Cree una nueva variable
sum
y configúrela en 0. Asume implícitamente el tipo 🚂.🔂 itera sobre cualquier cosa que implemente el protocolo 🔂🐚⚪️, mientras que ⏩ es un rango literal que implementa 🔂🐚🚂. Un rango tiene un valor de inicio, un valor de parada y un valor de paso, que se supone que es 1 si
start < stop
, o -1 en caso contrario. También se puede especificar el valor del paso usando ⏭ para crear el rango literal. El valor de inicio es inclusivo, mientras que el valor de detención es exclusivo, por lo que es equivalentefor k in range(n)
aoSum_{k=0..n-1}
en la fórmula.Necesitamos calcular sigma (n - k), o la suma de los divisores de
n - k
en otras palabras, y el argumento es necesario varias veces, por lo que esto se almacenan - k
en la variablenmk
para guardar algunos bytes.Esto establece la
sig
variable al argumento de sigma e itera sobre todos los números del 1 alnmk - 1
. Podría inicializar la variable a 0 e iterar sobre 1..nmk pero hacerlo de esta manera es más corto.🚮 calcula el resto, o módulo y 😛 verifica la igualdad, por lo que la condición será 👍 si
i
es un divisor denmk
.Esta es una asignación por llamada, similar a la
+= -= >>=
familia del operador en algunos de los idiomas inferiores libres de emoji. Esta línea también se puede escribir como🍮 sig ➕ sig i
. Por lo tanto, después de que finalice el ciclo interno,sig
contendrá la suma de divisores den - k
, osigma(n - k)
Otra asignación por llamada, por lo que esto se suma
sigma(n - k) * A(k)
al total, como en la fórmula.Finalmente, la suma se divide por n y se devuelve el cociente. Esta explicación probablemente tomó tres veces más tiempo que escribir el código en sí ...
fuente
Pari / GP , 8 bytes
Pruébalo en línea!
fuente
Octava, 18 bytes
Utiliza la función incorporada partcnt.
No puedo hacerlo bien usando una función anónima usando @, se agradecería alguna ayuda.
fuente
Retina , 34 bytes
Pruébalo en línea!
Explicación
Convierta la entrada a unario.
Esto calcula las 2 particiones n-1 de la lista de dígitos unarios. Hacemos esto repetidamente (
+
) haciendo coincidir el primer (1
) límite sin palabras (\B
es decir, una posición entre dos1
s) en cada línea (%
) y reemplazándolo con;
, todo lo que sigue ($'
), un salto de línea (¶
), todo delante de que ($`
) y,
. Ejemplo:Se convierte
Donde
v
marca el resultado de$'
y^
marca el resultado$`
. Este es un idioma común para obtener el resultado de dos reemplazos diferentes a la vez (básicamente insertamos ambos;
el,
reemplazo como el reemplazo, así como las "mitades" faltantes de la cadena para completar dos sustituciones completas).Trataremos
;
como particiones reales y,
solo como marcadores de posición que eviten que las\B
coincidencias posteriores allí. Siguiente...... quitamos esas comas. Eso nos da todas las particiones. Por ejemplo, para la entrada
4
obtenemos:Sin embargo, no nos importa el pedido:
Esto ordena las corridas de
1
s en cada línea para obtener particiones desordenadas.Finalmente, contamos las
@
coincidencias únicas ( ) de.+
, es decir, cuántas líneas / particiones distintas hemos obtenido. Agregué esta@
opción hace años, luego la olvidé por completo y la redescubrí recientemente. En este caso, guarda un byte sobre la primera deduplicación con las líneasD`
.fuente
Python 2 ,
5453 bytesPruébalo en línea!
Cómo funciona
Cada partición de n se puede representar como una lista x = [x 1 , ⋯, x m ] de modo que x 1 + ⋯ + x m = n . Esta representación se vuelve única si requerimos que x 1 ≤ ⋯ ≤ x m .
Definimos una función auxiliar f (n, k) que cuenta las particiones con límite inferior k , es decir, las listas x tal que x 1 + ⋯ + x m = n y k ≤ x 1 ≤ ⋯ ≤ x m . Para la entrada n , el desafío pide la salida de f (n, 1) .
Para enteros positivos n y k tales que k ≤ n , hay al menos una partición con límite inferior k : la lista singleton [n] . Si n = k (en particular, si n = 1 ), esta es la única partición elegible. Por otro lado, si k> n , no hay soluciones en absoluto.
Si k <n , podemos contar recursivamente las particiones restantes construyéndolas de izquierda a derecha, de la siguiente manera. Para cada j tal que k ≤ j ≤ n / 2 , podemos construir particiones [x 1 , ⋯, x m ] = [j, y 1 , ⋯, y m-1 ] . Tenemos que x 1 + ⋯ + x m = n si y solo si y 1 + ⋯ + y m-1 = n - j . Además, x 1 ≤ ⋯ ≤ x m si y solo si j ≤ y 1 ≤ ⋯ ≤ y m-1 .
Por lo tanto, las particiones x de n que comienzan con j pueden calcularse como f (n - j, j) , que cuenta las particiones válidas y . Al requerir que j ≤ n / 2 , aseguramos que j ≤ n - j , por lo que hay al menos un y . Por lo tanto, podemos contar todas las particiones de n sumando 1 (para [n] ) yf (n - j, j) para todos los valores válidos de j .
El código es una implementación sencilla de la función matemática f . Además, establece k por defecto en 1 , por lo que
f(n)
calcula el valor de f (n, 1) para la entrada n .fuente
J ,
3735 bytesPruébalo en línea!
Explicación
fuente
p(n) = sum(sigma(n-k) * p(k) for k = 0 to n-1) / n
. Agregaré una explicación del código más adelante cuando creo que no se puede acortar significativamente.JavaScript,
125121 bytesPruébalo en línea!
Advertencia: la complejidad del tiempo y el espacio es exponencial. Funciona muy lento para grandes números.
fuente
Python 2 , 89 bytes
-9 bytes por Mr.Xcoder -1 byte por notjagan
Pruébalo en línea!
fuente
¯\_(ツ)_/¯
- por cierto, si quisieras mantener una función completa, no necesitarías la variable, 94 bytesJalea , 13 bytes
Pruébalo en línea!
Toma 5 segundos resolver n = 1000 en TIO.
fuente
Java 8 (229 bytes)
Sin golf:
fuente
Jalea , 3 bytes
El
Œṗ
átomo se ha agregado recientemente y significa "particiones enteras".Pruébalo en línea!
fuente
Pyt , 2 bytes
Explicación:
fuente
JavaScript ES7, 69 bytes
JavaScript ES6, 71 bytes
Complejidad de tiempo O (n ^ n), así que tenga cuidado (aparece un retraso obvio en mi computadora
F(6)
)fuente