Subset sum problem: Difference between revisions
(→{{header|C}}: to should only be incremented if sums is incremented) |
(→{{header|C}}: get rid of nonstandard header) |
||
Line 80: | Line 80: | ||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include < |
#include <limits.h> |
||
#include <string.h> |
#include <string.h> |
||
#define INTBITS (sizeof(int) * CHAR_BIT) |
|||
#define MAX_WEIGHT 1024 |
#define MAX_WEIGHT 1024 |
||
typedef struct { void* data; int weight; } item; |
typedef struct { void* data; int weight; } item; |
Revision as of 00:45, 4 January 2012
Implement a function/procedure/method/subroutine that takes a set/array/list/stream/table/collection of words with integer weights, and identifies a non-empty subset of them whose weights sum to zero (cf. the Dropbox Diet candidate screening exercise and the Subset sum problem Wikipedia article).
For example, for this set of weighted words, one solution would be the set of words {elysee, efferent, deploy, departure, centipede, bonnet, balm, archbishop}, because their respective weights of -326, 54, 44, 952, -658, 452, 397, and -915 sum to zero.
word | weight |
---|---|
alliance | -624 |
archbishop | -915 |
balm | 397 |
bonnet | 452 |
brute | 870 |
centipede | -658 |
cobol | 362 |
covariate | 590 |
departure | 952 |
deploy | 44 |
diophantine | 645 |
efferent | 54 |
elysee | -326 |
eradicate | 376 |
escritoire | 856 |
exorcism | -983 |
fiat | 170 |
filmy | -874 |
flatworm | 503 |
gestapo | 915 |
infra | -847 |
isis | -982 |
lindholm | 999 |
markham | 475 |
mincemeat | -880 |
moresby | 756 |
mycenae | 183 |
plugging | -266 |
smokescreen | 423 |
speakeasy | -745 |
vein | 813 |
Another solution would be the set of words {flatworm, gestapo, infra, isis, lindholm, plugging, smokescreen, speakeasy}, because their respective weights of 503, 915, -847, -982, 999, -266, 423, and -745 also sum to zero.
You may assume the weights range from -1000 to 1000. If there are multiple solutions, only one needs to be found. Use any algorithm you want and demonstrate it on a set of at least 30 weighted words with the results shown in a human readable form. Note that an implementation that depends on enumerating all possible subsets is likely to be infeasible.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <limits.h>
- include <string.h>
- define INTBITS (sizeof(int) * CHAR_BIT)
- define MAX_WEIGHT 1024
typedef struct { void* data; int weight; } item;
inline void setbit(int *x, int n) { x[n/INTBITS] |= (1 << (n % INTBITS)); }
inline int hasbit(int *x, int n) { return x[n/INTBITS] & (1 << (n % INTBITS)); }
int* subsum(item *x, int n) { int *buf, *from, *to, sums, alloc, i; int len = 1 + (n + (INTBITS - 1)) / INTBITS; /* 1 weight, rest bit field */ int rlen = len * sizeof(int); int *seen = calloc(sizeof(int), 2 * n * (MAX_WEIGHT / INTBITS) + 2);
buf = calloc(len, sizeof(int)); alloc = sums = 1;
for (i = 0; i < n; i++) { if (alloc < sums * 2) { alloc = sums * 2; buf = realloc(buf, rlen * alloc); }
for (from = to = buf + len * sums; from > buf; ) { from -= len; if (hasbit(seen, from[0] + x[i].weight + MAX_WEIGHT * n)) continue;
setbit(seen, from[0] + x[i].weight + MAX_WEIGHT * n);
memcpy(to, from, rlen); setbit(to + 1, i); sums++;
if (to[0] += x[i].weight) { to += len; continue; }
/* found it */ memcpy(buf, to, rlen); free(seen); return realloc(buf, rlen); } }
/* no solution */ free(seen); free(buf); return 0; }
int main(void) { item em[] = { {"alliance", -624}, {"archbishop", -915}, {"balm", 397}, {"bonnet", 452}, {"brute", 870}, {"centipede", -658}, {"cobol", 362}, {"covariate", 590}, {"departure", 952}, {"deploy", 44}, {"diophantine", 645}, {"efferent", 54}, {"elysee", -326}, {"eradicate", 376}, {"escritoire", 856}, {"exorcism", -983}, {"fiat", 170}, {"filmy", -874}, {"flatworm", 503}, {"gestapo", 915}, {"infra", -847}, {"isis", -982}, {"lindholm", 999}, {"markham", 475}, {"mincemeat", -880}, {"moresby", 756}, {"mycenae", 183}, {"plugging", -266}, {"smokescreen", 423}, {"speakeasy", -745}, {"vein", 813} };
int *ret, n = sizeof(em)/sizeof(em[0]);
if (!(ret = subsum(em, n))) { puts("no zero sums\n"); return 1; }
while (n--) if (hasbit(ret + 1, n)) printf("%2d| %5d %s\n", n, em[n].weight, (char*)em[n].data);
free(ret);
return 0; }</lang> output<lang>12| -326 elysee 11| 54 efferent
9| 44 deploy 8| 952 departure 5| -658 centipede 3| 452 bonnet 2| 397 balm 1| -915 archbishop</lang>
D
A very simple brute-force solution.
<lang d>import std.stdio, std.algorithm, std.string, std.typecons;
T[][] combinations(T)(T[] arr, int k) {
if (k == 0) return [[]]; T[][] result; foreach (i, x; arr) foreach (suffix; combinations(arr[i+1 .. $], k-1)) result ~= x ~ suffix; return result;
}
void main() {
alias tuple T; immutable items = [
T("alliance", -624), T("archbishop", -915), T("balm", 397), T("bonnet", 452), T("brute", 870), T("centipede", -658), T("cobol", 362), T("covariate", 590), T("departure", 952), T("deploy", 44), T("diophantine", 645), T("efferent", 54), T("elysee", -326), T("eradicate", 376), T("escritoire", 856), T("exorcism", -983), T("fiat", 170), T("filmy", -874), T("flatworm", 503), T("gestapo", 915), T("infra", -847), T("isis", -982), T("lindholm", 999), T("markham", 475), T("mincemeat", -880), T("moresby", 756), T("mycenae", 183), T("plugging", -266), T("smokescreen", 423), T("speakeasy", -745), T("vein", 813)];
foreach (n; 1 .. items.length) foreach (comb; combinations(items, n)) if (reduce!q{ a + b[1] }(0, comb) == 0) { const solution = join(map!q{ a[0] }(comb), ", "); writefln("A subset of length %d: %s", n, solution); return; } writefln("No solution found.");
}</lang> Output:
A subset of length 2: archbishop, gestapo
Python
A brute force solution is enough.
<lang python>from itertools import combinations
words = [ ("alliance", -624), ("archbishop", -915), ("balm", 397), ("bonnet", 452), ("brute", 870), ("centipede", -658), ("cobol", 362), ("covariate", 590), ("departure", 952), ("deploy", 44), ("diophantine", 645), ("efferent", 54), ("elysee", -326), ("eradicate", 376), ("escritoire", 856), ("exorcism", -983), ("fiat", 170), ("filmy", -874), ("flatworm", 503), ("gestapo", 915), ("infra", -847), ("isis", -982), ("lindholm", 999), ("markham", 475), ("mincemeat", -880), ("moresby", 756), ("mycenae", 183), ("plugging", -266), ("smokescreen", 423), ("speakeasy", -745), ("vein", 813)]
for n in xrange(1, len(words)):
for comb in combinations(words, n): if sum(c[1] for c in comb) == 0: sol = ", ".join(r[0] for r in comb) print "A subset of length %d: %s" % (n, sol) break else: print "No subsets of length", n, "sum to zero."</lang>
Output:
No subsets of length 1 sum to zero. A subset of length 2: archbishop, gestapo A subset of length 3: centipede, markham, mycenae A subset of length 4: alliance, balm, deploy, mycenae A subset of length 5: alliance, brute, covariate, deploy, mincemeat A subset of length 6: alliance, archbishop, balm, deploy, gestapo, mycenae A subset of length 7: alliance, archbishop, bonnet, cobol, departure, exorcism, moresby A subset of length 8: alliance, archbishop, balm, bonnet, fiat, flatworm, isis, lindholm A subset of length 9: alliance, archbishop, balm, bonnet, brute, covariate, eradicate, mincemeat, plugging A subset of length 10: alliance, archbishop, balm, bonnet, brute, centipede, cobol, departure, deploy, mincemeat A subset of length 11: alliance, archbishop, balm, bonnet, brute, centipede, cobol, departure, infra, moresby, speakeasy A subset of length 12: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, diophantine, efferent, elysee, infra A subset of length 13: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, efferent, eradicate, filmy, isis A subset of length 14: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, elysee, filmy, markham, speakeasy A subset of length 15: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, elysee, exorcism, flatworm, infra, mycenae A subset of length 16: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, elysee, exorcism, filmy, gestapo, infra A subset of length 17: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, exorcism, isis, mincemeat, mycenae, plugging, vein A subset of length 18: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, exorcism, filmy, isis, mycenae, vein A subset of length 19: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, fiat, infra, isis, smokescreen A subset of length 20: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, gestapo, infra, isis, smokescreen, speakeasy A subset of length 21: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, flatworm, infra, lindholm, mincemeat, plugging, speakeasy A subset of length 22: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, escritoire, exorcism, fiat, filmy, flatworm, mincemeat, plugging, speakeasy A subset of length 23: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, escritoire, exorcism, infra, isis, mincemeat, moresby, mycenae, smokescreen, speakeasy A subset of length 24: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, exorcism, filmy, gestapo, infra, markham, mincemeat, moresby, mycenae, plugging, smokescreen, speakeasy A subset of length 25: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, eradicate, exorcism, fiat, filmy, flatworm, infra, isis, lindholm, markham, mincemeat, moresby, mycenae, plugging, speakeasy A subset of length 26: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, elysee, eradicate, escritoire, exorcism, fiat, filmy, gestapo, infra, isis, markham, mincemeat, mycenae, plugging, speakeasy, vein A subset of length 27: alliance, archbishop, balm, bonnet, brute, centipede, covariate, departure, deploy, efferent, elysee, eradicate, escritoire, exorcism, fiat, filmy, flatworm, infra, isis, lindholm, markham, mincemeat, moresby, mycenae, plugging, smokescreen, speakeasy No subsets of length 28 sum to zero. No subsets of length 29 sum to zero. No subsets of length 30 sum to zero.
Ruby
a brute force solution: <lang ruby>weights = {
'alliance' => -624, 'archbishop' => -915, 'balm' => 397, 'bonnet' => 452, 'brute' => 870, 'centipede' => -658, 'cobol' => 362, 'covariate' => 590, 'departure' => 952, 'deploy' => 44, 'diophantine' => 645, 'efferent' => 54, 'elysee' => -326, 'eradicate' => 376, 'escritoire' => 856, 'exorcism' => -983, 'fiat' => 170, 'filmy' => -874, 'flatworm' => 503, 'gestapo' => 915, 'infra' => -847, 'isis' => -982, 'lindholm' => 999, 'markham' => 475, 'mincemeat' => -880, 'moresby' => 756, 'mycenae' => 183, 'plugging' => -266, 'smokescreen' => 423, 'speakeasy' => -745, 'vein' => 813,
}
words = weights.keys 1.upto(words.length) do |n|
zerosum = words.combination(n).find do |subset| subset.reduce(0) {|sum, word| sum += weights[word]} == 0 end
if zerosum.nil? puts "no subsets of length #{n} sum to zero" else puts "a subset of length #{n} that sums to zero: #{zerosum}" end
end</lang>
output:
no subsets of length 1 sum to zero a subset of length 2 that sums to zero: ["archbishop", "gestapo"] a subset of length 3 that sums to zero: ["centipede", "markham", "mycenae"] a subset of length 4 that sums to zero: ["alliance", "balm", "deploy", "mycenae"] a subset of length 5 that sums to zero: ["alliance", "brute", "covariate", "deploy", "mincemeat"] a subset of length 6 that sums to zero: ["alliance", "archbishop", "balm", "deploy", "gestapo", "mycenae"] a subset of length 7 that sums to zero: ["alliance", "archbishop", "bonnet", "cobol", "departure", "exorcism", "moresby"] a subset of length 8 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "fiat", "flatworm", "isis", "lindholm"] a subset of length 9 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "covariate", "eradicate", "mincemeat", "plugging"] a subset of length 10 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "deploy", "mincemeat"] a subset of length 11 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "infra", "moresby", "speakeasy"] a subset of length 12 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "diophantine", "efferent", "elysee", "infra"] a subset of length 13 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "efferent", "eradicate", "filmy", "isis"] a subset of length 14 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "filmy", "markham", "speakeasy"] a subset of length 15 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "exorcism", "flatworm", "infra", "mycenae"] a subset of length 16 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "elysee", "exorcism", "filmy", "gestapo", "infra"] a subset of length 17 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "exorcism", "isis", "mincemeat", "mycenae", "plugging", "vein"] a subset of length 18 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "filmy", "isis", "mycenae", "vein"] a subset of length 19 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "fiat", "infra", "isis", "smokescreen"] a subset of length 20 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "gestapo", "infra", "isis", "smokescreen", "speakeasy"] a subset of length 21 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "flatworm", "infra", "lindholm", "mincemeat", "plugging", "speakeasy"] a subset of length 22 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "mincemeat", "plugging", "speakeasy"] a subset of length 23 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "infra", "isis", "mincemeat", "moresby", "mycenae", "smokescreen", "speakeasy"] a subset of length 24 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "filmy", "gestapo", "infra", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"] a subset of length 25 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "eradicate", "exorcism", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "speakeasy"] a subset of length 26 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "gestapo", "infra", "isis", "markham", "mincemeat", "mycenae", "plugging", "speakeasy", "vein"] a subset of length 27 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "covariate", "departure", "deploy", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"] no subsets of length 28 sum to zero no subsets of length 29 sum to zero no subsets of length 30 sum to zero no subsets of length 31 sum to zero
Ursala
This solution scans the set sequentially while maintaining a record of all distinct sums obtainable by words encountered thus far, and stops when a zero sum is found. <lang Ursala>#import std
- import int
weights =
{
'alliance': -624, 'archbishop': -915, 'balm': 397, 'bonnet': 452, 'brute': 870, 'centipede': -658, 'cobol': 362, 'covariate': 590, 'departure': 952, 'deploy': 44, 'diophantine': 645, 'efferent': 54, 'elysee': -326, 'eradicate': 376, 'escritoire': 856, 'exorcism': -983, 'fiat': 170, 'filmy': -874, 'flatworm': 503, 'gestapo': 915, 'infra': -847, 'isis': -982, 'lindholm': 999, 'markham': 475, 'mincemeat': -880, 'moresby': 756, 'mycenae': 183, 'plugging': -266, 'smokescreen': 423, 'speakeasy': -745, 'vein': 813}
nullset = ~&nZFihmPB+ =><> ~&ng?r\~&r ^TnK2hS\~&r ^C/~&lmPlNCX *D ^A/sum@lmPrnPX ~&lrmPC
- cast %zm
main = nullset weights</lang>
The name of the function that takes the weighted set is nullset
. It manipulates a partial result represented as a list of pairs, each containing a subset of weighted words and the sum of their weights. Here is a rough translation:
=><>
fold right combinator with the empty list as the vacuuous case~&ng?r\~&r
If the partial result contains a zero sum, return it.^TnK2hS\~&r
Concatenate the partial result with the new list of subsets (computed as follows) and delete duplicate sums.^C/~&lmPlNCX
Cons a singleton subset containing the next word to the partial results.*D
Distribute the next word in the set to the partial results and do the following to each.sum@lmPrnPX
Add the weight of the new word to the existing sum.~&lrmPC
Cons the new word to the list of existing ones.~&nZFihmPB+
To conclude, search for a result with a zero sum, if any, and return its associated subset of weighted words.
output:
< 'flatworm': 503, 'gestapo': 915, 'infra': -847, 'isis': -982, 'lindholm': 999, 'plugging': -266, 'smokescreen': 423, 'speakeasy': -745>