StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>My thought was to identify which group of numbers is equal to the delta between the 2 sets, and that would identify the problem directly.</p> </blockquote> <p>The problem "<em>given an integer s, and a set of integers, does any non-empty subset of the set sum to s?</em>" is known as the "<a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">subset sum problem</a>". It is extremely well studied, and it is NP-Complete. (See <a href="http://xkcd.com/287/" rel="nofollow">this link</a> for a related problem.)</p> <p>That is to say it is amongst the hardest problems to solve in a reasonable amount of time. It is widely believed (though at present not <em>proved</em>) that no polynomial-time algorithm can possibly exist for this problem. The best you can do is something like O(2^n) for a set containing n elements. </p> <p>(I note that your problem is in floats, not integers. It doesn't really matter, as long as you correctly handle the comparison of the calculated sum to the target sum to handle any rounding error that might have accrued in doing the sum.)</p> <p>For a small number of elements -- you say you have only 15 or so in the set -- your best bet is to just try them all exhaustively. Here's how you do that.</p> <p>The trick is to realize that there is one subset for each integer from 0 to 2^n. If you look at those numbers in binary:</p> <pre><code>0000 0001 0010 0011 ... </code></pre> <p>each one corresponds to a subset. The first has no members. The second has just group 1. The third has just group 2. The fourth has group 1 and group 2. And so on.</p> <p>The pseudocode is easy enough:</p> <pre><code>for each integer i from 1 to 2^n { sum = 0; for each integer b from 1 to n { if the bth bit of i is on then sum = sum + group(b) } if sum == target then print out i in binary and quit } quit with no solution </code></pre> <p>Obviously this is O(n 2^n). If you can find an algorithm that <em>always</em> does better than O(c^n), or <em>prove</em> that you cannot find such an algorithm then you'll be famous forever.</p> <p>The Wikipedia article has a better algorithm that gives an answer much faster <em>most</em> but not <em>all</em> of the time. I would go with the naive algorithm first since it will only take you a few minutes to code up; if it is unacceptably slow then go for the faster, more complex algorithm.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload