Partitions

May 11, 2012

The partitions of an integer is the set of all sets of integers that sum to the given integer. For instance, the partitions of 4 is the set of sets ((1 1 1 1) (1 1 2) (1 3) (2 2) (4)). We computed the number of partitions of an integer in a previous exercise. In today’s exercise, we will make a list of the partitions.

The process is recursive. There is a single partition of 0, the empty set (). There is a single partition of 1, the set (1). There are two partitions of 2, the sets (1 1) and (2). There are three partitions of 3, the sets (1 1 1), (1 2) and (3). There are five partitions of 4, the sets (1 1 1 1), (1 1 2), (1 3), (2 2), and (4). There are seven partitions of 5, the sets (1 1 1 1 1), (1 1 1 2), (1 2 2), (1 1 3), (1 4), (2 3) and (5). And so on. In each case, the next-larger set of partitions is determined by adding each integer x less than or equal to the desired integer n to all the sets formed by the partition of nx, eliminating any duplicates.

Your task is to write a function that generates the set of all partitions of a given integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

12 Responses to “Partitions”

  1. uberlazy said

    A recursive solution in Clojure. The result is in the reverse order than what is shown in the problem description, because it’s slightly more convenient to check the subtrahend against 0 than against the original minuend, which would have to be remembered somehow. It shouldn’t matter as the problem calls for a set.

    (defn- parts-helper [num subtr acc]
      (cond
       (= num 0) [acc]
       (or (= subtr 0) (< num 0)) []
       :else (concat
    	  (intpart (- num subtr) subtr (conj acc subtr))
    	  (intpart num (dec subtr) acc))))
    
    (defn parts [num]
      (parts-helper num num []))
    
  2. uberlazy said

    A copy-paste blunder. The code should read:

    [sourceoode="css"]
    (defn- parts-helper [num subtr acc]
    (cond
    (= num 0) [acc]
    (or (= subtr 0) (< num 0)) []
    :else (concat
    (parts-helper (- num subtr) subtr (conj acc subtr))
    (parts-helper num (dec subtr) acc))))

    (defn parts [num]
    (parts-helper num num []))

    [/sourcecode]

  3. [...] today’s Programming Praxis exercise, our goal is to write a function that gives all unique sums that [...]

  4. My Haskell solution (see http://bonsaicode.wordpress.com/2012/05/11/programming-praxis-partitions/ for a version with comments):

    part :: Int -> [[Int]]
    part 0 = [[]]
    part n = [x:y | x <- [1..n], y <- part (n-x), [x] >= take 1 y]
    
  5. Mike said

    Python 2.7

    def partitionsOf(n):
        if n == 0:
            return {()}
        else:
            return {tuple(sorted(t + (x,))) for x in range(1, n + 1) for t in partitionsOf(n - x)}
    
  6. Graham said

    It strikes me that many recursive solutions will probably be inefficient
    (except for Haskell ones, perhaps), since solutions to subproblems are
    recomputed every time they’re needed, similar to SICP’s discussion of Fibonacci
    number generation.
    First up, a memoizing version (based on a Python version that Programming
    Praxis pointed me to on StackOverflow) that stores previous answers.
    Next are zs1 and zs2, Python versions of two
    algorithms found in Fast Algorithms for Generating Integer
    Paritions
    by Zoghbi and Stojmenovic (1998). They’re iterative and more
    efficient than the first solution, if uglier. I’ve made them generators instead
    of lists, but that’s not really relevant to the algorithms.

    from functools import update_wrapper
    
    def memoize(func):
        func.memo = {}
        def wrapper(arg):
            try:
                return func.memo[arg]
            except KeyError:
                func.memo[arg] = result = func(arg)
                return result
        return update_wrapper(wrapper, func)
    
    @memoize
    def partitions(n):
        parts = set([tuple([n])])
        for k in xrange(1, n):
            for p in partitions(n - k):
                parts.add(tuple(sorted([k] + p)))
        return map(list, parts)
    
    def zs1(n):
        x = [1] * n
        x[0], m, h = n, 0, 0
        yield [x[0]]
        while x[0] != 1:
            if x[h] == 2:
                m, x[h] = m + 1, 1
                h -= 1
            else:
                r = x[h] - 1
                t, x[h] = m - h + 1, r
                while t >= r:
                    h += 1
                    x[h], t = r, t - r
                if t == 0:
                    m = h
                else:
                    m = h + 1
                    if t > 1:
                        h += 1
                        x[h] = t
            yield x[:m + 1]
    
    def zs2(n):
        x = [1] * (n + 1)
        yield x[1:]
        x[:2] = -1, 2
        h, m = 1, n - 1
        yield x[1: m + 1]
        while x[1] != n:
            if m - h > 1:
                h += 1
                x[h], m = 2, m - 1
            else:
                j = m - 2
                while x[j] == x[m - 1]:
                    x[j] = 1
                    j -= 1
                h = j + 1
                x[h], r, x[m] = x[m - 1] + 1, x[m] + x[m - 1] * (m - h - 1), 1
                if m - h > 1:
                    x[m - 1] = 1
                m = h + r - 1
            yield x[1: m + 1]
    
    if __name__ == "__main__":
        print sorted(partitions(6))
        print list(zs1(6))
        print list(zs2(6))
    
  7. @Graham: The Haskell version isn’t memoized. Memoizing the function is pretty simple and doesn’t add too much to the program length though:

    memopart = (memo !!) where
        memo = [[]] : [[x:y | x <- [1..n], y <- memo !! (n-x), [x] >= take 1 y] | n <- [1..]]
    
  8. Graham said

    @Remco: thanks for that. I thought there might have been some sort of wizardry hidden in the lazy evaluation or something, but I appreciate the enlightenment.

  9. Jussi Piitulainen said

    Find partitions where the least term is equal to or greater than another parameter. This way duplicates are not generated. All partitions are found by setting the other parameter to 1.

    (define integer-partitions
      (case-lambda
       ((n) (integer-partitions n 1))
       ((n m) (if (= n m) (list (list m))
                  (if (< n m) (list)
                      (append (map (lambda (p) (cons m p))
                                   (integer-partitions (- n m) m))
                              (integer-partitions n (+ m 1))))))))
    
    > (integer-partitions 4)
    ((1 1 1 1) (1 1 2) (1 3) (2 2) (4))
    
  10. Jon Bodner said

    Solution in Go:

    This shows off some of the ugly things in Go: no built-in set type (use a map with an empty value), no easy way to get all the keys for a map (have to manually copy to a slice), no way to directly use a slice as the key for a map or define a custom hashcode or equals on a type (convert the slice to a string, and use that as the key in the map).

  11. My solution is not as neat and elegant as yours but all the same, I’m proud that I was able to do it.
    Here’s my solution in Python:

    def partitions(n):
    p = []
    # n is not 0
    if n:
    # from 1 to n
    for i in range(1, n+1):
    a = partitions(n-i)

    if len(a) == 0:
    p.append(i)
    else:
    for j in a:
    if isinstance(j, int):
    b = [j, i]
    b.sort()
    if b not in p:
    p.append(b)
    else:
    j.append(i)
    j.sort()
    if j not in p:
    p.append(j)
    return p

    # n is 0
    else:
    return []

  12. Jan Van lent said

    Another Python version [1].
    It uses a sparse representation for the partitions, e.g., 4 = 4 x 1 = 2 x 1 + 2 = 1 x 1 + 3 = 2 x 2 = 1 x 4 instead of 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2 + 2 = 4.

    [1] http://code.activestate.com/recipes/221132/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 622 other followers

%d bloggers like this: