Strict partitions of a positive integer

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.

Pyth, 7 bytes

l{I#./Q

• 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).

Mathematica, 11 bytes

PartitionsQ


Test case

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


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.

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

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.)

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.

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.

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

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.

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).

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

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


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.

05AB1E, 8 bytes

ÅœʒDÙQ}g


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