17
\$\begingroup\$

OEIS A000009 counts the number of strict partitions of the integers. A strict partition of a nonnegative integer n is a set of positive integers (so no repetition is allowed, and order does not matter) that sum to n.

For example, 5 has three strict partitions: 5, 4,1, and 3,2.

10 has ten partitions:

10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1

Challenge

Given a nonnegative integer n<1000, output the number of strict partitions it has.

Test cases:

0 -> 1

42 -> 1426

Here is a list of the strict partition numbers from 0 to 55, from OEIS:

[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]

This is , so the shortest solution in bytes wins.

\$\endgroup\$

12 Answers 12

4
\$\begingroup\$

Pyth, 7 bytes

l{I#./Q

Try it online. Test suite.

  • Take the input (Q).
  • Find its partitions (./).
  • Filter it (#) on uniquify ({) not changing (I) the partition. This removes partitions with duplicates.
  • Find the result's length (l).
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 11 bytes

PartitionsQ

Test case

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
\$\endgroup\$
4
\$\begingroup\$

Python 2, 49 bytes

f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0

The recursion branches at every potential summand k from 1 to n to decide whether it should be included. Each included summand is subtracted from the desired sum n, and at the end, if n=0 remains, that path is counted.

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

Haskell, 39 bytes

f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]

The function (:[0]) converts a number k to the list [k,0]. So,

mapM(:[0])[1..n]

computes the Cartesian product of [1,0],[2,0],...,[n,0], which gives all subsets of [1..n] with 0's standing for omitted elements. The strict partitions of n correspond to such lists with sum n. Such elements are counted by a list comprehension, which is shorter than length.filter.

\$\endgroup\$
1
  • \$\begingroup\$ Brilliant! I was looking for a replacement for subsequences (+ import) in my answer myself, but didn't succeed so far. \$\endgroup\$
    – nimi
    Feb 13, 2016 at 2:52
2
\$\begingroup\$

ES6, 64 bytes

f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)

Works by recursive trial subtraction. k is the number that was last subtracted, and the next number to be subtracted must be larger (but not so large that an even larger number cannot be subtracted). 1 is added because you can always subtract n itself. (Also since this is recursive I have to take care that all of my variables are local.)

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

Python, 68 bytes

p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1

Just call the anonymous function passing the nonnegative integer n as argument... and wait the end of the universe.

\$\endgroup\$
4
  • \$\begingroup\$ make it n>0, you save a byte and go faster (i believe you recurse on negative numbers) :P \$\endgroup\$
    – st0le
    Feb 12, 2016 at 23:58
  • \$\begingroup\$ Also, Memoizing this kind of speeds it up \$\endgroup\$
    – st0le
    Feb 13, 2016 at 0:00
  • \$\begingroup\$ Cant you change your if statement to: return sum(...)if n else 1 \$\endgroup\$ Feb 13, 2016 at 0:07
  • \$\begingroup\$ @randomra Of course, of course... \$\endgroup\$
    – Bob
    Feb 15, 2016 at 17:28
2
\$\begingroup\$

05AB1E, 5 bytes

LæOQO

Try it online!

Note: this is extremely slow and will timeout for inputs greater than about 20.

Explanation:

L         # range 1..input
 æ        # list of subsets
  O       # sum each subset
   Q      # equal? (1 for each sum that equals the input, 0 otherwise)
    O     # sum the booleans
\$\endgroup\$
1
\$\begingroup\$

Haskell, 58 bytes

import Data.List
h x=sum[1|i<-subsequences[1..x],sum i==x]

Usage example: map h [0..10] -> [1,1,1,2,2,3,4,5,6,8,10].

It's a simple brute-force approach. Check the sums of all subsequences of 1..x. This works for x == 0, too, because all subsequences of [1..0] are [[]] and the sum of [] is 0.

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

Haskell, 43 bytes

0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n

The binary function n%k counts the number of strict partitions of n into parts with a maximum part k, so the desired function is f n=n%n. Each value k can be included, which decreases n by k, or excluded, and either way the new maximum k is one lower, giving the recursion n%k=n%(k-1)+(n-k)%(k-1).

\$\endgroup\$
1
  • \$\begingroup\$ n%k|q<-k-1=n%q+(n-k)%q shaves a byte off of line 3. \$\endgroup\$ Aug 28, 2018 at 17:40
1
\$\begingroup\$

Vyxal l, 24 bitsv2, 3 bytes

Ṅ'Þu

Try it Online!

Vyxal forever

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

Julia, 53 bytes

n->endof(collect(filter(p->p==∪(p),partitions(n))))

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

We get the integer partitions using partitions, filter to only those with distinct summands, collect into an array, and find the last index (i.e. the length) using endof.

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

05AB1E, 8 bytes

ÅœʒDÙQ}g

Try it online or verify all test cases.

Explanation:

Ŝ          # Get all integer partitions of the (implicit) input
            #  i.e. 5 → [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
  ʒ   }     # Filter by:
   D        #  Duplicate the current partition
    Ù       #  Uniquify (removing any duplicated values from) this copied partition
            #   i.e. [1,1,1,1,1] → [1]
            #   i.e. [1,4] → [1,4]
     Q      #  Check if it's still the same
            #   i.e. [1,1,1,1,1] and [1] → 0 (falsey)
            #   i.e. [1,4] and [1,4] → 1 (truthy)
       g    # Then take the length of the filtered list (and implicitly output it)
            #  i.e. [[1,4],[2,5],[5]] → 3
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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