Loading ...
Sorry, an error occurred while loading the content.

Uploaded file: "05-02-2004 JeffGrigg SubsetSum in C#.zip"

Expand Messages
  • Jeff Grigg
    This is a brute force solution to the subset sum problem in C#, with Order(2^N * N) performance. I wrote this in response to the OT - How could I match
    Message 1 of 1 , May 2, 2004
    • 0 Attachment
      This is a brute force solution to the "subset sum" problem in C#,
      with Order(2^N * N) performance.

      I wrote this in response to the "OT - How could I match combinations
      of bank transactions?" thread in news:comp.software.extreme-
      programming started on April 29th.

      The "subset sum" problem is interesting because it can be
      generalized to the useful household problem of, "I just got the
      current bank balance of my checking account from the ATM. How can I
      figure out what transactions (deposits and checks) have cleared?"

      It's a "NP complete" problem. Solving it in less than Order(2^N)
      time will be a bit of a trick. ;->

      This solution is slow, inefficient and not very scalable. But in
      good XP tradition, I hope to build on it (and post new solutions),
      with ideas I described in the news thread.

      Beyond the current search algorithm being outlandishly slow (which
      is intentional), I think I'm "off in the weeds" in terms of
      asserting that the solution sets I get match my expectations. I
      suppose that I should just assert the expected solutions in exactly
      the same order that the current implementation produces them. But I
      fear that this won't help me when I change the implementation (which
      I plan to do), and that it will be very unhelpful when I run both
      old and new implementations against each other, for timing tests,
      and for additional validation.
      - jeff
    Your message has been successfully submitted and would be delivered to recipients shortly.