8
\$\begingroup\$

Pk(n) means the amount of partitions of n into exactly k parts. Given n and k, calculate Pk(n).

Tip: Pk(n) = Pk(n−k) + Pk−1(n−1), with initial values p0(0) = 1 and pk(n) = 0 if n ≤ 0 or k ≤ 0. [Wiki]

Examples

n    k    Ans
1    1    1
2    2    1
4    2    2
6    2    3
10   3    8

Rules

\$\endgroup\$
  • 1
    \$\begingroup\$ You should clearly state that this is code-golf, even though it's tagged. \$\endgroup\$ – Mr. Xcoder Jul 26 '17 at 14:01
  • 2
    \$\begingroup\$ Can someone link to the OEIS for this (I assume there is one with the number of partition sequences we've been running into on the CnR OEIS post) \$\endgroup\$ – Stephen Jul 26 '17 at 14:03
  • 3
    \$\begingroup\$ I think the last test case should be 8 \$\endgroup\$ – H.PWiz Jul 26 '17 at 14:12
  • 2
    \$\begingroup\$ I agree with H.PWiz that the last testcase should be 8 instead of 7. \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:19
  • 2
    \$\begingroup\$ A008284 \$\endgroup\$ – miles Jul 26 '17 at 14:26

16 Answers 16

3
\$\begingroup\$

Pyth, 9 7 6 bytes

-1 byte thanks to Erik the Outgolfer!

/lM./E

Try it online!

Inputs to the program are reversed (i.e. k, n).

\$\endgroup\$
3
\$\begingroup\$

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}

Try it online!


Explanation

How does the code structurally work?

First of all, we define our function P, with two integer parameters n and k, and give it a return type of Int, with this piece of code: func P(_ n:Int,_ k:Int)->Int{...}. The cool trick here is that we tell the compiler to ignore the names of the parameters, with _ followed by a space, which saves us two bytes when we call the function. return is obviously used to return the result of our nested ternary described below.

Another trick I used was n*k>0, which saves us a couple of bytes over n>0&&k>0. If the condition is true (both the integers are still higher than 0), then we recursively call our function with n decremented by k as our new n and k stays the same, and we add the result of P() with n and k decremented by 1. If the condition is not true, we return either 1 or 0 depending on whether n is equal to k.

How does the recursive algorithm work?

We know that the first element of the sequence is p0(0), and so we check that both integers are positive (n*k>0). If they are not higher than 0, we check if they are equal (n==l ?1:0), here being two cases:

  • There is exactly 1 possible partition, and thus we return 1, if the integers are equal.

  • There are no partitions if one of them is already 0 and the other is not.

However, if both are positive, we recursively call P twice, adding the results of P(n-k,k) and P(n-1,k-1). And we loop again until n has reached 0.


* Note: The spaces cannot be removed.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 6 bytes

œċS€ċ⁸

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Ah ha, of course! \$\endgroup\$ – Jonathan Allan Jul 26 '17 at 14:31
2
\$\begingroup\$

Python 2, 61 55 51 50 bytes

-10 bytes thanks to Erik the Outgolfer. -1 byte thanks to Mr. Xcoder.

I will say, I did copy the hint from OP and translate it to Python. :P

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This breaks on the last test case of 10, 3. Too much recursion \$\endgroup\$ – jkelm Jul 26 '17 at 14:18
  • 1
    \$\begingroup\$ (n>0and k>0) -> n>0<k \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:19
  • 1
    \$\begingroup\$ Also you can do +(n==k) instead of [0,1][n==k]. \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:23
  • 1
    \$\begingroup\$ You don't need the space in or +. \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:26
  • 1
    \$\begingroup\$ 50 bytes, replace n>0<k and with n*k>0and \$\endgroup\$ – Mr. Xcoder Jul 26 '17 at 14:46
2
\$\begingroup\$

Mathematica, 33 bytes

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

here is n x k table

 \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  
\$\endgroup\$
  • 1
    \$\begingroup\$ Of course. I knew there was a builtin. \$\endgroup\$ – Matthew Roh Jul 26 '17 at 14:17
  • \$\begingroup\$ A Mathematica Simplified port would save a 13 bytes here I believe (Length->Len`1 and IntegerPartitions -> Int`7 \$\endgroup\$ – Jonathan Allan Jul 26 '17 at 14:44
  • \$\begingroup\$ @JonathanAllan I'm actually making a super-short version of this. Hopefully I can finish it by the end of the month \$\endgroup\$ – JungHwan Min Jul 26 '17 at 16:50
2
\$\begingroup\$

JavaScript (ES6), 42 40 39 bytes

I think this works.

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

Try it

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>

\$\endgroup\$
2
\$\begingroup\$

MATL, 14 bytes

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

Try it online!

Explanation

Consider inputs 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
\$\endgroup\$
  • \$\begingroup\$ Honestly I'm surprised MATL doesn't have an "integer partition" builtin or something. \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:25
  • \$\begingroup\$ @Sanchises It should be working now. Thanks for telling me! \$\endgroup\$ – Luis Mendo Jul 26 '17 at 19:14
  • \$\begingroup\$ No problem. I was just playing with it to understand your method (which is generally easier for small cases) when I ran into the error. \$\endgroup\$ – Sanchises Jul 26 '17 at 20:22
1
\$\begingroup\$

Haskell, 41 bytes

0#0=1
n#k|n*k>0=(n-k)#k+(n-1)#(k-1)
_#_=0

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 41 bytes

n&0=0^n
n&k=sum$map(&(k-1))[n-1,n-k-1..0]

Try it online!

An alternate recurrence.

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 35 bytes

Pari/GP has a built-in for iterating over integer partitions.

n->k->i=0;forpart(x=n,i++,,[k,k]);i

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 13 bytes

I have a feeling know this basic approach won't be the golfiest!

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Yeah it isn't (see my Jelly answer at the far bottom). \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:29
  • \$\begingroup\$ Oh no Code bowling \$\endgroup\$ – Matthew Roh Jul 26 '17 at 14:30
  • \$\begingroup\$ @EriktheOutgolfer If it works why is it deleted? \$\endgroup\$ – Jonathan Allan Jul 26 '17 at 14:30
  • \$\begingroup\$ @Jonathan refresh \$\endgroup\$ – Matthew Roh Jul 26 '17 at 14:31
  • \$\begingroup\$ @JonathanAllan It was deleted before a test case was fixed. \$\endgroup\$ – Erik the Outgolfer Jul 26 '17 at 14:32
0
\$\begingroup\$

05AB1E, 9 bytes

L²ã€{ÙO¹¢

Try it online!

\$\endgroup\$
0
\$\begingroup\$

CJam, 18 bytes

{_,:)@m*:$_&::+e=}

Try it online!

Expects inputs in reverse, i.e. k n instead of n k.

\$\endgroup\$
0
\$\begingroup\$

Scala, 73 bytes

Well this is some easy unreworked use of OP's tip.

k and n are the parameters of my recursive function f. See TIO link for context.

Since this is recursive, should I include function def in byte count?

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 41 bytes

f(n,k){n=n*k>0?f(n-k,k)+f(--n,--k):n==k;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R (+ pryr), 49 bytes

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

Which evaluates to the recursive function

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

(k < 1 | n < 1) checks if any of the initial states are met. !n + k evaluates to TRUE (1) if both n and k are 0, and FALSE (0) otherwise. f(n - k, k) + f(n - 1, k - 1) handles the recursion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.