Subset Sums

November 9, 2010

We have previously solved Part 1 and Part 2 of the Greplin Programming Challenge. In today’s exercise we will solve the third and final part:

Find all the subsets of a set of non-negative integers where the largest number is the sum of the remaining numbers, and return a count of the number of them. For instance, for the set { 1, 2, 3, 4, 6 } the subsets are 1+2=3, 1+3=4, 2+4=6, and 1+2+3=6, so the result is 4 subsets. Apply your program to the set { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99 }.

Your task is to write a program to solve the challenge. In addition to solving the challenge, you might like to apply your solution to the set of prime numbers less than 210. 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

7 Responses to “Subset Sums”

  1. [...] Praxis – Subset Sums By Remco Niemeijer In today’s Programming Praxis exercise, we have to solve the third part of the Greplin challenge, which is to [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/09/programming-praxis-subset-sums/ for a version with comments):

    import Data.List
    
    greplin3 :: [Integer] -> Int
    greplin3 = length . filter (\s -> sum (init s) == last s) .
               tail . subsequences
    
    main :: IO ()
    main = print $ greplin3 [ 3, 4, 9,14,15,19,28,37,47,50,54
                            ,56,59,61,70,73,78,81,92,95,97,99]
    
  3. turuthok said

    For the 2^10:

    n = 2**10
    f = [1] * n
    f[0], f[1] = 0, 0
    p = []
    for i in xrange(2, n):
      if f[i]:
        for j in xrange(i+i, n, i): f[j] = False
        p.append(i)
    
    m = {}
    
    def go(idx, sum):
      if sum >= n: return 0
      if idx >= len(p): return f[sum]
      if (idx, sum) in m: return m[(idx, sum)];
    
      r = go(idx+1, sum) + go(idx+1, sum+p[idx])
      m[(idx, sum)] = r
      return r
    
    print go(0, 0) - len(p)
    

    ~/praxis$ time python greplin3.py
    44586565247

    real 0m0.592s
    user 0m0.456s
    sys 0m0.132s

  4. turuthok said

    Should’ve read the HOWTO post source code first before posting … sorry, and I should’ve changed f[j] = False to f[j] = 1 even though it doesn’t seem to affect the result.

  5. Christopher Oliver said

    I am confused that brute force should take as long as you claim. The following code brute-force searches the powerset, but runs in under four seconds (not minutes) on a
    cheap (AMD M520) laptop with stklos. I suspect that since your first algorithm computes
    and stores the entire powerset in order to then filter it, you are hitting the swap hard.

    (define subsets-problem-data
    ‘(3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99))

    (define (for-each-in-powerset fn set)
    (let recur ((arg-so-far ‘()) (set set))
    (if (null? set)
    (fn arg-so-far)
    (begin
    (recur arg-so-far (cdr set))
    (recur (cons (car set) arg-so-far) (cdr set))))))

    (define (problem-3)
    (let ((total 0))
    (for-each-in-powerset
    (lambda (set)
    (if (and (pair? set)
    (pair? (cdr set))
    (= (car set) (apply + (cdr set))))
    (set! total (+ total 1))))
    subsets-problem-data)
    total))

  6. Khanh Nguyen said
    let power_set (list:int list) =     
        let rec helper l result = 
            match l with
            | [] -> result
            | x::xs -> 
                let ll = List.map (fun s -> x::s) result
                helper xs (List.append result ll)        
        helper list [[]]
    
    let subset_sums (list:int list) = 
        power_set list 
        |> List.tail //the first set is the empty set
        |> List.filter (fun x -> List.head x = (List.tail x |> List.sum)) 
        |> List.length
    
    subset_sums [3;4;9;14;15;19;28;37;47;50;54;56;59;61;70;73;78;81;92;95;97;99]
    

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 612 other followers

%d bloggers like this: