14
\$\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\$

11 Answers 11

4
\$\begingroup\$

Mathematica, 11 bytes

PartitionsQ

Test case

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
\$\endgroup\$
3
\$\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\$
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\$
  • \$\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 '16 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\$
  • \$\begingroup\$ make it n>0, you save a byte and go faster (i believe you recurse on negative numbers) :P \$\endgroup\$ – st0le Feb 12 '16 at 23:58
  • \$\begingroup\$ Also, Memoizing this kind of speeds it up \$\endgroup\$ – st0le Feb 13 '16 at 0:00
  • \$\begingroup\$ Cant you change your if statement to: return sum(...)if n else 1 \$\endgroup\$ – andlrc Feb 13 '16 at 0:07
  • \$\begingroup\$ @randomra Of course, of course... \$\endgroup\$ – Bob Feb 15 '16 at 17:28
1
\$\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\$
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\$
  • \$\begingroup\$ n%k|q<-k-1=n%q+(n-k)%q shaves a byte off of line 3. \$\endgroup\$ – Izaak Weiss Aug 28 '18 at 17:40
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\$

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\$
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\$
0
\$\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\$

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.