CoCreate Modeling code examples: Solving the subset sum problem

topic end
<!--
   * Set TOPICTITLE = <nop>CoCreate Modeling code examples: Solving the subset sum problem
-->

<style type="text/css">
pre { background-color:#FFEECC; }
</style>

---++ <nop>CoCreate Modeling: Solving the subset sum problem

In a [[http://ww3.cad.de/foren/ubb/Forum92/HTML/000286.shtml][recent discussion]] in the 
German CoCreate user forum, a customer was looking for ways to solve a variation
of the [[http://en.wikipedia.org/wiki/Subset_sum_problem][subset sum problem]]
(which is a special case of the [[http://mathworld.wolfram.com/KnapsackProblem.html][knapsack problem]]).
This was needed to find the right combination of tool parts to manufacture a
screw. Those tool parts are available in a wide variety of diameters, and the task
at hand is to find a set of these tools which, when combined, can be used to
manufacture a screw of a given size.

Abstracting from the manufacturing problem, the problem can be stated like this:
Given =n= items of lengths <tt>l<sub>1</sub></tt>, <tt>l<sub>2</sub></tt>...
<tt>l<sub>n</sub></tt> and a total length of =t=, find all subsets of items
which add up to =t=.

Even though the description sounds fairly simple, the problem is
surprisingly tough. In fact, it is [[http://en.wikipedia.org/wiki/NP-Complete][NP-complete]],
which is computer science gobbledigook for "d*mn tough, man!".
In practice, it means that for small values of =n=, it's easy to find
an algorithm which tests all permutations and lists all subsets in
a reasonable amount of time. However, as the size of the array of item lengths
grows, the computation time may grow exponentially, and chances are you'll
never see the day when it ends
(cf. [[http://en.wikipedia.org/wiki/Minor_characters_from_The_Hitchhiker's_Guide_to_the_Galaxy#Deep_Thought][Deep Thought]]).

The following simple [[http://en.wikipedia.org/wiki/Backtracking][backtracking]]
algorithm is of that nature: It performs reasonably well for small arrays, but will 
quickly wear your patience for larger arrays. To see how the algorithm behaves,
I created a version of the code which only counts the number of found solutions;
then I ran it in [[http://clisp.cons.org/][CLISP]], compiled and interpreted:


| *Array size* | *Run time<br>(compiled)* | *Run time<br>(interpreted)* |
|  10          |  0.002s    |  0.02s  |
|  15          |  0.05s     |  0.35s  |
|  20          |  0.7s      |  6s    |
|  25          |  18s       |  210s  |
|  27          |  80s       |  780s  |
|  29          |  270s      |       |
|  30          |  570s      |       |

Take those results with arbitrary amounts of salt; the code (see below)
initializes the test array with random numbers and will therefore always
vary a little. But the results are reliable enough to show that you don't
really want to use this algorithm for large arrays...

<pre>
<font color="#6a5acd">(</font><font color="#804040"><b>let</b></font> <font color="#6a5acd">((</font>solutions <font color="#ff00ff">0</font><font color="#6a5acd">)</font>
      flags
      numbers<font color="#6a5acd">)</font>

  <font color="#6a5acd">(</font><font color="#804040"><b>defun</b></font> found-solution<font color="#6a5acd">()</font>
    <font color="#ff00ff">&quot;Called whenever the algorithm has found a solution&quot;</font>

    <font color="#6a5acd">(</font><font color="#804040"><b>let</b></font> <font color="#6a5acd">((</font>total <font color="#ff00ff">0</font><font color="#6a5acd">))</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>format</b></font> <font color="#804040"><b>t</b></font> <font color="#ff00ff">&quot;  &quot;</font><font color="#6a5acd">)</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>dotimes</b></font> <font color="#6a5acd">(</font>i <font color="#6a5acd">(</font><font color="#804040"><b>length</b></font> numbers<font color="#6a5acd">))</font>
        <font color="#6a5acd">(</font><font color="#804040"><b>when</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> flags i<font color="#6a5acd">)</font>
          <font color="#6a5acd">(</font><font color="#804040"><b>incf</b></font> total <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> numbers i<font color="#6a5acd">))</font>
          <font color="#6a5acd">(</font><font color="#804040"><b>format</b></font> <font color="#804040"><b>t</b></font> <font color="#ff00ff">&quot;~A &quot;</font> <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> numbers i<font color="#6a5acd">)))</font>
        <font color="#6a5acd">)</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>format</b></font> <font color="#804040"><b>t</b></font> <font color="#ff00ff">&quot; =&gt; ~A~%&quot;</font> total<font color="#6a5acd">)</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>incf</b></font> solutions<font color="#6a5acd">)))</font>

  <font color="#6a5acd">(</font><font color="#804040"><b>defun</b></font> find-solutions<font color="#6a5acd">(</font>k target-sum callback<font color="#6a5acd">)</font>
    <font color="#ff00ff">&quot;Core backtracking algorithm&quot;</font>

    <font color="#6a5acd">(</font><font color="#804040"><b>when</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>zerop</b></font> target-sum<font color="#6a5acd">)</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>funcall</b></font> callback<font color="#6a5acd">)</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>return-from</b></font> find-solutions<font color="#6a5acd">))</font>

    <font color="#6a5acd">(</font><font color="#804040"><b>unless</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>=</b></font> k <font color="#6a5acd">(</font><font color="#804040"><b>length</b></font> numbers<font color="#6a5acd">))</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>let</b></font> <font color="#6a5acd">((</font>nk <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> numbers k<font color="#6a5acd">)))</font>
        <font color="#6a5acd">(</font><font color="#804040"><b>when</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>&gt;=</b></font> target-sum nk<font color="#6a5acd">)</font>
          <font color="#0000ff">;; try subtracting numbers[k] from target-sum</font>
          <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> flags k<font color="#6a5acd">)</font> <font color="#804040"><b>t</b></font><font color="#6a5acd">)</font>
          <font color="#6a5acd">(</font>find-solutions <font color="#6a5acd">(</font><font color="#804040"><b>+</b></font> <font color="#ff00ff">1</font> k<font color="#6a5acd">)</font> <font color="#6a5acd">(</font><font color="#804040"><b>-</b></font> target-sum nk<font color="#6a5acd">)</font> callback<font color="#6a5acd">)</font>
          <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> flags k<font color="#6a5acd">)</font> <font color="#804040"><b>nil</b></font><font color="#6a5acd">)))</font>

      <font color="#0000ff">;; recurse without subtracting first</font>
      <font color="#6a5acd">(</font>find-solutions <font color="#6a5acd">(</font><font color="#804040"><b>+</b></font> <font color="#ff00ff">1</font> k<font color="#6a5acd">)</font> target-sum callback<font color="#6a5acd">)))</font>

  <font color="#6a5acd">(</font><font color="#804040"><b>defun</b></font> find-subset-sum<font color="#6a5acd">(</font>target-sum<font color="#6a5acd">)</font>
    <font color="#ff00ff">&quot;Set up and run backtracking algorithm based on 'numbers' array&quot;</font>

    <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> flags <font color="#6a5acd">(</font><font color="#804040"><b>make-array</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>list</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>length</b></font> numbers<font color="#6a5acd">))))</font>
    <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> solutions <font color="#ff00ff">0</font><font color="#6a5acd">)</font>
    <font color="#6a5acd">(</font>find-solutions <font color="#ff00ff">0</font> target-sum <font color="#2e8b57"><b>#'found-solution</b></font><font color="#6a5acd">)</font>
    <font color="#6a5acd">(</font><font color="#804040"><b>format</b></font> <font color="#804040"><b>t</b></font> <font color="#ff00ff">&quot;Found ~A different solutions.~%&quot;</font> solutions<font color="#6a5acd">))</font>


  <font color="#6a5acd">(</font><font color="#804040"><b>defun</b></font> subset-sum-test<font color="#6a5acd">(</font>size<font color="#6a5acd">)</font>
    <font color="#ff00ff">&quot;Test subset sum algorithm using random numbers&quot;</font>

    <font color="#6a5acd">(</font><font color="#804040"><b>let*</b></font> <font color="#6a5acd">((</font>total <font color="#ff00ff">0</font><font color="#6a5acd">)</font> target-sum<font color="#6a5acd">)</font>
      <font color="#0000ff">;; init numbers array with random values up to 1000</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> numbers <font color="#6a5acd">(</font><font color="#804040"><b>make-array</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>list</b></font> size<font color="#6a5acd">)))</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>dotimes</b></font> <font color="#6a5acd">(</font>i size<font color="#6a5acd">)</font>
        <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> numbers i<font color="#6a5acd">)</font> <font color="#6a5acd">(</font><font color="#804040"><b>random</b></font> <font color="#ff00ff">1000</font><font color="#6a5acd">))</font>
        <font color="#6a5acd">(</font><font color="#804040"><b>incf</b></font> total <font color="#6a5acd">(</font><font color="#804040"><b>aref</b></font> numbers i<font color="#6a5acd">)))</font>

      <font color="#6a5acd">(</font><font color="#804040"><b>setf</b></font> target-sum <font color="#6a5acd">(</font><font color="#804040"><b>floor</b></font> <font color="#6a5acd">(</font><font color="#804040"><b>/</b></font> total <font color="#ff00ff">2</font><font color="#6a5acd">)))</font> <font color="#0000ff">;; random target sum</font>
      <font color="#6a5acd">(</font><font color="#804040"><b>format</b></font> <font color="#804040"><b>t</b></font> <font color="#ff00ff">&quot;Now listing all subsets which sum up to ~A:~%&quot;</font> target-sum<font color="#6a5acd">)</font>

      <font color="#6a5acd">(</font>find-subset-sum target-sum<font color="#6a5acd">)))</font>

  <font color="#6a5acd">)</font>

</pre>

<!--
<pre>
(let ((solutions 0)
      flags 
      numbers)
  
  (defun found-solution()
    "Called whenever the algorithm has found a solution"
    
    (let ((total 0))
      (format t "  ")
      (dotimes (i (length numbers))
        (when (aref flags i)
          (incf total (aref numbers i))
          (format t "~A " (aref numbers i)))
        )
      (format t " => ~A~%" total)
      (incf solutions)))
  
  (defun find-solutions(k target-sum callback)
    "Core backtracking algorithm"
    
    (when (zerop target-sum)
      (funcall callback)
      (return-from find-solutions))
    
    (unless (= k (length numbers))
      (let ((nk (aref numbers k)))
        (when (>= target-sum nk)
          ;; try subtracting numbers[k] from target-sum
          (setf (aref flags k) t)
          (find-solutions (+ 1 k) (- target-sum nk) callback)
          (setf (aref flags k) nil)))
      
      ;; recurse without subtracting first
      (find-solutions (+ 1 k) target-sum callback)))
  
  (defun find-subset-sum(target-sum)
    "Set up and run backtracking algorithm based on 'numbers' array"
    
    (setf flags (make-array (list (length numbers))))
    (setf solutions 0)
    (find-solutions 0 target-sum #'found-solution)
    (format t "Found ~A different solutions.~%" solutions))
  
  
  (defun subset-sum-test(size)
    "Test subset sum algorithm using random numbers"
    
    (let* ((total 0) target-sum)
      ;; init numbers array with random values up to 1000
      (setf numbers (make-array (list size)))
      (dotimes (i size)
        (setf (aref numbers i) (random 1000))
        (incf total (aref numbers i)))

      (setf target-sum (floor (/ total 2))) ;; random target sum
      (format t "Now listing all subsets which sum up to ~A:~%" target-sum)
      
      (find-subset-sum target-sum)))
  
  )
</pre>
-->

The core backtracking algorithm is in =find-solutions=. It will recursively
exhaust all subsets. When it finds a subset which adds up to =target-sum=,
it will call the =callback= function - this function can either simply
increase a solution counter, report the current solution to the user, or
store it somewhere for later retrieval.

In the test example above, the callback function is =print-solution= which
increments a solution counter and prints the current solution.

To test the code, run =subset-sum-test=, providing an array size. This function
will create an array of =numbers= of that size and initialize it with random
values; it will also pick a random =target-sum=. In a real application,
you would replace =subset-sum-test= with a function which gets the array
data from somewhere (for example, from a tools database as in the customer's
case), and lets the user pick a =target-sum=.

-- Main.ClausBrod - 01 Mar 2006

The aforementioned customer would actually have preferred a solution in CoCreate
Drafting's macro language. However, this macro language isn't really
a full-blown programming language (even though it is perfectly adequate
for almost all customization purposes). For instance, its macros cannot return
values, the language doesn't have an array type, and the macro expansion stack
(i.e. the depth of the macro call tree) has a fixed limit - which pretty much
rules out non-trivial amounts of recursion.

While I was considering my options, I also fooled around with VBA,
which resulted in the code presented below. I'm not at all
proficient in VBA, so I'm sure the implementation is lacking, but
anyway - maybe someone out there finds it useful nonetheless ;)

<pre>
Dim solutions As Long
Dim flags() As Boolean
Dim numbers() As Long

Sub findSolutions(k As Long, targetSum As Long)
  If targetSum = 0 Then
    ' we found a solution
    solutions = solutions + 1
    Exit Sub
  End If
  
  If k <= UBound(numbers) Then
    If (targetSum >= numbers(k)) Then
      flags(k) = True
      ' try first by subtracting numbers[k] from targetSum
      Call findSolutions(k + 1, targetSum - numbers(k))
      flags(k) = False
    End If
    
    ' now try without subtracting
    Call findSolutions(k + 1, targetSum)
  End If
End Sub

Sub subsetsum()
  Dim targetSum As Long
  Dim i As Long
  
  Dim arraySize As Long
  arraySize = 25
  ReDim numbers(0 To arraySize - 1)
  ReDim flags(0 To arraySize - 1)
  
  ' initialize numbers array with random entries
  Randomize
  For i = 0 To arraySize - 1
    numbers(i) = Int(1000 * Rnd + 1)
    flags(i) = False
    targetSum = targetSum + numbers(i)
  Next
  targetSum = Int(targetSum / 2)
  
  solutions = 0
  Call findSolutions(0, targetSum)
  MsgBox "Found " + Str(solutions) + " solutions."
End Sub
</pre>

Let's see - we recurse one level for each entry in the array, so with a maximum
array size of 30 (the customer said he was considering a table of 20-30 values),
the recursion depth should never exceed 30. That's not a lot, in fact,
so would this still exceed the macro stack thresholds in <nop>CoCreate Drafting?

Oh, and by the way, the recursive function doesn't even try to return values,
so the lack of return values in the macro language isn't a real obstacle
in this case! I couldn't resist and just had to try to translate the algorithm
into <nop>CoCreate Drafting macro language:

<pre>
{ Description:  Subset sum algorithm }
{ Author:       Claus Brod  }
{ Language:     CoCreate Drafting macros }
{ (C) Copyright 2006 Claus Brod, all rights reserved }

DEFINE Found_solution
  LOCAL I
  LOCAL Solution
  LOCAL Total
  LOCAL Nk

  { display current solution }
  LET Subset_sum_solutions (Subset_sum_solutions+1)
  LET I 1
  LET Solution ''
  LET Total 0
  WHILE (I <= Subset_sum_arraysize)
    IF (READ_LTAB 'Flags' I 1)
      LET Nk (READ_LTAB 'Numbers' I 1)
      LET Total (Total + Nk)
      LET Solution (Solution + ' ' + STR(Nk))
    END_IF
    LET I (I+1)
  END_WHILE
  DISPLAY_NO_WAIT (Solution + ' sum up to ' + STR(Total))
END_DEFINE

DEFINE Find_solutions
  PARAMETER K
  PARAMETER Target_sum

  LOCAL Nk

  IF (Target_sum = 0)
    { we found a solution, display it }
    Found_solution
  ELSE_IF (K <= Subset_sum_arraysize)
    LET Nk (READ_LTAB 'Numbers' K 1)
    { The following optimization only works if we can assume a sorted array }
    IF ((Nk * (Subset_sum_arraysize-K+1)) >= Target_sum)
      IF (Target_sum >= Nk)
        { try first by subtracting Numbers[k] from Target }
        WRITE_LTAB 'Flags' K 1 1
        Find_solutions (K+1) (Target_sum-Nk)
        WRITE_LTAB 'Flags' K 1 0
      END_IF

      { now try without subtracting }
      Find_solutions (K+1) Target_sum
    END_IF
  END_IF
END_DEFINE

DEFINE Subset_sum
  PARAMETER Subset_sum_arraysize

  LOCAL Target
  LOCAL Random
  LOCAL I
  LOCAL Subset_sum_solutions
  LOCAL Start_time

  { Allocate Numbers and Flags arrays }
  CREATE_LTAB Subset_sum_arraysize 1 'Numbers'
  CREATE_LTAB Subset_sum_arraysize 1 'Flags'

  LET Target 0
  LET I 1
  WHILE (I <= Subset_sum_arraysize)
    LET Random (INT(1000 * RND + 1))
    LET Target (Target + Random)
    WRITE_LTAB 'Numbers' I 1 Random
    WRITE_LTAB 'Flags' I 1 0
    LET I (I+1)
  END_WHILE
  LET Target (INT (Target/2))

  DISPLAY ('Array size is ' + STR(Subset_sum_arraysize) + ', target sum is ' + STR(Target))

  { Sorting in reverse order speeds up the recursion }
  SORT_LTAB 'Numbers' REVERSE_SORT 1 CONFIRM

  LET Start_time (TIME)
  LET Subset_sum_solutions 0
  Find_solutions 1 Target
  DISPLAY ('Found ' + STR(Subset_sum_solutions) + ' solutions in ' + STR(TIME-Start_time) + ' seconds.')
END_DEFINE
</pre>

Because <nop>CoCreate Drafting's macro language doesn't have arrays, they have to be emulated
using _logical tables_, or _ltabs_. The solutions which are found are displayed
in <nop>CoCreate Drafting's prompt line, which is certainly not the most ideal place, but it's
sufficient to verify the algorithm is actually doing anything .-)

What you see above, is a tuned version of the macro code I came up with initially.
The "literal" translation from the original Lisp version took ages to 
complete even for small arrays; for instance, searching for solutions in an array
of 20 numbers took 95 seconds (using OSDD 2005). However, there are two
simple optimizations which can be applied to the algorithm.

First, the input array can be sorted in reverse order, i.e.
largest numbers first. This makes it more likely that we
can prune the recursion tree early. This optimization
itself improved runtimes by only 5% or so, but more importantly,
it paved the way for another optimization.

Since we know that the numbers in the array are
monotonically decreasing, we can now predict in many cases that
there is no chance of possibly reaching the target sum anyway, and
therefore abort the recursion early. Example for an array of size 20:
   * We are in the midst of the recursion, say, at recursion
     level 15. The array entry at index 15 contains the value 42.
   * Let us further assume that =Target_sum= has already been
     reduced to 500 earlier in the recursion, i.e. the remaining
     entries in the array somehow have to sum up to 500 to meet 
     the required subset sum.
   * Because the values in the array are monotonically
     decreasing, we know that the entries 15 through 20 have a
     value of 42 at most. Assuming that _all_ remaining entries are
     42, we get a maximum remaining sum of 42*6=252.
   * This means we can prune the recursion tree at this point
     because there's no way that this recursion line will ever
     find a solution.

This second optimization improved runtimes tremendously; with an array size of 20,
we're now down to 15 seconds (originally 95 seconds); however, it
still takes more than 3000 seconds to find all solutions in an array of size 30.

By the way, all performance measurements mentioned here were taken on the same
system, a laptop with a 1.7 GHz Celeron CPU.

In real life, the =Numbers= array will in fact contain floating-point
values rather than integers. The algorithm doesn't change, but
whenever you work with floating-point values, it's good to follow
a few basic guidelines like the ones outlined [[OsdmFaqLisp#RoundingErrors][here]].

In the case of the above macro code, instead of a comparison like
<tt>IF (Target = 0)</tt>, you'd probably want to write something
like =IF (ABS(Target) < Epsilon)= where =Epsilon= is a small value
chosen to meet a user-defined tolerance (for example 0.001).

-- Main.ClausBrod - 16 Mar 2006

This is taking me to places I didn't anticipate. 
[[http://www.codecomments.com/archive269-2004-7-238675.html][Over at codecomments.com]],
they are discussing solutions to the subset sum problem in Haskell,
Prolog and Caml, if anyone is interested. (I sure was, and even read
a tutorial on Haskell to help me understand what these guys are
talking about :) )

-- Main.ClausBrod - 01 Apr 2006

I started to learn some Ruby, so here's a na&iuml;ve implementation of
the algorithm in yet another language ;) (See also [[Blog.BlogOnSoftware20060416][this blog entry]].)

<pre>
<font color="#008080">$solutions</font> = <font color="#ff00ff">0</font>
<font color="#008080">$numbers</font> = []
<font color="#008080">$flags</font> = []

<font color="#a020f0">def </font><font color="#008080">find_solutions</font>(k, target_sum)
  <font color="#804040"><b>if</b></font> target_sum == <font color="#ff00ff">0</font>
    <font color="#0000ff"># found a solution!</font>
    (<font color="#ff00ff">0</font>..<font color="#008080">$numbers</font>.length).each { |<font color="#008080">i</font>| <font color="#804040"><b>if</b></font> (<font color="#008080">$flags</font>[i]) <font color="#804040"><b>then</b></font> print <font color="#008080">$numbers</font>[i], <font color="#6a5acd">&quot;</font><font color="#ff00ff"> </font><font color="#6a5acd">&quot;</font>; <font color="#804040"><b>end</b></font> }
    print <font color="#6a5acd">&quot;</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
    <font color="#008080">$solutions</font> = <font color="#008080">$solutions</font> + <font color="#ff00ff">1</font>
  <font color="#804040"><b>else</b></font>
    <font color="#804040"><b>if</b></font> k &lt; <font color="#008080">$numbers</font>.length
      <font color="#804040"><b>if</b></font> target_sum &gt;= <font color="#008080">$numbers</font>[k]
        <font color="#008080">$flags</font>[k] = <font color="#ff00ff">true</font>
        find_solutions k+<font color="#ff00ff">1</font>, target_sum-<font color="#008080">$numbers</font>[k]
        <font color="#008080">$flags</font>[k] = <font color="#ff00ff">false</font>
      <font color="#804040"><b>end</b></font>
      find_solutions k+<font color="#ff00ff">1</font>, target_sum
    <font color="#804040"><b>end</b></font>
  <font color="#804040"><b>end</b></font>
<font color="#a020f0">end</font>

<font color="#a020f0">def </font><font color="#008080">find_subset_sum</font>(target_sum)
  print <font color="#6a5acd">&quot;</font><font color="#6a5acd">\n</font><font color="#ff00ff">Now listing all subsets which sum up to </font><font color="#6a5acd">&quot;</font>, target_sum, <font color="#6a5acd">&quot;</font><font color="#ff00ff">:</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
  <font color="#008080">$solutions</font> = <font color="#ff00ff">0</font>
  (<font color="#ff00ff">0</font>..<font color="#008080">$numbers</font>.length()).each { |<font color="#008080">i</font>| <font color="#008080">$flags</font>[i] = <font color="#ff00ff">false</font> }
  find_solutions <font color="#ff00ff">0</font>, target_sum
  print <font color="#6a5acd">&quot;</font><font color="#ff00ff">Found </font><font color="#6a5acd">&quot;</font>, <font color="#008080">$solutions</font>, <font color="#6a5acd">&quot;</font><font color="#ff00ff"> different solutions.</font><font color="#6a5acd">\n</font><font color="#6a5acd">&quot;</font>
<font color="#a020f0">end</font>

<font color="#a020f0">def </font><font color="#008080">subset_sum_test</font>(size)
  total = <font color="#ff00ff">0</font>
  target_sum = <font color="#ff00ff">0</font>
  (<font color="#ff00ff">0</font>..size).each { |<font color="#008080">i</font>| <font color="#008080">$numbers</font>[i] = rand(<font color="#ff00ff">1000</font>); total += <font color="#008080">$numbers</font>[i]; print <font color="#008080">$numbers</font>[i], <font color="#6a5acd">&quot;</font><font color="#ff00ff"> </font><font color="#6a5acd">&quot;</font> }
  target_sum = total/<font color="#ff00ff">2</font>
  find_subset_sum target_sum
<font color="#a020f0">end</font>

subset_sum_test <font color="#ff00ff">25</font>
</pre>

-- Main.ClausBrod - 17 Apr 2006

#SubsetSumPython

The other day, I experimented with Python and thought I'd start with a quasi-verbatim
translation of the subset sum code. Here is the result. Apologies for the non-idiomatic
and na&iuml;ve implementation.

<pre>
<style type="text/css">
<!--
.String { color: #4a708b; }
.Statement { color: #b03060; font-weight: bold; }
.PreProc { color: #1874cd; }
.Constant { color: #ff8c00; }
.Special { color: #8a2be2; }
.Identifier { color: #458b74; }
-->
</style>
<span class="PreProc">import</span> random
<span class="PreProc">import</span> array
<span class="PreProc">import</span> sys

numbers = array.array(<span class="String">'i'</span>)
flags = array.array(<span class="String">'c'</span>)
solutions = <span class="Constant">0</span>

<span class="Statement">def</span> <span class="Identifier">find_solutions</span>(k, target_sum):
    <span class="Statement">global</span> solutions

    <span class="Statement">if</span> target_sum == <span class="Constant">0</span>:
        <span class="Identifier">print</span> <span class="String">&quot;  Solution:&quot;</span>,
        <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, <span class="Identifier">len</span>(numbers)):
            <span class="Statement">if</span> flags[i] != <span class="Constant">0</span>:
                <span class="Identifier">print</span> numbers[i],
        <span class="Identifier">print</span>
        solutions = solutions + <span class="Constant">1</span>
    <span class="Statement">else</span>:
        <span class="Statement">if</span> k &lt; <span class="Identifier">len</span>(numbers):
            <span class="Statement">if</span> (numbers[k] * (<span class="Identifier">len</span>(numbers)-k+<span class="Constant">1</span>)) &gt;= target_sum:
                <span class="Statement">if</span> target_sum &gt;= numbers[k]:
                    flags[k] = <span class="Constant">1</span>
                    find_solutions(k+<span class="Constant">1</span>, target_sum - numbers[k])
                    flags[k] = <span class="Constant">0</span>
                find_solutions(k+<span class="Constant">1</span>, target_sum)

<span class="Statement">def</span> <span class="Identifier">find_subset_sum</span>(target_sum):
    <span class="Statement">global</span> solutions
    <span class="Statement">global</span> flags
    <span class="Identifier">print</span> <span class="String">&quot;Subsets which sum up to %s:&quot;</span> % target_sum
    flags = [<span class="Constant">0</span>] * <span class="Identifier">len</span>(numbers)
    find_solutions(<span class="Constant">0</span>, target_sum)
    <span class="Identifier">print</span> <span class="String">&quot;Found&quot;</span>, solutions, <span class="String">&quot;different solutions&quot;</span>

<span class="Statement">def</span> <span class="Identifier">subset_sum_test</span>(size):
    <span class="Statement">global</span> numbers
    total = <span class="Constant">0</span>

    <span class="Identifier">print</span> <span class="String">&quot;Random values:</span><span class="Special">\n</span><span class="String">  &quot;</span>,
    <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, size):
        numbers.append(random.randint(<span class="Constant">0</span>, <span class="Constant">1000</span>))
        total = total + numbers[i]
        <span class="Identifier">print</span> numbers[i],
    <span class="Identifier">print</span>

    numbers = <span class="Identifier">sorted</span>(numbers, reverse = <span class="Identifier">True</span>)
    target_sum = total/<span class="Constant">2</span>
    find_subset_sum(target_sum)

subset_sum_test(<span class="Constant">15</span> <span class="Statement">if</span> <span class="Identifier">len</span>(sys.argv) &lt; <span class="Constant">2</span> <span class="Statement">else</span> <span class="Identifier">int</span>(sys.argv[<span class="Constant">1</span>]))

</pre>

See also [[Blog.DefinePrivatePublic20130630ASubsetOfPython][A Subset Of Python]].

-- Main.ClausBrod - 30 Jun 2013

#SubsetSumCSharp

And here is an implementation in C#:

<pre>
<style type="text/css">
<!--
.String { color: #4a708b; }
.Constant { color: #ff8c00; }
.Statement { color: #b03060; font-weight: bold; }
.Comment { color: #0000ee; font-style: italic; }
.Type { color: #008b00; font-weight: bold; }
-->
</style>
<span class="Statement">using</span> System;

<span class="Type">namespace</span> SubsetSum
{
   <span class="Type">class</span> SubsetSum
   {
      <span class="Type">private</span> <span class="Type">int</span>[] numbers;
      <span class="Type">private</span> <span class="Type">bool</span>[] flags;

      <span class="Type">private</span> <span class="Type">int</span> findSolutions(<span class="Type">int</span> k, <span class="Type">int</span> targetSum, <span class="Type">int</span> solutions=<span class="Constant">0</span>)
      {
         <span class="Statement">if</span> (targetSum == <span class="Constant">0</span>) {
            Console.Write(<span class="String">&quot;  Solution: &quot;</span>);
            <span class="Statement">for</span> (<span class="Type">int</span> i=<span class="Constant">0</span>; i&lt;numbers.Length; i++) {
               <span class="Statement">if</span> (flags[i]) {
                  Console.Write(<span class="String">&quot;{0} &quot;</span>, numbers[i]);
               }
            }
            Console.WriteLine();
            solutions++;
         } <span class="Statement">else</span> {
            <span class="Statement">if</span> (k &lt; numbers.Length) {
               <span class="Statement">if</span> ((numbers[k] * (numbers.Length - k + <span class="Constant">1</span>)) &gt;= targetSum) {
                  <span class="Statement">if</span> (targetSum &gt;= numbers[k]) {
                     flags[k] = <span class="Constant">true</span>;
                     solutions = findSolutions(k + <span class="Constant">1</span>, targetSum - numbers[k], solutions);
                     flags[k] = <span class="Constant">false</span>;
                  }
                  solutions = findSolutions(k + <span class="Constant">1</span>, targetSum, solutions);
               }
            }
         }
         <span class="Statement">return</span> solutions;
      }

      <span class="Type">public</span> <span class="Type">void</span> solve() {
         Array.Sort(numbers, (x, y) =&gt; y - x); <span class="Comment">// sort in reverse order</span>
         Array.Clear(flags, <span class="Constant">0</span>, flags.Length);

         <span class="Type">int</span> total = <span class="Constant">0</span>;
         Array.ForEach(numbers, (<span class="Type">int</span> n) =&gt; total += n);
         <span class="Type">int</span> solutions = findSolutions(<span class="Constant">0</span>, total / <span class="Constant">2</span>);
         Console.WriteLine(<span class="String">&quot;Found {0} different solutions.&quot;</span>, solutions);
      }

      SubsetSum(<span class="Type">int</span> size) {
         numbers = <span class="Statement">new</span> <span class="Type">int</span>[size];
         Random r = <span class="Statement">new</span> Random();
         <span class="Statement">for</span> (<span class="Type">int</span> i = <span class="Constant">0</span>; i &lt; size; i++) {
            numbers[i] = r.Next(<span class="Constant">1000</span>);
            Console.Write(<span class="String">&quot;{0} &quot;</span>, numbers[i]);
         }
         Console.WriteLine();

         flags = <span class="Statement">new</span> <span class="Type">bool</span>[size];
      }

      <span class="Type">public</span> <span class="Type">static</span> <span class="Type">void</span> Main(<span class="Type">string</span>[] args)
      {
         <span class="Type">int</span> size = args.Length &gt; <span class="Constant">1</span> ? <span class="Type">int</span>.Parse(args[<span class="Constant">1</span>]) : <span class="Constant">15</span>;
         <span class="Statement">new</span> SubsetSum(size).solve();
      }
   }
}
</pre>

#SubsetSumDelphi

A na&iuml;ve implementation in Delphi:

<pre id='vimCodeElement'>
<span class="Statement">program</span> subsetsum;

<span class="PreProc">{$APPTYPE CONSOLE}</span>
<span class="PreProc">{$R *.res}</span>

<span class="Statement">uses</span>
  System.Generics.Collections,
  System.Generics.Defaults,
  System.<nop>SysUtils;

<span class="Statement">type</span>
  !TSubsetSum = class
  <span class="Statement">private</span>
    FNumbers: TArray&lt;<span class="Type">Integer</span>&gt;;
    FFlags: TArray&lt;<span class="Type">Boolean</span>&gt;;

    <span class="Statement">function</span> !FindSolutions( aK: <span class="Type">Integer</span>; aTargetSum: <span class="Type">Integer</span>; aSolutions: <span class="Type">Integer</span> = <span class="Constant">0</span> ): <span class="Type">Integer</span>;
  <span class="Statement">public</span>
    <span class="Statement">procedure</span> Solve( );
    <span class="Statement">constructor</span> Create( aSize: <span class="Type">Integer</span> );
  <span class="Statement">end</span>;

<span class="Statement">var</span>
  vSize: <span class="Type">Integer</span>;
  vSubsetSum: !TSubsetSum;

<span class="Statement">constructor</span> !TSubsetSum.Create( aSize: <span class="Type">Integer</span> );
<span class="Statement">var</span>
  i: <span class="Type">Integer</span>;
<span class="Statement">begin</span>
  !SetLength( FNumbers, aSize );
  !SetLength( FFlags, aSize );
  <span class="Identifier">Randomize</span>;
  <span class="Statement">for</span> i := <span class="Constant">0</span> <span class="Statement">to</span> aSize - <span class="Constant">1</span> <span class="Statement">do</span>
  <span class="Statement">begin</span>
    FNumbers[i] := <span class="Identifier">Random</span>( <span class="Constant">1000</span> );
    <span class="Identifier">Write</span>( FNumbers[i].ToString + <span class="Constant">' '</span> );
  <span class="Statement">end</span>;
  <span class="Identifier">writeln</span>;
<span class="Statement">end</span>;

<span class="Statement">function</span> !TSubsetSum.!FindSolutions( aK, aTargetSum, aSolutions: <span class="Type">Integer</span> ): <span class="Type">Integer</span>;
<span class="Statement">begin</span>
  <span class="Statement">if</span> ( aTargetSum = <span class="Constant">0</span> ) <span class="Statement">then</span>
  <span class="Statement">begin</span>
    <span class="Identifier">write</span>( <span class="Constant">'  Solution: '</span> );
    <span class="Statement">for</span> <span class="Statement">var</span> i := <span class="Constant">0</span> <span class="Statement">to</span> <span class="Identifier">Length</span>( FNumbers ) - <span class="Constant">1</span> <span class="Statement">do</span>
      <span class="Statement">if</span> FFlags[i] <span class="Statement">then</span>
        <span class="Identifier">write</span>( FNumbers[i].ToString + <span class="Constant">' '</span> );
    <span class="Identifier">writeln</span>;
    <span class="Identifier">inc</span>( aSolutions );
  <span class="Statement">end</span>
  <span class="Statement">else</span>
  <span class="Statement">begin</span>
    <span class="Statement">if</span> ( aK &lt; <span class="Identifier">Length</span>( FNumbers ) ) <span class="Statement">then</span>
      <span class="Statement">if</span> ( ( FNumbers[aK] * ( <span class="Identifier">Length</span>( FNumbers ) - aK + <span class="Constant">1</span> ) ) &gt;= aTargetSum ) <span class="Statement">then</span>
      <span class="Statement">begin</span>
        <span class="Statement">if</span> ( aTargetSum &gt;= FNumbers[aK] ) <span class="Statement">then</span>
        <span class="Statement">begin</span>
          FFlags[aK] := <span class="Constant">True</span>;
          aSolutions := !FindSolutions( aK + <span class="Constant">1</span>, aTargetSum - FNumbers[aK], aSolutions );
          FFlags[aK] := <span class="Constant">False</span>;
        <span class="Statement">end</span>;
        aSolutions := !FindSolutions( aK + <span class="Constant">1</span>, aTargetSum, aSolutions );
      <span class="Statement">end</span>;
  <span class="Statement">end</span>;
  <span class="Statement">Result</span> := aSolutions;
<span class="Statement">end</span>;

<span class="Statement">procedure</span> !TSubsetSum.Solve;
<span class="Statement">var</span>
  vTotal: <span class="Type">Integer</span>;
  vSolutions: <span class="Type">Integer</span>;
<span class="Statement">begin</span>
  TArray.Sort&lt;<span class="Type">Integer</span>&gt;( FNumbers, TComparer&lt;<span class="Type">Integer</span>&gt;.Construct(
    <span class="Statement">function</span>( <span class="Statement">const</span> Left, Right: <span class="Type">Integer</span> ): <span class="Type">Integer</span>
    <span class="Statement">begin</span>
      <span class="Statement">Result</span> := Right - Left;
    <span class="Statement">end</span> ) );

  vTotal := <span class="Constant">0</span>;
  <span class="Statement">for</span> <span class="Statement">var</span> vNumber: <span class="Type">Integer</span> <span class="Statement">in</span> FNumbers <span class="Statement">do</span>
    vTotal := vTotal + vNumber;

  vSolutions := !FindSolutions( <span class="Constant">0</span>, vTotal <span class="Statement">div</span> <span class="Constant">2</span> );
  <span class="Identifier">writeln</span>( Format( <span class="Constant">'Found %d different solutions.'</span>, [vSolutions] ) );
<span class="Statement">end</span>;

<span class="Statement">begin</span>
  vSize := <span class="Constant">15</span>;
  <span class="Statement">if</span> ( <span class="Identifier">ParamCount</span> &gt; <span class="Constant">1</span> ) <span class="Statement">then</span>
    vSize := <span class="Identifier">ParamStr</span>( <span class="Constant">0</span> ).ToInteger;

  vSubsetSum := !TSubsetSum.Create( vSize );
  vSubsetSum.Solve( );
  vSubsetSum.Free;
<span class="Statement">end</span>.
</pre>

-- Main.ClausBrod - 19 Jan 2021

---

%COMMENT{type="below" nonotify="on"}%See also http://stackoverflow.com/questions/2353497/the-subsets-sum-problem-and-the-solvability-of-np-complete-problems

-- Main.ClausBrod - 16 Mar 2016
to top
End of topic
Skip to action links | Back to top
You are here: CoCreateModeling > MacroSubsetSum

r1.24 - 19 Jan 2021 - 19:20 - ClausBrod to top
CoCreateModeling
Welcome
