Subset sum problem: Difference between revisions
Content added Content deleted
(Add Perl) |
({{Out}}) |
||
| Line 3: | 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). |
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 |
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" |
{| style="text-align: left; width: 40%;" border="4" cellpadding="2" cellspacing="2" |
||
| Line 725: | Line 726: | ||
[http://www.cs.arizona.edu/icon/library/src/procs/lists.icn lists.icn provides lcomb for list combinations] |
[http://www.cs.arizona.edu/icon/library/src/procs/lists.icn lists.icn provides lcomb for list combinations] |
||
{{Out}}<pre>No zero-sum subsets of length 1 |
|||
A zero-sum subset of length 2 : [ archbishop gestapo ] |
A zero-sum subset of length 2 : [ archbishop gestapo ] |
||
A zero-sum subset of length 3 : [ centipede markham mycenae ] |
A zero-sum subset of length 3 : [ centipede markham mycenae ] |
||
| Line 948: | Line 949: | ||
(subsets N *Words) ) ) |
(subsets N *Words) ) ) |
||
(range 1 (length *Words)) )</lang> |
(range 1 (length *Words)) )</lang> |
||
{{Out}} |
|||
Output: |
|||
<pre>-> ((archbishop . -915) (gestapo . 915))</pre> |
<pre>-> ((archbishop . -915) (gestapo . 915))</pre> |
||
| Line 1,180: | Line 1,181: | ||
<br> |
<br> |
||
{{Out}} when using the input of: <tt> 0 12 </tt><br> |
|||
(The above arguments set the target sum to zero and limits finding of a dozen solutions.) |
|||
<pre style="height:90ex"> |
<pre style="height:90ex"> |
||
[1] exorcism -983 |
[1] exorcism -983 |
||
| Line 1,368: | Line 1,369: | ||
set zsss [searchForSubset $wordweights] |
set zsss [searchForSubset $wordweights] |
||
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</lang> |
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</lang> |
||
{{Out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Found zero-summing subset: archbishop, gestapo |
Found zero-summing subset: archbishop, gestapo |
||
| Line 1,427: | Line 1,428: | ||
* <code>~&lrmPC</code> Cons the new word to the list of existing ones. |
* <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. |
* <code>~&nZFihmPB+</code> To conclude, search for a result with a zero sum, if any, and return its associated subset of weighted words. |
||
{{Out}} |
|||
output: |
|||
<pre> |
<pre> |
||
< |
< |
||