P k (n) significa la cantidad de particiones n
en k
partes exactamente . Dado n
y k
, calcular P k (n).
Consejo: P k (n) = P k (n − k) + P k − 1 (n − 1), con valores iniciales p 0 (0) = 1 y p k (n) = 0 si n ≤ 0 o k ≤ 0. [Wiki]
Ejemplos
n k Ans
1 1 1
2 2 1
4 2 2
6 2 3
10 3 8
Reglas
- Se aplican reglas generales de código de golf .
code-golf
combinatorics
integer-partitions
Matthew Roh
fuente
fuente
8
lugar de7
.Respuestas:
Pyth ,
976 bytes-1 byte gracias a Erik the Outgolfer !
Pruébalo en línea!
Las entradas al programa se invierten (es decir
k, n
).fuente
Swift ,
7673 bytesPruébalo en línea!
Explicación
¿Cómo funciona estructuralmente el código?
En primer lugar, definimos nuestra función
P
, con dos parámetros enterosn
yk
, y le dan un tipo de retorno deInt
, con este trozo de código:func P(_ n:Int,_ k:Int)->Int{...}
. El truco genial aquí es que le decimos al compilador que ignore los nombres de los parámetros,_
seguido de un espacio, que nos ahorra dos bytes cuando llamamos a la función.return
obviamente se usa para devolver el resultado de nuestro ternario anidado que se describe a continuación.Otro truco que utilicé fue
n*k>0
, que nos ahorra un par de bytesn>0&&k>0
. Si la condición es verdadera (ambos enteros son aún más altos que0
), entonces recurrimos recursivamente a nuestra función conn
decrementado pork
como nuevon
yk
permanece igual, y sumamos el resultado deP()
conn
yk
decrementado por 1. Si la condición no es verdadera , devolvemos cualquiera1
o0
dependiendo de sin
es igual ak
.¿Cómo funciona el algoritmo recursivo?
Sabemos que el primer elemento de la secuencia es p 0 (0) , por lo que verificamos que ambos enteros sean positivos (
n*k>0
). Si no son superiores a 0, verificamos si son iguales (n==l ?1:0
), aquí hay dos casos:Hay exactamente 1 partición posible, y por lo tanto devolvemos 1, si los enteros son iguales.
No hay particiones si una de ellas ya es 0 y la otra no.
Sin embargo, si ambos son positivos, recurrimos recursivamente
P
dos veces, agregando los resultados deP(n-k,k)
yP(n-1,k-1)
. Y volvemos a recorrerlo hasta quen
llegue a 0.* Nota: los espacios no se pueden eliminar.
fuente
Jalea , 6 bytes
Pruébalo en línea!
fuente
Python 2 ,
61555150 bytes-10 bytes gracias a Erik the Outgolfer. -1 byte gracias al Sr. Xcoder.
Diré, copié la pista de OP y la traduje a Python. :PAGS
Pruébalo en línea!
fuente
(n>0and k>0)
->n>0<k
+(n==k)
lugar de[0,1][n==k]
.or +
.n>0<k and
conn*k>0and
Mathematica, 33 bytes
aquí está la tabla nxk
fuente
Length
->Len`1
yIntegerPartitions
->Int`7
JavaScript (ES6),
424039 bytesCreo que esto funciona.
Intentalo
fuente
MATL , 14 bytes
Pruébalo en línea!
Explicación
Considere insumos
6
,2
.fuente
Haskell, 41 bytes
Pruébalo en línea!
fuente
Haskell , 41 bytes
Pruébalo en línea!
Una recurrencia alternativa.
fuente
Pari / GP , 35 bytes
Pari / GP tiene una función integrada para iterar sobre particiones enteras.
Pruébalo en línea!
fuente
Jalea , 13 bytes
¡Tengo la
sensación deque este enfoque básico no será el más golfista!Pruébalo en línea!
fuente
05AB1E , 9 bytes
Pruébalo en línea!
fuente
CJam , 18 bytes
Pruébalo en línea!
Espera entradas en reversa, es decir, en
k n
lugar den k
.fuente
Scala , 73 bytes
Bueno, este es un uso fácil y sencillo de la punta de OP.
k
yn
son los parámetros de mi función recursivaf
. Ver enlace TIO para el contexto.Como esto es recursivo, ¿debo incluir la función def en el conteo de bytes?
Pruébalo en línea!
fuente
C (gcc) , 41 bytes
Pruébalo en línea!
fuente
R (+ pryr), 49 bytes
Que evalúa la función recursiva
(k < 1 | n < 1)
comprueba si se cumple alguno de los estados iniciales.!n + k
evalúa como TRUE (1) si ambosn
yk
son 0, y FALSE (0) en caso contrario.f(n - k, k) + f(n - 1, k - 1)
maneja la recursividad.fuente