Partitions

May 11, 2012

The only tricky part is eliminating duplicates. Our solution is not to add the duplicates in the first place by defining a function set-cons that is like cons but returns the original list unchanged if the item being consed onto the list is already present in the list:

(define (set-cons x xs)
  (if (member x xs) xs
    (cons x xs)))

With that, it’s easy. Two nested loops do the work; x loops over the integers from 1 to n, and yss loops over the smaller partitions, calling parts recursively:

(define (parts n)
  (if (zero? n) (list (list))
    (let ((xs (list)))
      (do ((x 1 (+ x 1))) ((= x n) (cons (list n) xs))
        (do ((yss (parts (- n x)) (cdr yss))) ((null? yss))
          (set! xs (set-cons (sort < (cons x (car yss))) xs)))))))

We sort the lists so that duplicate lists in different orders can be identified and eliminated from the output. You may prefer this version of the function that eliminates the assignment:

(define (parts n)
  (if (zero? n) (list (list))
    (let x-loop ((x 1) (xs (list)))
      (if (= x n) (cons (list n) xs)
        (let y-loop ((yss (parts (- n x))) (xs xs))
          (if (null? yss) (x-loop (+ x 1) xs)
            (y-loop (cdr yss)
                    (set-cons (sort < (cons x (car yss)))
                              xs))))))))

Both versions of the function give the same output:

> (parts 0)
(())
> (parts 1)
((1))
> (parts 2)
((2) (1 1))
> (parts 3)
((3) (1 1 1) (1 2))
> (parts 4)
((4) (2 2) (1 1 2) (1 1 1 1) (1 3))
> (parts 5)
((5) (2 3) (1 1 3) (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 4))
> (parts 6)
((6) (3 3) (2 2 2) (2 4) (1 1 4) (1 1 2 2) (1 1 1 1 2)
  ((1 1 1 1 1 1) (1 1 1 3) (1 2 3) (1 5))

You can run the program at http://programmingpraxis.codepad.org/TaCSCQAW.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
12 Comments »

12 Responses to “Partitions”

  1. uberlazy said
    May 11, 2012 at 10:18 AM

    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
    May 11, 2012 at 10:20 AM

    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. Programming Praxis – Partitions « Bonsai Code said
    May 11, 2012 at 4:50 PM

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

  4. Remco Niemeijer said
    May 11, 2012 at 4:51 PM

    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
    May 11, 2012 at 6:27 PM

    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
    May 11, 2012 at 10:56 PM

    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. Remco Niemeijer said
    May 11, 2012 at 11:26 PM

    @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
    May 12, 2012 at 2:05 AM

    @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
    May 12, 2012 at 5:37 AM

    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
    May 13, 2012 at 3:45 AM

    Solution in Go:


    package main
    import "fmt"
    import "sort"
    type EMPTY struct {}
    var PRESENT EMPTY = EMPTY{}
    func partition(val int) []string {
    set := make(map[string]EMPTY)
    for i := 1; i<=val;i++ {
    for _,result := range worker([]int{i},val-i) {
    set[fmt.Sprintf("%v",result)]=PRESENT
    }
    }
    out := make([]string,len(set))
    pos :=0
    for key := range set {
    out[pos] = key
    pos++
    }
    sort.Strings(out)
    return out
    }
    func worker(already []int, val int) [][]int {
    if val == 0 {
    sort.Ints(already)
    return [][]int{already}
    }
    out := [][]int {}
    for i := 1;i<=val;i++ {
    out = append(out,worker(append(already,i),val-i)…)
    }
    return out
    }
    func main() {
    for i := 0;i<10;i++ {
    result := partition(i)
    fmt.Printf("%d (%d): %v\n",i,len(result),result)
    }
    }

    view raw

    partition.go

    hosted with ❤ by GitHub

    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. Benjamin Samson said
    May 13, 2012 at 11:21 AM

    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
    August 16, 2012 at 11:31 PM

    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 comment