Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

Mathematica, 11 bytes

PartitionsQ

Test case

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
share|improve this answer

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.

share|improve this answer
    
Brilliant! I was looking for a replacement for subsequences (+ import) in my answer myself, but didn't succeed so far. – nimi Feb 13 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.)

share|improve this answer

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).
share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
make it n>0, you save a byte and go faster (i believe you recurse on negative numbers) :P – st0le Feb 12 at 23:58
    
Also, Memoizing this kind of speeds it up – st0le Feb 13 at 0:00
    
Cant you change your if statement to: return sum(...)if n else 1 – andlrc Feb 13 at 0:07
    
@dev-null Sure, thanks! – Bob Feb 13 at 10:03
    
@randomra Of course, of course... – Bob Feb 15 at 17:28

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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