Subset sum problem: Difference between revisions

{{draft task|Discrete math}}

 

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 [http://www.dropbox.com/jobs/challenges Diet] candidate screening exercise and the [[wp:Subset sum problem|Subset sum problem]] Wikipedia article).

 

 

|- style="background-color: rgb(255, 204, 255);"

! word !! weight

| 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.

 

 

=={{header|Ada}}==

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

procedure SubsetSum is

end loop;

end loop;

{{out}}

<pre>2: archbishop gestapo

 

=={{header|C}}==

#include <stdlib.h>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}

 

 

 

 

 

=={{header|D}}==

{{trans|Ruby}}

 

immutable items = [

P("alliance", -624), P("archbishop", -915), P("balm", 397),

P("vein", 813)];

 

return writefln("A subset of length %d: %-(%s, %)", n,

{{out}}

<pre>A subset of length 2: archbishop, gestapo</pre>

This version prints all the 349_167 solutions in about 1.8 seconds and counts them in about 0.05 seconds.

{{trans|C}}

 

 

struct Item { string data; int weight; }

{"mincemeat", -880}, {"moresby", 756}, {"mycenae", 183},

{"plugging", -266}, {"smokescreen", 423}, {"speakeasy", -745},

 

Sum[] mkSums(in Item[] p, in size_t n, in size_t shift) {

r[1 << i].sum = p[i].weight;

 

ri = Sum(r[i & ~b].sum + r[b].sum, i << shift);

}

 

}

 

if (mask & (1U << m))

// Much faster than writeln.

printf("%s ", em[m].data.ptr);

if (mask)

 

static if (showAllSolutions)

showMask(l[x].mask | r[y].mask);

return s;

 

writeln("Zero sums: ", sols);

{{out}}

<pre>Zero sums: 349167</pre>

 

=={{header|Go}}==

 

import "fmt"

}

fmt.Println("no subset sums to 0")

{{out}}

<pre>

 

=={{header|Haskell}}==

combinations 0 _ = [[]]

combinations _ [] = []

W "vein" 813]

 

{{out}}

<pre>["archbishop","gestapo"]</pre>

 

items = [-61, 1, 32, 373, 311, 249, 311, 32, -92, -185, -433,

{{out}}

 

=={{header|Icon}} and {{header|Unicon}}==

{{trans|Ruby}}

 

procedure main()

 

return T

 

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/lists.icn lists.icn provides lcomb for list combinations]

 

A zero-sum subset of length 2 : [ archbishop gestapo ]

A zero-sum subset of length 3 : [ centipede markham mycenae ]

No zero-sum subsets of length 31</pre>

 

{"brute", 870}, {"centipede", -658}, {"cobol", 362}, {"covariate", 590},{"departure", 952},

{"deploy", 44}, {"diophantine", 645}, {"efferent", 54}, {"elysee", -326}, {"eradicate", 376},

 

result = Rest@Select[ Subsets[a, 7], (Total[#[[;; , 2]]] == 0) &];

 

<pre>A zero-sum subset of length 2 : {archbishop,gestapo}

A zero-sum subset of length 4 : {brute,centipede,efferent,plugging}

....</pre>

 

=={{header|OCaml}}==

Just search randomly until a result is found:

 

[ "alliance", -624; "archbishop", -915; "balm", 397; "bonnet", 452;

"brute", 870; "centipede", -658; "cobol", 362; "covariate", 590;

in

let res = aux [] d in

 

=={{header|PicoLisp}}==

(alliance . -624) (archbishop . -915) (balm . 397) (bonnet . 452)

(brute . 870) (centipede . -658) (cobol . 362) (covariate . 590)

(infra . -847) (isis . -982) (lindholm . 999) (markham . 475)

(mincemeat . -880) (moresby . 756) (mycenae . 183) (plugging . -266)

Minimal brute force solution:

 

(pick

(find '((L) (=0 (sum cdr L)))

(subsets N *Words) ) )

<pre>-> ((archbishop . -915) (gestapo . 915))</pre>

 

=={{header|Python}}==

===Version 1===

"alliance": -624, "archbishop": -925, "balm": 397,

"bonnet": 452, "brute": 870, "centipede": -658,

for x in s[-neg]:

print(x, words[x])

{{out}}<pre>

('mycenae', 183)

</pre>

===Brute force===

>>>

>>> word2weight = {"alliance": -624, "archbishop": -915, "balm": 397, "bonnet": 452,

>>> answer

 

 

 

 

 

 

 

 

 

 

 

 

[1] exorcism -983

[2] isis -982

[31] lindholm 999

 

 

</pre>

 

=={{header|Ruby}}==

a brute force solution:

}

 

1.upto(words.length) do |n|

zerosum = words.combination(n).find do |subset|

end

puts "a subset of length #{n} that sums to zero: #{zerosum}"

end

 

a subset of length 2 that sums to zero: ["archbishop", "gestapo"]

a subset of length 3 that sums to zero: ["centipede", "markham", "mycenae"]

no subsets of length 30 sum to zero

no subsets of length 31 sum to zero</pre>

 

=={{header|Tcl}}==

As it turns out that the problem space has small subsets that sum to zero, it is more efficient to enumerate subsets in order of their size rather than doing a simple combination search. This is not true of all possible input data sets though; the problem is known to be NP-complete after all.

if {$size <= 0} {

return

# Nothing was found

return -code error "no subset sums to zero"

Demonstrating:

alliance -624

archbishop -915

}

set zsss [searchForSubset $wordweights]

<pre>

Found zero-summing subset: archbishop, gestapo

=={{header|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.

#import int

 

#cast %zm

 

The name of the function that takes the weighted set is <code>nullset</code>. 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:

* <code>=><></code> fold right combinator with the empty list as the vacuuous case

* <code>~&lrmPC</code> Cons the new word to the list of existing ones.

* <code>~&nZFihmPB+</code> To conclude, search for a result with a zero sum, if any, and return its associated subset of weighted words.

<pre>

<

'smokescreen': 423,

'speakeasy': -745>

</pre>