Subset sum problem: Difference between revisions

{{draft task|Discrete math}}

 

;Task:

 

 

|+             Table of weighted words

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

Note that an implementation that depends on enumerating all possible subsets is likely to be infeasible.

<br><br>

 

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

 

subsum(0, 0);

return 0;

 

{{output}}<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy

...</pre>

 

{{trans|Java}}

using System.Collections.Generic;

 

}

}

{{out}}

<pre>The weights of the following 5 subsets add up to zero:

 

(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) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (smokescreen, 423)</pre>

 

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

We use the Pseudo-polynomial time dynamic programming solution, found in the [[wp:Subset sum problem|Subset sum problem]] Wikipedia article. If A and B are the min and max possible sums, the time and memory needed are '''O((B-A)*N)'''. '''Q''' is an array such as Q(i,s) = true if there is a nonempty subset of x0, ..., xi which sums to s.

;; 0 <= i < N , A <= s < B , -A = abs(A)

;; mapping two dims Q(i,s) to one-dim Q(qidx(i,s)) :

(map (lambda(i) (first (list-ref input i))) (fillQ (map rest input))))

 

{{out}}

<pre>

===Brute force===

We use the '''powerset''' procrastinator which gives in sequence all subsets of the input list.

(lib 'sequences) ;; for powerset

 

("deploy" . 44) ("diophantine" . 645) ("efferent" . 54)

("elysee" . -326) ("eradicate" . 376))

 

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

Task data:

 

alliance -624

archbishop -915

 

words=:{.@;:;._2 text

 

Implementation:

 

p=:(#~ 0&<)y

n=:(#~ 0&>)y

keep=: [ #~ #&2@#@[ #: choose i.~ ]

;:inv words #~y e. (p keep P),n keep N

 

Task example:

 

 

Note also that there are over 300,000 valid solutions here. More than can be comfortably displayed:

 

Ns=: </.~ /:~ (I.N e. P){N

+/#@,@{"1 Ps,.Ns

 

(One of those is the empty solution, but the rest of them are valid.)

=={{header|Java}}==

{{trans|Kotlin}}

private static class Item {

private String word;

zeroSum(0, 0);

}

{{out}}

<pre>The weights of the following 5 subsets add up to zero:

 

(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) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (smokescreen, 423)</pre>

 

=={{header|Kotlin}}==

{{trans|C}}

 

class Item(val word: String, val weight: Int) {

println("The weights of the following $LIMIT subsets add up to zero:\n")

zeroSum(0, 0)

 

{{out}}

</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},

{423, smokescreen}}.</pre>

 

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

ReadChar;

 

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

lastfor, print "Length $n: @names[@_]\n" if vecsum(@weights[@_]) == 0;

} @names, $n;

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

{{out}}

 

We can also use different modules for this brute force method. Assuming the same pairs/names/weights variables:

use Algorithm::Combinatorics qw/combinations/;

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

last;

}

 

=={{header|Phix}}==

Simple Brute force

{{out}}

<pre>

</pre>

===Alternative===

Shows the first zero-sum subset found, only.

{{out}}

<pre>

Total 0 for {-61,32,373,311,249,311,32,-92,-185,-433,-402,-247,156,125,249,32,-464,-278,218,32,-123,-216,373,-185,-402,156,-402,-61,902}

</pre>

 

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

<br>which "chunk" to search for solutions &nbsp; (that is, out of the 31 names, take a "chunk" at a time).

 

parse arg target stopAt chunkette . /*option optional arguments from the CL*/

if target=='' | target=="," then target= 0 /*Not specified? Then use the default.*/

if stopAt=='' | stopAt=="," then stopAt= 1 /* " " " " " " */

end /*N*/

call eSort N /*sort the names with weights. */

call tello center(' doing chunk:' chunk" ", 79, '─')

call combN N, chunk /*N items, a CHUNK at a time. */

call tello _ 'solution's(??) "found so far."

end /*chunk*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.= @.0

do n=1 for y; !.n=n /*construct the first combination. */

end /*n*/

if s>target then leave /*Is 1st dig>target? Then we're done.*/

do k=2 for ym; _= !.k; s= s + #._ /*Σ the weights; is sum > target ? */

end /*k*/

if s==target then call telly /*have we found a pot of gold? */

/*──────────────────────────────────────────────────────────────────────────────────────*/

if !.u >= bbase+u then return .combUp(u-1)

p= !.u /*P will be used for the next digt. */

end /*u*/; return 0 /*go back and sum this combination. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

if $==. then do while $.k<$.j; parse value $.j $.k with $.k $.j

end /*while $.k<$.j*/

else do while #.k<#.j; parse value @.j @.k #.j #.k with @.k @.j #.k #.j

end /*while #.k<#.j*/

end /*i*/

end /*while h>1*/; return

/*──────────────────────────────────────────────────────────────────────────────────────*/

tello: parse arg _,e; if e==. then say; say _; call lineout 'SUBSET.'y, _; return

/*──────────────────────────────────────────────────────────────────────────────────────*/

call eSort y, . /*sort the names alphabetically. */

do gs=1 for y; nameL= nameL $.gs /*build a list of names whose sum = 0 */

call tello

call tello 'There are ' N " entries in the (above)" arg(1) 'table.'

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.

 

=={{header|Ring}}==

# Project : Subset sum problem

 

next

return alist

Output:

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

=={{header|Scala}}==

{{Out}}Best seen running in your browser by [https://scastie.scala-lang.org/KnhJimmSTL6QXIGTAdZjBQ Scastie (remote JVM)].

private val LIMIT = 5

private val n = items.length

zeroSum(0, 0)

 

=={{header|Sidef}}==

alliance => -624, archbishop => -915,

brute => 870, centipede => -658,

})

found || say "Length #{n}: (none)"

{{out}}

<pre style="height: 40ex; overflow: scroll">

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

 

=={{header|zkl}}==

{{trans|C}}

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

T("bonnet", 452), T("brute", 870), T("centipede", -658),

 

set:=List.createLong(items.len(),0);

{{out}}

<pre>