OEIS A000009 cuenta el número de particiones estrictas de los enteros. Una partición estricta de un entero no negativo n
es un conjunto de enteros positivos (por lo que no se permite la repetición y el orden no importa) que suman n
.
Por ejemplo, 5 tiene tres particiones estrictas: 5
, 4,1
, y 3,2
.
10 tiene diez particiones:
10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1
Desafío
Dado un entero no negativo n
<1000, genera el número de particiones estrictas que tiene.
Casos de prueba:
0 -> 1
42 -> 1426
Aquí hay una lista de los números de partición estrictos del 0 al 55, de OEIS:
[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]
Este es el código de golf , por lo que gana la solución más corta en bytes.
fuente
subsequences
(+import
) en mi respuesta, pero hasta ahora no tuve éxito.ES6, 64 bytes
Obras por sustracción recursiva de prueba.
k
es el número que se restó por última vez, y el siguiente número que se restará debe ser mayor (pero no tan grande que no se pueda restar un número aún mayor). Se agrega 1 porque siempre se puede restarn
. (Además, dado que esto es recursivo, debo tener cuidado de que todas mis variables sean locales).fuente
Python, 68 bytes
Simplemente llame a la función anónima pasando el entero no negativo
n
como argumento ... y espere el final del universo.fuente
n>0
, se ahorra un byte e ir más rápido (creo que son recursivos en números negativos): Preturn sum(...)if n else 1
Python 2, 49 bytes
Las ramas de recursividad en cada sumando el potencial
k
de1
quen
para decidir si debe ser incluido. Cada sumando incluido se resta de la suma deseadan
, y al final, sin=0
permanece, se cuenta esa ruta.fuente
Haskell, 43 bytes
La función binaria
n%k
cuenta el número de particiones estrictas den
en partes con una parte máximak
, por lo que la función deseada esf n=n%n
. Cada valork
puede ser incluido, que disminuyen
pork
, o excluido, y de cualquier manera el nuevo máximok
es uno inferior, dando la recursiónn%k=n%(k-1)+(n-k)%(k-1)
.fuente
n%k|q<-k-1=n%q+(n-k)%q
afeita un byte de la línea 3.Julia, 53 bytes
Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.
Obtenemos las particiones enteras usando
partitions
,filter
solo para aquellos con sumandos distintos,collect
en una matriz, y encontramos el último índice (es decir, la longitud) usandoendof
.fuente
Haskell, 58 bytes
Ejemplo de uso:
map h [0..10]
->[1,1,1,2,2,3,4,5,6,8,10]
.Es un enfoque simple de fuerza bruta. Verifique las sumas de todas las subsecuencias de
1..x
. Esto también funcionax == 0
porque todas las subsecuencias de[1..0]
are[[]]
y la suma de[]
is0
.fuente
05AB1E , 8 bytes
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
05AB1E , 5 bytes
Pruébalo en línea!
Nota: esto es extremadamente lento y agota el tiempo de espera para entradas mayores de aproximadamente 20.
Explicación:
fuente