13
\$\begingroup\$

\$P_k(n)\$ means the number of partitions of \$n\$ into exactly \$k\$ positive parts. Given \$n\$ and \$k\$, calculate \$P_k(n)\$.

Tip: \$P_k(n) = P_k(n−k) + P_{k−1}(n−1)\$, with initial values \$P_0(0) = 1\$ and \$P_k(n) = 0\$ if \$n \leq 0\$ or \$k \leq 0\$. [Wiki]

Examples

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

Rules

\$\endgroup\$
11
  • 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, 2017 at 14:03
  • \$\begingroup\$ Related \$\endgroup\$
    – miles
    Jul 26, 2017 at 14:14
  • 2
    \$\begingroup\$ A008284 \$\endgroup\$
    – miles
    Jul 26, 2017 at 14:26
  • 1
    \$\begingroup\$ This needs more detail. Can 0 be a partition element? Can a partition contain duplicates? Do we count only increasing partitions? \$\endgroup\$
    – Zgarb
    Jul 26, 2017 at 15:37
  • 1
    \$\begingroup\$ @Zgarb it could help to add such information to the post, yes. But to address these questions "an integer partition is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.", so: no zeros inside; duplicates are acceptable; disregard order for counting. (Note that P(0,0) is 1 however - one way to have the empty set). \$\endgroup\$ Jul 26, 2017 at 16:10

19 Answers 19

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

Jelly, 6 bytes

œċS€ċ⁸

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Ah ha, of course! \$\endgroup\$ Jul 26, 2017 at 14:31
3
\$\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\$
3
  • 1
    \$\begingroup\$ Of course. I knew there was a builtin. \$\endgroup\$ Jul 26, 2017 at 14:17
  • \$\begingroup\$ A Mathematica Simplified port would save a 13 bytes here I believe (Length->Len`1 and IntegerPartitions -> Int`7 \$\endgroup\$ Jul 26, 2017 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\$ Jul 26, 2017 at 16:50
3
\$\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\$
3
\$\begingroup\$

Haskell, 41 bytes

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

Try it online!

\$\endgroup\$
3
\$\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\$
3
  • \$\begingroup\$ Honestly I'm surprised MATL doesn't have an "integer partition" builtin or something. \$\endgroup\$ Jul 26, 2017 at 14:25
  • \$\begingroup\$ @Sanchises It should be working now. Thanks for telling me! \$\endgroup\$
    – Luis Mendo
    Jul 26, 2017 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, 2017 at 20:22
2
\$\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\$
2
\$\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\$
2
\$\begingroup\$

05AB1E, 5 bytes

ÅœIùg

Try it online or verify all test cases.

Explanation:

Ŝ     # Get all lists of positive integers that sum to the first (implicit) 
       # input-integer `n`
   ù   # Only keep the lists with a length equal to
  I    # the second input-integer `k`
    g  # Pop and push the length to get the amount of remaining lists
       # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 41 40 bytes

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

Try it online!

\$\endgroup\$
1
\$\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\$
5
  • \$\begingroup\$ Yeah it isn't (see my Jelly answer at the far bottom). \$\endgroup\$ Jul 26, 2017 at 14:29
  • \$\begingroup\$ Oh no Code bowling \$\endgroup\$ Jul 26, 2017 at 14:30
  • \$\begingroup\$ @EriktheOutgolfer If it works why is it deleted? \$\endgroup\$ Jul 26, 2017 at 14:30
  • \$\begingroup\$ @Jonathan refresh \$\endgroup\$ Jul 26, 2017 at 14:31
  • \$\begingroup\$ @JonathanAllan It was deleted before a test case was fixed. \$\endgroup\$ Jul 26, 2017 at 14:32
1
\$\begingroup\$

05AB1E, 9 bytes

L²ã€{ÙO¹¢

Try it online!

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

CJam, 18 bytes

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

Try it online!

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

\$\endgroup\$
1
\$\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\$
1
\$\begingroup\$

Scala, 98 bytes

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

k and n are the parameters of my recursive function f.

def f(n:Int,k:Int):Int={(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\$
1
  • \$\begingroup\$ This is invalid as it's a snippet, not a proper function. \$\endgroup\$
    – emanresu A
    Jun 12 at 22:23
1
\$\begingroup\$

Vyxal, 5 bytes

ṄvL=∑

Try it Online!

Jelly, 5 bytes

ŒṗẈ=S

Try it online!

Dang it, ninja'd by Kevin because I took the time to get the shortest jelly answer too :p

Exact same approach as the 05ab1e answer, derived independently - both answers get the integer partitions of the first input and then count the number of partitions where the length equals the second input.

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

Regex 🐇 (Perl/PCRE+(?^=)RME), 32 28 bytes

^((?^=(\2?x))(\1|^x)x*)+,\2$

Try it on replit.com (RegexMathEngine)

Takes its input in unary, as the lengths of two strings of xs delimited by a ,, specifying \$(n,k)\$. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

This simply enumerates all the partitions. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary-sized partition on the first iteration, then increasing it by an arbitrary nonnegative integer on each subsequent iteration. Each iteration increments the counter, which is then compared with \$k\$ at the end.

On each iteration, the size of the partition (arbitrarily chosen) is captured in \1, which is accessed via a nested backreference. The counter is stored in \2. Lookinto is used to ensure there is room to read and increment \2 on each iteration.

^                   # tail = N
(                   # \1 = the following, looping:
    (?^=            # Lookinto; tail = N
        (           # \2 = sum of the following:
            \2?     # previous value of \2 if set, else 0
            x       # 1
        )
    )
    # \1 = the sum of the below items
    (
        \1          # On subsequent iterations, \1
    |
        ^x          # On the first iteration, 1
    )
    x*              # any nonnegative integer
    # \1 = some of the above items
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

This uses nested backreferences (supported by Java / Perl / PCRE / .NET), a branch reset group (Perl / PCRE / Pythonregex), and a lookinto, a feature just added to RegexMathEngine. The parameterless form of it, (?^=pattern), is equivalent to one of the common uses of variable-length lookbehind, (?<=(?=pattern)^.*) – it allows matching against the entire string, even after the top-level cursor has advanced past the start. It also has a parametrized form, e.g. (?^5=pattern) will match pattern against the current contents of \5.

Regex 🐇 (RME / Perl / PCRE2 v10.35+), 36 34 bytes

^((?|(?=.*,(\2x))\1x*|^(x)+))+,\2$

Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only

Without lookinto, there's still always room within \$k\$, accesible via lookahead, to count iterations.

Starting with a positive arbitrary-sized partition on the first iteration is done by ^(x)+, which also initializes the counter to \$1\$. On subsequent iterations, \1x* advances by the sum of \1 and any arbitrary nonnegative integer, which also gets captured in \1. At the end, , asserts that the cumulative sum is equal to \$n\$.

To enforce \$k\$ as the number of partitions, it starts by setting \2 \$=1\$ on the first iteration with ^(x)+. On subsequent iterations, (?^=(\2x)) increments \2 by \$1\$. Lookahead is used to avoid not having room for \2\$+1\$ when nearing the end of \$n\$. The Branch Reset Group (?|...|...) allows \2 to be captured/recaptured in these two places.

^                   # tail = N
(                   # \1 = the following, looping:
    (?|             # Branch Reset Group
        # This alternative can only match on iterations after the first, because
        # it unconditionally matches \1 and \2.
        (?=         # Lookahead
            .*,     # tail = K
            (\2x)   # \2 += 1
        )
        \1x*        # \1 += {any nonnegative integer}; tail -= \1
    |
        ^           # Anchor to start, to only match on the first iteration.
        (x)+        # \2 = 1; \1 = {any nonnegative integer}; tail -= \1
    )
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

Regex 🐇 (RME / Perl / PCRE2), 50 bytes

^((?=(?(3)(\3)))((?|(?=.*,(\4x))\2x*|^(x)+)))+,\4$

Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied back and forth between \2 and \3 using only forward-declared backreferences.

This would also make the regex compatible with Pythonregex and Ruby, but they have no way of doing 🐇 output without source code modifications.

It still doesn't work under PCRE1, probably due to its bug where in certain conditions, captures are not reverted to their earlier values when backtracking: Try it online!

^                      # tail = N
(                      # \1 = the following, looping:
    (?=
        (?(3)(\3))     # If \3 is set, \2 = \3, else leave \2 unset
    )
    (                  # \3 = the following, to avoid a nested backreference
        (?|            # Branch Reset Group
            # This alternative can only match on iterations after the first,
            # because it unconditionally matches \1 and \2.
            (?=
                .*,    # tail = K
                (\4x)  # \4 += 1
            )
            \2x*       # \3 = \2 + {any nonnegative integer}; tail -= \3
        |
            ^          # Anchor to start, to only match on the first iteration.
            (x)+       # \4 = 1; \3 = {any nonnegative integer}; tail -= \3
        )
    )
)+                     # Iterate the above as many times as possible, min 1
,                      # Assert tail == 0; tail = K
\4$                    # Assert tail == \4
\$\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.