Subset sum problem: Difference between revisions
Content added Content deleted
(Add Perl) |
({{Out}}) |
||
Line 3:
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).
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.
|
{| style="text-align: left; width: 40%;" border="4" cellpadding="2" cellspacing="2"
Line 725 ⟶ 726:
[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 ]
Line 948 ⟶ 949:
(subsets N *Words) ) )
(range 1 (length *Words)) )</lang>
{{Out}}
<pre>-> ((archbishop . -915) (gestapo . 915))</pre>
Line 1,180 ⟶ 1,181:
<br>
<pre style="height:90ex">
[1] exorcism -983
Line 1,368 ⟶ 1,369:
set zsss [searchForSubset $wordweights]
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</lang>
{{Out}}
<pre>
Found zero-summing subset: archbishop, gestapo
Line 1,427 ⟶ 1,428:
* <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.
{{Out}}
<pre>
<
| |||