16
\$\begingroup\$

The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the number 4 has the following partitons:

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Hence, it has 5 partitions. This is OEIS A000041.


Task

Given a positive integer N determine its partition number.

  • All standard rules apply.

  • The input and output may be handled through any reasonable mean.

  • This is , so the shortest code in bytes wins.


Test Cases

Input | Output

1  |  1
2  |  2
3  |  3
4  |  5
5  |  7
6  |  11
7  |  15
8  |  22
9  |  30
10 |  42
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm almost positive this is a duplicate... \$\endgroup\$ – James Aug 31 '17 at 15:36
  • \$\begingroup\$ @DJMcMayhem Umm, ok. Let me know if you find a duplicate. Sorry, I'm new to all this! \$\endgroup\$ – user70974 Aug 31 '17 at 15:37
  • 1
    \$\begingroup\$ @DJMcMayhem maybe this question you asked since it's a short step from "generating" to "counting" but you don't necessarily have to generate all the partitions to count them... \$\endgroup\$ – Giuseppe Aug 31 '17 at 15:51
  • 1
    \$\begingroup\$ this one is a dupe, EXCEPT that is a popcon(?) and closed as too broad. IMHO this is WAY better written and should be keep open, while the old one should be (reopened and) closed as dupe \$\endgroup\$ – Rod Aug 31 '17 at 15:51
  • 2
    \$\begingroup\$ @Rod, it's a bad pop-con, but switching the close reason to dupe wouldn't be an improvement. The performance requirement there would be an obstacle to porting some answers (no-one's going to generate the 24061467864032622473692149727991 partitions of 1000 in a couple of minutes); and the Hardy-Ramanujan-Rademacher implementation is not exactly golfed... However, it may be worth opening a discussion in meta about what to do with this question and that one. \$\endgroup\$ – Peter Taylor Aug 31 '17 at 16:04

16 Answers 16

13
\$\begingroup\$

Pyth, 3 bytes

l./

Try it here! or Try a test Suite.

The answer took much longer to format than writing the code itself :P.


How?

Pyth is the right tool for the job.

l./   Full program with implicit input.

 ./   Integer partitions. Return all sorted lists of positive integers that add to the input.
l     Length.
      Implicitly output the result.
|improve this answer|||||
\$\endgroup\$
34
\$\begingroup\$

Mathematica, 11 bytes

PartitionsP

Explanation

ยฏ\_(ใƒ„)_/ยฏ
|improve this answer|||||
\$\endgroup\$
8
\$\begingroup\$

Python 2, 85 83 bytes

-2 bytes thanks to @notjagan

lambda n:n<1or sum(sum(i*((n-k)%i<1)for i in range(1,n+1))*p(k)for k in range(n))/n

Try it online!

Using recursive formula from OEIS A000041.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 83 bytes. \$\endgroup\$ – notjagan Aug 31 '17 at 17:12
  • \$\begingroup\$ 84 bytes. ==0 is equivalent to <1 in this case. EDIT: Use notjagan's approach \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 17:13
  • \$\begingroup\$ @Mr.Xcoder The original code actually had <1 instead of ==0, but the TIO code didn't. \$\endgroup\$ – notjagan Aug 31 '17 at 17:13
  • \$\begingroup\$ Also 83 bytes. \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 17:17
8
\$\begingroup\$

Emojicode 0.5, 204 201 bytes

๐Ÿ‹๐Ÿš‚๐Ÿ‡๐Ÿ–๐Ÿ…ฐ๏ธโžก๐Ÿš‚๐Ÿ‡๐ŸŠโฌ…๐Ÿ•1๐Ÿ‡๐ŸŽ1๐Ÿ‰๐Ÿฎs 0๐Ÿ”‚kโฉ0๐Ÿ•๐Ÿ‡๐Ÿฆtโž–๐Ÿ•k๐Ÿฎr t๐Ÿ”‚iโฉ1 t๐Ÿ‡๐ŸŠ๐Ÿ˜›๐Ÿšฎt i 0๐Ÿ‡๐Ÿฎโž•r i๐Ÿ‰๐Ÿ‰๐Ÿฎโž•sโœ–r๐Ÿ…ฐ๏ธk๐Ÿ‰๐ŸŽโž—s๐Ÿ•๐Ÿ‰๐Ÿ‰

Try it online!

-3 bytes by using "less than or equal to 1" instead of "less than 2" because the "less than" emoji has a quite long UTF-8 encoding. Also made t a frozen to silence a warning without affecting the byte count.

Extends the ๐Ÿš‚ (integer) class with a method named ๐Ÿ…ฐ๏ธ. You can write a simple program that takes a number from the input, calls ๐Ÿ…ฐ๏ธ on the number and prints the result like this:

๐Ÿ๐Ÿ‡
 ๐Ÿฆstr๐Ÿ”ท๐Ÿ”ก๐Ÿ˜ฏ๐Ÿ”คPlease enter a number๐Ÿ”ค
 ๐ŸŠ๐Ÿฆnum๐Ÿš‚str 10๐Ÿ‡
  ๐Ÿ˜€๐Ÿ”ก๐Ÿ…ฐ๏ธnum 10
 ๐Ÿ‰๐Ÿ“๐Ÿ‡
  ๐Ÿ˜€๐Ÿ”คLearn what a number is, you moron!๐Ÿ”ค
 ๐Ÿ‰
๐Ÿ‰

This part could be golfed a lot by omitting the messages and error handling, but it's not included in the score, so I prefer to show more features of Emojicode instead, while improving readability along the way.

Ungolfed

๐Ÿ‹๐Ÿš‚๐Ÿ‡
 ๐Ÿ–๐Ÿ…ฐ๏ธโžก๐Ÿš‚๐Ÿ‡
  ๐ŸŠโ—€๏ธ๐Ÿ•2๐Ÿ‡
   ๐ŸŽ1
  ๐Ÿ‰
  ๐Ÿฎsum 0
  ๐Ÿ”‚kโฉ0๐Ÿ•๐Ÿ‡
   ๐Ÿฆnmkโž–๐Ÿ•k
   ๐Ÿฎsig nmk
   ๐Ÿ”‚iโฉ1 nmk๐Ÿ‡
    ๐ŸŠ๐Ÿ˜›๐Ÿšฎnmk i 0๐Ÿ‡
     ๐Ÿฎโž•sig i
    ๐Ÿ‰
   ๐Ÿ‰
   ๐Ÿฎโž•sumโœ–sig๐Ÿ…ฐ๏ธk
  ๐Ÿ‰
  ๐ŸŽโž—sum๐Ÿ•
 ๐Ÿ‰
๐Ÿ‰

Explanation

Note: a lot of emoji choice doesn't make much sense in emojicode 0.5. It's 0.x, after all. 0.6 will fix this.

Emojicode is an object-oriented programming language featuring generics, protocols, optionals and closures, but this program uses no closures and all generics and protocols can be considered implicit, while the only optional appears in the I/O stub.

The program operates on only a few types: ๐Ÿš‚ is the integer type, ๐Ÿ”ก is the string type and โฉ is the range type. A few booleans (๐Ÿ‘Œ) appear too, but they are only used in conditions. Booleans can take a value of ๐Ÿ‘ or ๐Ÿ‘Ž, which correspond to true and false, respectively.

There are currently no operators in Emojicode, so addition, comparsions and other operations that are normally operators are implemented as functions, effectively making the expressions use prefix notation. Operators are also planned in 0.6.

Let's tackle the test program first.

๐Ÿ

This is the ๐Ÿ block, which can be compared to main from other languages.

๐Ÿ‡ ... ๐Ÿ‰

Grapes and watermelons declare code blocks in emojicode.

๐Ÿฆstr๐Ÿ”ท๐Ÿ”ก๐Ÿ˜ฏ๐Ÿ”คPlease enter a number๐Ÿ”ค

This declares a "frozen" named str and sets it value to a new string created using the initializer (constructor) ๐Ÿ˜ฏ, which takes a prompt as a string and then inputs a line from the user. Why use a frozen instead of a variable? It won't change, so a variable would emit a warning.

๐ŸŠ๐Ÿฆnum๐Ÿš‚str 10

Let's break it down. ๐Ÿš‚str 10 calls the ๐Ÿš‚ method on the str frozen with the argument 10. By convention, methods named with the name of a type convert the object to that type. 10 is the base to use for integer conversion. This method returns an optional, ๐Ÿฌ๐Ÿš‚. Optionals can contain a value of the base type or nothingness, โšก. When the string doesn't contain a number, โšก is returned. To use the value, one has to unwrap the optional using ๐Ÿบ, which raises a runtime error if the value is โšก. Therefore, it is good practice to check for nothingness before unwrapping an optional. It is so common, in fact, that Emojicode has a shorthand for that. Normally, ๐ŸŠ is an "if". ๐ŸŠ๐Ÿฆ variable expression means: evaluate the expression. If the optional contains nothingness, the condition evaluates to ๐Ÿ‘Ž (false). Otherwise, a frozen named variable is created with the unwrapped value of the optional, and the condition evaluates to ๐Ÿ‘, (true). Therefore, in normal usage, the ๐Ÿ‡ ... ๐Ÿ‰ block following the conditional is entered.

๐Ÿ˜€๐Ÿ”ก๐Ÿ…ฐ๏ธnum 10

๐Ÿ…ฐ๏ธ is the method the main code adds to ๐Ÿš‚ using ๐Ÿ‹ that calculates the number of partitions. This calls ๐Ÿ…ฐ๏ธ on the num frozen we declared in the conditional and converts the result to a string using base 10 by the ๐Ÿ”ก method. Then, ๐Ÿ˜€ prints the result.

๐Ÿ“๐Ÿ‡ ... ๐Ÿ‰

๐Ÿ“ means "else", so this block is entered when the user did not enter a number correctly.

๐Ÿ˜€๐Ÿ”คLearn what a number is, you moron!๐Ÿ”ค

Prints the string literal.

Now, let's look at the main program. I'll explain the ungolfed version; the golfed version just had the whitespace removed and variables renamed to single letter names.

๐Ÿ‹๐Ÿš‚๐Ÿ‡ ... ๐Ÿ‰

Extend the ๐Ÿš‚ class. This is a feature that is not commonly found in programming languages. Instead of creating a new class with ๐Ÿš‚ as the superclass, ๐Ÿ‹ modifies ๐Ÿš‚ directly.

๐Ÿ–๐Ÿ…ฐ๏ธโžก๐Ÿš‚๐Ÿ‡ ... ๐Ÿ‰

Creates a new method named ๐Ÿ…ฐ๏ธ that returns a ๐Ÿš‚. It returns the number of partitions calculated using the formula a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)

๐ŸŠโฌ…๐Ÿ•1๐Ÿ‡
 ๐ŸŽ1
๐Ÿ‰

๐Ÿ• is similar to this or self from other languages and refers to the object the method was called on. This implementation is recursive, so this is the terminating condition: if the number the method was called on is less than or equal 1, return 1.

๐Ÿฎsum 0

Create a new variable sum and set it to 0. Implicitly assumes type ๐Ÿš‚.

๐Ÿ”‚kโฉ0๐Ÿ•

๐Ÿ”‚ iterates over anything that implements the ๐Ÿ”‚๐Ÿšโšช๏ธ protocol, while โฉ is a range literal that happens to implement ๐Ÿ”‚๐Ÿš๐Ÿš‚. A range has a start value, a stop value and a step value, which is assumed to be 1 if start < stop, or -1 otherwise. One can also specify the step value by using the โญ to create the range literal. The start value is inclusive, while the stop value is exclusive, so this is equivalent to for k in range(n) or the Sum_{k=0..n-1} in the formula.

๐Ÿฆnmkโž–๐Ÿ•k

We need to calculate sigma(n - k), or the sum of divisors of n - k in other words, and the argument is needed a few times, so this stores n - k in the variable nmk to save some bytes.

๐Ÿฎsig nmk
๐Ÿ”‚iโฉ1 nmk

This sets the sig variable to the argument of sigma and iterates over all numbers from 1 to nmk - 1. I could initialize the variable to 0 and iterate over 1..nmk but doing it this way is shorter.

๐ŸŠ๐Ÿ˜›๐Ÿšฎnmk i 0

๐Ÿšฎ calculates the remainder, or modulus and ๐Ÿ˜› checks for equality, so the condition will be ๐Ÿ‘ if i is a divider of nmk.

๐Ÿฎโž•sig i

This is an assignment by call, similar to the += -= >>= operator family in some of the inferior, emoji-free languages. This line can be also written as ๐Ÿฎ sig โž• sig i. Therefore, after the inner loop finishes, sig will contain the sum of divisors of n - k, or sigma(n - k)

๐Ÿฎโž•sumโœ–sig๐Ÿ…ฐ๏ธk

Another assignment by call, so this adds sigma(n - k) * A(k) to the total, just as in the formula.

๐ŸŽโž—sum๐Ÿ•

Finally, the sum is divided by n and the quotient is returned. This explanation probably took thrice as much time as writing the code itself...

|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

Pari/GP, 8 bytes

numbpart

Try it online!

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Octave, 18 bytes

partcnt(input(''))

Uses the built-in function partcnt.

Can't get it right by using an anonymous function using @, some help would be appreciated.

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Retina, 34 bytes

.+
$*
+%1`\B
;$'ยถ$`,
,

%O`1+
@`.+

Try it online!

Explanation

.+
$*

Convert the input to unary.

+%1`\B
;$'ยถ$`,

This computes all 2n-1 partitions of the unary digit list. We do this by repeatedly (+) matching the first (1) non-word boundary (\B, i.e. a position between two 1s) in each line (%) and replacing it with ;, everything after it ($'), a linefeed (ยถ), everything in front of it ($`) and ,. Example:

1;1,111

Becomes

      vv
1;1,1;11
1;1,1,11
^^^^^

Where v marks the result of $' and ^ marks the result $`. This is a common idiom to get the result of two different replacements at once (we basically insert both the ; and the , replacement, as well as the missing "halves" of the string to complete two full substitutions).

We will treat ; as actual partitions and , just as placeholders that prevent subsequent \B from matching there. So next...

,

... we remove those commas. That gives us all the partitions. For example for input 4 we get:

1;1;1;1
1;1;11
1;11;1
1;111
11;1;1
11;11
111;1
1111

We don't care about the order though:

%O`1+

This sorts the runs of 1s in each line so we get unordered partitions.

@`.+

Finally, we count the unique (@) matches of .+, i.e. how many distinct lines/partitions we've obtained. I added this @ option ages ago, then completely forgot about it and only recently rediscovered it. In this case, it saves a byte over first deduplication the lines with D`.

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Python 2, 54 53 bytes

f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n/2+1))

Try it online!

How it works

Each partition of n can be represented as a list x = [x1, โ‹ฏ, xm] such that x1 + โ‹ฏ + xm = n. This representation becomes unique if we require that x1 โ‰ค โ‹ฏ โ‰ค xm.

We define an auxiliary function f(n, k) that counts the partitions with lower bound k, i. e., the lists x such that x1 + โ‹ฏ + xm = n and k โ‰ค x1 โ‰ค โ‹ฏ โ‰ค xm. For input n, the challenge thus asks for the output of f(n, 1).

For positive integers n and k such that k ≤ n, there is at least one partition with lower bound k: the singleton list [n]. If n = k (in particular, if n = 1), this is the only eligible partition. On the other hand, if k > n, there are no solutions at all.

If k < n, we can recursively count the remaining partitions by building them from left to right, as follows. For each j such that k ≤ j ≤ n/2, we can build partitions [x1, โ‹ฏ, xm] = [j, y1, โ‹ฏ, ym-1]. We have that x1 + โ‹ฏ + xm = n if and only if y1 + โ‹ฏ + ym-1 = n - j. Furthermore, x1 โ‰ค โ‹ฏ โ‰ค xm if and only if j ≤ y1 โ‰ค โ‹ฏ โ‰ค ym-1.

Therefore, the partitions x of n that begin with j can be calculated as f(n - j, j), which counts the valid partitions y. By requiring that j ≤ n/2, we assure that j ≤ n - j, so there is at least one y. We can thus count all partitions of n by summing 1 (for [n]) and f(n - j, j) for all valid values of j.

The code is a straightforward implementation of the mathematical function f. In addition, it makes k default to 1, so f(n) computes the value of f(n, 1) for input n.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Oh wow, this is incredible! Can you add an explanation on how this works? \$\endgroup\$ – user70974 Sep 5 '17 at 16:12
  • \$\begingroup\$ I've edited my answer. If anything is unclear, please let me know. \$\endgroup\$ – Dennis Sep 6 '17 at 5:20
3
\$\begingroup\$

J, 37 35 bytes

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:

Try it online!

Explanation

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:  Input: n
                                 1:  Constant 1
  ]                                  Get n
   1&(                          )    Repeat n times on x = [1]
                          \            For each prefix
                         #               Length
                      q:@                Prime factors
                 /.~&                    Group equal factors
              #.~                        Compute p+p^2+...+p^k for each group
           >:@                           Increment
                    &.q:                 Product
                           %           Divide
                            #          Length
         ]                             Get x
          *                            Times
   1   #.                              Sum
                              ,        Joim
                               ]       Get x
                                       Set this as next value of x
0{                                   Select value at index 0
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I'm dumbstruck and dumbfounded, mind posting an explanation? \$\endgroup\$ – cole Sep 1 '17 at 5:13
  • 1
    \$\begingroup\$ @cole This is an iterative approach that starts with the solution for p(0) = 1, and builds the next using the formula p(n) = sum(sigma(n-k) * p(k) for k = 0 to n-1) / n. I'll add an explanation of the code later when I believe it can't be significantly shortened. \$\endgroup\$ – miles Sep 1 '17 at 6:29
2
\$\begingroup\$

JavaScript, 125 121 bytes

n=>(z=(a,b)=>[...Array(a)].map(b))(++n**n,(_,a)=>z[F=z(n,_=>a%(a/=n,n)|0).sort().join`+`]=b+=eval(F)==n-1&!z[F],b=0)|b||1

Try it online!

Warning: time and space complexity is exponential. Works very slow for large numbers.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Python 2, 89 bytes

-9 bytes by Mr.Xcoder -1 byte by notjagan

lambda n:len(p(n))
p=lambda n,I=1:{(n,)}|{y+(x,)for x in range(I,n/2+1)for y in p(n-x,x)}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ 90 bytes \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 15:56
  • \$\begingroup\$ @Mr.Xcoder Don't even know, why I didn't use lambda D: \$\endgroup\$ – Dead Possum Aug 31 '17 at 15:57
  • \$\begingroup\$ Hehe, ¯\_(ใƒ„)_/¯ - BTW, if you wanted to keep it a full function, you wouldn't need the variable, 94 bytes \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 15:58
  • \$\begingroup\$ @Mr.Xcoder Yeah.. I'm feeling rusty after some time being away from codegolf :c \$\endgroup\$ – Dead Possum Aug 31 '17 at 16:00
  • \$\begingroup\$ -1 byte. \$\endgroup\$ – notjagan Aug 31 '17 at 17:06
1
\$\begingroup\$

Jelly, 13 bytes

Jร†sรฆ.:L;
1ร‡ยกแธข

Try it online!

Takes 5 seconds to solve n = 1000 on TIO.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Java 8 (229 bytes)

import java.util.function.*;class A{static int j=0;static BiConsumer<Integer,Integer>f=(n,m)->{if(n==0)j++;else for(int i=Math.min(m,n);i>=1;i--)A.f.accept(n-i,i);};static Function<Integer,Integer>g=n->{f.accept(n,n);return j;};}

Ungolfed:

import java.util.function.*;

class A {
    static int j = 0;
    static BiConsumer<Integer, Integer> f = (n, m) -> {
        if (n == 0)
            j++;
        else
            for (int i = Math.min(m, n); i >= 1; i--)
                A.f.accept(n - i, i);
    };
    static Function<Integer, Integer> g = n -> {
        f.accept(n, n);
        return j;
    };
}
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Jelly, 3 bytes

The ล’แน— atom has recently been added, and it means "Integer partitions".

ล’แน—L

Try it online!

ล’แน—L   - Full program.

ล’แน—    - Integer partitions.
  L   - Length.
      - Output implicitly.
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Pyt, 2 bytes

โ†แตฑ

Explanation:

โ†          Get input
 แตฑ         Number of partitions
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

JavaScript ES7, 69 Bytes

n=>(f=(i,s)=>i?[for(c of Array(1+n))f(i-1,s,s-=i)]:c+=!s)(n,n,c=0)&&c

JavaScript ES6, 71 Bytes

n=>(f=(i,s)=>i?[...Array(1+n)].map(_=>f(i-1,s,s-=i)):c+=!s)(n,n,c=0)&&c

Time complexity O(n^n), so be careful (an obvious delay appears on my computer for F(6))

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy