Particiones enteras restringidas

8

P k (n) significa la cantidad de particiones nen kpartes exactamente . Dado ny 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

Matthew Roh
fuente
1
Debe indicar claramente que se trata de código de golf , aunque esté etiquetado.
Sr. Xcoder
2
¿Puede alguien enlace a la OEIS para esto (Asumo que es uno con el número de secuencias de partición que hemos estado corriendo en el puesto del CNR OEIS)
Stephen
3
Creo que el último caso de prueba debería ser 8
H.PWiz
2
Estoy de acuerdo con H.PWiz en que el último caso de prueba debería ser en 8lugar de 7.
Erik the Outgolfer
2
A008284
millas

Respuestas:

3

Swift , 76 73 bytes

func P(_ n:Int,_ k:Int)->Int{return n*k>0 ?P(n-k,k)+P(n-1,k-1):n==k ?1:0}

Prué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 enteros ny k, y le dan un tipo de retorno de Int, 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. returnobviamente 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 bytes n>0&&k>0. Si la condición es verdadera (ambos enteros son aún más altos que 0), entonces recurrimos recursivamente a nuestra función con ndecrementado por kcomo nuevo ny kpermanece igual, y sumamos el resultado de P()con ny kdecrementado por 1. Si la condición no es verdadera , devolvemos cualquiera 1o 0dependiendo de si nes igual a k.

¿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 Pdos veces, agregando los resultados de P(n-k,k)y P(n-1,k-1). Y volvemos a recorrerlo hasta que nllegue a 0.


* Nota: los espacios no se pueden eliminar.

Sr. Xcoder
fuente
2

Python 2 , 61 55 51 50 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

P=lambda n,k:n*k>0and P(n-k,k)+P(n-1,k-1)or+(n==k)

Pruébalo en línea!

totalmente humano
fuente
1
Esto se rompe en el último caso de prueba de 10, 3. Demasiada recursión
jkelm
1
(n>0and k>0)->n>0<k
Erik the Outgolfer
1
También puedes hacerlo en +(n==k)lugar de [0,1][n==k].
Erik the Outgolfer
1
No necesitas el espacio adentro or +.
Erik the Outgolfer
1
50 bytes , reemplace n>0<k andconn*k>0and
Sr. Xcoder
2

Mathematica, 33 bytes

Length@IntegerPartitions[#,{#2}]&

aquí está la tabla nxk

 \k->
 n1  0  0   0   0   0   0   0   0   0  
 |1  1  0   0   0   0   0   0   0   0  
 v1  1  1   0   0   0   0   0   0   0  
  1  2  1   1   0   0   0   0   0   0  
  1  2  2   1   1   0   0   0   0   0  
  1  3  3   2   1   1   0   0   0   0  
  1  3  4   3   2   1   1   0   0   0  
  1  4  5   5   3   2   1   1   0   0  
  1  4  7   6   5   3   2   1   1   0  
  1  5  8   9   7   5   3   2   1   1  
J42161217
fuente
1
Por supuesto. Sabía que había un edificio incorporado.
Matthew Roh
Un puerto simplificado de Mathematica ahorraría 13 bytes aquí, creo ( Length-> Len`1y IntegerPartitions->Int`7
Jonathan Allan
@ JonathanAllan Realmente estoy haciendo una versión súper corta de esto. Espero poder terminarlo para fin de mes
JungHwan Min
2

JavaScript (ES6), 42 40 39 bytes

Creo que esto funciona.

f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y

Intentalo

k.value=(
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y
)(i.value=10,j.value=3)
onchange=_=>k.value=f(+i.value,+j.value)
*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}
<label for=i>n: </label><input id=i type=number><label for=j>k: </label><input id=j type=number><label for=k>P<sub>k</sub>(n): </label><input id=k readonly>

Lanudo
fuente
2

MATL , 14 bytes

y:Z^!S!Xu!Xs=s

Pruébalo en línea!

Explicación

Considere insumos 6, 2.

y     % Implicitly take the two inputs. Duplicate from below
      % STACK: 6, 2, 6
:     % Range
      % STACK: 6, 2, [1 2 3 4 5 6]
Z^    % Cartesian power
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 1; 2 2; ...; 6 6]
!S!   % Sort each row
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 1 2; 2 2; ...; 6 6]
Xu    % Unique rows
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 2; ...; 6 6]
!Xs   % Sum of each row, as a row vector
      % STACK: 6, [2 3 ... 6 7 4 ... 12]
=     % Equals, element-wise
      % STACK: [0 0 ... 1  0 0 ... 0]
s     % Sum. Implicitly display
      % STACK: 3
Luis Mendo
fuente
Sinceramente, me sorprende que MATL no tenga una "partición entera" integrada o algo así.
Erik the Outgolfer
@Sanchises Debería estar funcionando ahora. ¡Gracias por decirme!
Luis Mendo
No hay problema. Solo estaba jugando con él para comprender su método (que generalmente es más fácil para casos pequeños) cuando me encontré con el error.
Sanchises
0

Jalea , 13 bytes

¡Tengo la sensación de que este enfoque básico no será el más golfista!

RŒṖL€€Ṣ€QṀ€=S

Pruébalo en línea!

Jonathan Allan
fuente
Sí, no lo es (mira mi respuesta de Jelly en el fondo).
Erik the Outgolfer
Oh no hay bolos de código
Matthew Roh
@EriktheOutgolfer Si funciona, ¿por qué se elimina?
Jonathan Allan
@Jonathan refrescar
Matthew Roh
@ JonathanAllan Se eliminó antes de que se corrigiera un caso de prueba.
Erik the Outgolfer
0

Scala , 73 bytes

Bueno, este es un uso fácil y sencillo de la punta de OP.

ky nson los parámetros de mi función recursiva f. Ver enlace TIO para el contexto.

Como esto es recursivo, ¿debo incluir la función def en el conteo de bytes?

(k,n)match{case(0,0)=>1
case _ if k<1|n<1=>0
case _=>f(n-k,k)+f(n-1,k-1)}

Pruébalo en línea!

V. Courtois
fuente
0

R (+ pryr), 49 bytes

f=pryr::f(`if`(k<1|n<1,!n+k,f(n-k,k)+f(n-1,k-1)))

Que evalúa la función recursiva

function (k, n) 
if (k < 1 | n < 1) !n + k else f(n - k, k) + f(n - 1, k - 1)

(k < 1 | n < 1)comprueba si se cumple alguno de los estados iniciales. !n + kevalúa como TRUE (1) si ambos ny kson 0, y FALSE (0) en caso contrario. f(n - k, k) + f(n - 1, k - 1)maneja la recursividad.

JAD
fuente