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}}==

A simple brute-force solution. This used the module of the third D solution of the Combinations Task.

{{trans|Ruby}}

import std.stdio, std.algorithm, std.typecons, combinations3;

 

comb.map!q{ a[0] });

"No solution found.".writeln;

{{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}}

 

enum showAllSolutions = true;

 

writeln("Zero sums: ", sols);

{{out}}

<pre>Zero sums: 349167</pre>

 

=={{header|FunL}}==

def sumset( a ) = foldl1( (+), map(w, a) )

 

for i <- 0..5

 

{{out}}

 

=={{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}}

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}

The above code uses a brute-force approach, but Mathematica includes several solution schemes that can be used to solve this problem. We can cast it as an integer linear programming problem, and thus find the largest or smallest subset sum, or even sums with specific constraints, such as a sum using three negative values and nine positive values.

 

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

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

 

Print["3 -ves, 9 +ves: ", Select[Transpose[{threeNineSoln*aValues, aNames}], #[[1]] != 0 &]];

 

<pre>Maximal solution: {{-624, alliance}, {-915, archbishop}, {397, balm},

{170, fiat}, {503, flatworm}, {-982, isis}, {475, markham},

{423, smokescreen}}.</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|Perl}}==

{{libheader|ntheory}}

 

my %pairs = (

mincemeat => -880, moresby => 756, mycenae => 183, plugging => -266,

smokescreen => 423, speakeasy => -745, vein => 813 );

 

forcomb {

} @names, $n;

Printing just the first one found for each number of elements:

{{out}}

<pre>

Length 2: archbishop gestapo

... to length 27 ...

</pre>

 

use Algorithm::Combinatorics qw/combinations/;

foreach my $n (1 .. @names) {

last;

}

 

 

{{out}}

 

=={{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) ) )

{{Out}}

<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

 

=={{header|Racket}}==

#lang racket

 

(for ([i (sub1 len)]) (loop l len (add1 i) '() 0)))

(zero-subsets words)

{{out}}

<pre>

(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)

</pre>

 

=={{header|REXX}}==

This REXX solution isn't limited to integers for the weights. &nbsp; &nbsp; This isn't a brute force solution.

<br>improved algorithm (by an order of magnitude), so the extra code to sort the list was included, as well as

<br>another sort to show the solutions in alphabetical order. &nbsp; Support was also added to allow specification of

 

 

Output note: &nbsp; this program also writes the displayed output to file(s): &nbsp; SUBSET.nnn

<br> ──────── where &nbsp; nnn &nbsp; is the ''chunk'' number.

 

[1] exorcism -983

[2] isis -982

[31] lindholm 999

 

 

─────────────────────────────── doing chunk: 1 ────────────────────────────────

─────────────────────────────── doing chunk: 2 ────────────────────────────────

─────────────────────────────── doing chunk: 3 ────────────────────────────────

─────────────────────────────── doing chunk: 4 ────────────────────────────────

 

Stopped after finding 12 subsets.

</pre>

 

=={{header|Ruby}}==

a brute force solution:

'alliance' =>-624, 'archbishop'=>-915, 'balm' => 397, 'bonnet' => 452,

'brute' => 870, 'centipede' =>-658, 'cobol' => 362, 'covariate'=> 590,

puts "no subsets of length #{n} sum to zero"

end

 

{{out}}

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]

{{Out}}

<pre>

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

'smokescreen': 423,

'speakeasy': -745>

</pre>