Subset sum problem: Difference between revisions

Line 95:

<~~lang~~ 11l>V words = [

<syntaxhighlight lang="11l">V words = [

‘alliance’ = -624, ‘archbishop’ = -925, ‘balm’ = 397,

‘bonnet’ = 452, ‘brute’ = 870, ‘centipede’ = -658,

Line 133:

L(x) s[-neg]

print(x‘ ’words[x])

L.break</~~lang~~>

L.break</syntaxhighlight>

Line 148:

=={{header|Action!}}==

<~~lang~~ ~~Action~~!>DEFINE PTR="CARD"

<syntaxhighlight lang="action!">DEFINE PTR="CARD"

DEFINE PAIR_SIZE="4"

Line 260:

Test(10)

Test(27)

RETURN</~~lang~~>

RETURN</syntaxhighlight>

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Subset_sum_problem.png Screenshot from Atari 8-bit computer]

Line 278:

=={{header|Ada}}==

<~~lang~~ ~~Ada~~>with Ada.Text_IO; use Ada.Text_IO;

<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

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

procedure SubsetSum is

Line 333:

end loop;

end SubsetSum;</~~lang~~>

end SubsetSum;</syntaxhighlight>

<pre>2: archbishop gestapo

Line 363:

=={{header|C}}==

<~~lang~~ c>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

#include <stdlib.h>

Line 427:

subsum(0, 0);

return 0;

}</~~lang~~>

}</syntaxhighlight>

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

Line 434:

=={{header|C sharp|C#}}==

<~~lang~~ csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Collections.Generic;

Line 515:

}

}</~~lang~~>

}</syntaxhighlight>

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

Line 531:

=={{header|C++}}==

<~~lang~~ cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

#include <vector>

Line 598:

subsum(0, 0);

return 0;

}</~~lang~~>

}</syntaxhighlight>

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

Line 609:

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

<~~lang~~ d>void main() {

<syntaxhighlight lang="d">void main() {

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

Line 632:

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

"No solution found.".writeln;

}</~~lang~~>

}</syntaxhighlight>

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

Line 639:

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

<~~lang~~ d>import std.stdio, std.algorithm;

<syntaxhighlight lang="d">import std.stdio, std.algorithm;

enum showAllSolutions = true;

Line 735:

writeln("Zero sums: ", sols);

}</~~lang~~>

}</syntaxhighlight>

Line 743:

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.

<~~lang~~ scheme>

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

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

Line 790:

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

</syntaxhighlight>

</lang>

<pre>

Line 845:

===Brute force===

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

<~~lang~~ scheme>

(lib 'sequences) ;; for powerset

Line 872:

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

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

</syntaxhighlight>

</lang>

=={{header|FunL}}==

<~~lang~~ funl>def subsetSum( s, w, v ) =

<syntaxhighlight lang="funl">def subsetSum( s, w, v ) =

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

Line 919:

for i <- 0..5

println( i, subsetSum(s, snd, i).get() )</~~lang~~>

println( i, subsetSum(s, snd, i).get() )</syntaxhighlight>

Line 933:

=={{header|Go}}==

<~~lang~~ go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 999:

}

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

}</~~lang~~>

}</syntaxhighlight>

<pre>

Line 1,015:

=={{header|Haskell}}==

<~~lang~~ haskell>combinations :: Int -> [a] -> [[a]]

<syntaxhighlight lang="haskell">combinations :: Int -> [a] -> [[a]]

combinations 0 _ = [[]]

combinations _ [] = []

Line 1,046:

W "vein" 813]

main = print $ map word $ head $ solver items</~~lang~~>

main = print $ map word $ head $ solver items</syntaxhighlight>

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

Non brute-force: the list of numbers used here are different, and difficult for a bruteforce method.

<~~lang~~ haskell>subsum :: Int -> [Int] -> [Int]

<syntaxhighlight lang="haskell">subsum :: Int -> [Int] -> [Int]

subsum w =

snd . head . filter ((== w) . fst) . (++ [(w, [])]) . foldl s [(0, [])]

Line 1,073:

main :: IO ()

main = print $ subsum 0 items</~~lang~~>

main = print $ subsum 0 items</syntaxhighlight>

Line 1,079:

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

<~~lang~~ ~~Icon~~>link printf,lists

<syntaxhighlight lang="icon">link printf,lists

procedure main()

Line 1,124:

return T

end</~~lang~~>

end</syntaxhighlight>

Line 1,166:

Task data:

<~~lang~~ J>text=:0 :0

<syntaxhighlight lang="j">text=:0 :0

alliance -624

archbishop -915

Line 1,201:

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

numbs=:+/|:0&".;._2 text</~~lang~~>

numbs=:+/|:0&".;._2 text</syntaxhighlight>

Implementation:

<~~lang~~ J>wsum0=:4 :0

<syntaxhighlight lang="j">wsum0=:4 :0

p=:(#~ 0&<)y

n=:(#~ 0&>)y

Line 1,214:

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

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

)</~~lang~~>

)</syntaxhighlight>

Task example:

<~~lang~~ J> words wsum0 numbs

<syntaxhighlight lang="j"> words wsum0 numbs

centipede markham mycenae</~~lang~~>

centipede markham mycenae</syntaxhighlight>

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

<~~lang~~ J> Ps=: </.~ /:~ (I.P e. N){P

<syntaxhighlight lang="j"> Ps=: </.~ /:~ (I.P e. N){P

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

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

349168</~~lang~~>

349168</syntaxhighlight>

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

Line 1,232:

=={{header|Java}}==

<~~lang~~ ~~Java~~>public class SubsetSum {

<syntaxhighlight lang="java">public class SubsetSum {

private static class Item {

private String word;

Line 1,309:

zeroSum(0, 0);

}

}</~~lang~~>

}</syntaxhighlight>

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

Line 1,326:

'''Works with gojq, the Go implementation of jq''' (provided `keys_unsorted` is replaced by `keys`)

# Input: an array of n elements, each of which is either in or out

# Output: a stream of the 2^n possible selections

Line 1,344:

. as $dict

| keys_unsorted | selections | select( sum($dict; 0));

</syntaxhighlight>

</lang>

'''An Example'''

<~~lang~~ jq>def weights:

<syntaxhighlight lang="jq">def weights:

{

"alliance": -624,

Line 1,381:

};

weights | first(zero_sums)</~~lang~~>

weights | first(zero_sums)</syntaxhighlight>

<pre>

Line 1,398:

=={{header|Julia}}==

<~~lang~~ julia>using Combinatorics

<syntaxhighlight lang="julia">using Combinatorics

const pairs = [

Line 1,428:

zerosums()

</~~lang~~>{{out}}

</syntaxhighlight>{{out}}

<pre>

For length 1: None

Line 1,467:

=={{header|Kotlin}}==

<~~lang~~ scala>// version 1.1.2

<syntaxhighlight lang="scala">// version 1.1.2

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

Line 1,530:

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

zeroSum(0, 0)

}</~~lang~~>

}</syntaxhighlight>

Line 1,548:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<~~lang~~ ~~Mathematica~~>a = {{"alliance", -624}, {"archbishop", -915}, {"balm", 397}, {"bonnet", 452},

<syntaxhighlight lang="mathematica">a = {{"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},

Line 1,557:

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

Map[ (Print["A zero-sum subset of length ", Length[#], " : ", #[[;; , 1]]])& , result ]</~~lang~~>

Map[ (Print["A zero-sum subset of length ", Length[#], " : ", #[[;; , 1]]])& , result ]</syntaxhighlight>

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

Line 1,570:

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.

<~~lang~~ ~~Mathematica~~>a = {{"alliance", -624}, {"archbishop", -915}, {"balm", 397}, {"bonnet", 452},

<syntaxhighlight lang="mathematica">a = {{"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},

Line 1,604:

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

</syntaxhighlight>

</lang>

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

Line 1,622:

=={{header|MiniZinc}}==

%Subset sum. Nigel Galloway: January 6th., 2021.

enum Items={alliance,archbishop,balm,bonnet,brute,centipede,cobol,covariate,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein};

Line 1,629:

var int: wSelected=sum(n in selected)(weight[n]);

constraint wSelected=0;

</syntaxhighlight>

</lang>

<pre>

Line 1,637:

</pre>

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

<~~lang~~ modula2>MODULE SubsetSum;

<syntaxhighlight lang="modula2">MODULE SubsetSum;

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

Line 1,738:

ReadChar;

END SubsetSum.</~~lang~~>

END SubsetSum.</syntaxhighlight>

=={{header|Nim}}==

We need the third party module "itertools" to compute the combinations.

<~~lang~~ ~~Nim~~>import sequtils, strformat, strutils

<syntaxhighlight lang="nim">import sequtils, strformat, strutils

import itertools

Line 1,792:

echo &"For length {lg}, found for example: ", comb.mapIt(words[it]).join(" ")

break checkCombs

echo &"For length {lg}, no set found."</~~lang~~>

echo &"For length {lg}, no set found."</syntaxhighlight>

Line 1,831:

Just search randomly until a result is found:

<~~lang~~ ocaml>let d =

<syntaxhighlight lang="ocaml">let d =

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

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

Line 1,865:

in

let res = aux [] d in

List.iter (fun (n,w) -> Printf.printf " %4d\t%s\n" w n) res</~~lang~~>

List.iter (fun (n,w) -> Printf.printf " %4d\t%s\n" w n) res</syntaxhighlight>

=={{header|Perl}}==

<~~lang~~ perl>use ntheory qw/:all/;

<syntaxhighlight lang="perl">use ntheory qw/:all/;

my %pairs = (

Line 1,889:

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

} @names, $n;

}</~~lang~~>

}</syntaxhighlight>

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

Line 1,905:

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

<~~lang~~ perl>use List::Util qw/sum/;

<syntaxhighlight lang="perl">use List::Util qw/sum/;

use Algorithm::Combinatorics qw/combinations/;

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

Line 1,914:

last;

}

}</~~lang~~>

}</syntaxhighlight>

=={{header|Phix}}==

Simple Brute force

with javascript_semantics

constant {words,weights} = columnize({{"alliance", -624}, {"archbishop", -915},

Line 1,957:

end if

end for

<pre>

Line 1,998:

This is significantly faster (near instant, in fact) than an "all possible combinations" approach.

Shows the first zero-sum subset found, only.

with javascript_semantics

constant weights = {-61, 1, 32, 373, 311, 249, 311, 32, -92, -185, -433,

Line 2,031:

end if

end for

<pre>

Line 2,040:

Using constraint modelling.

<~~lang~~ ~~Picat~~>import cp.

<syntaxhighlight lang="picat">import cp.

%

Line 2,109:

[speakeasy, -745],

[vein, 813 ]

].</~~lang~~>

].</syntaxhighlight>

Line 2,120:

Get a solution - if possible - for a specific number of selected things.

<~~lang~~ ~~Picat~~>go2 =>

things(Things),

foreach(Len in 1..Things.length)

Line 2,131:

nl

end,

nl.</~~lang~~>

nl.</syntaxhighlight>

Line 2,223:

There are in total 349167 solutions of any number of items (the empty set is not a solution in our book).

<~~lang~~ ~~Picat~~>go3 =>

things(Things),

Count = count_all(subset_sum(Things, _X, _Z)),

println(count=Count),

nl.

</syntaxhighlight>

</lang>

=={{header|PicoLisp}}==

<~~lang~~ ~~PicoLisp~~>(de *Words

<syntaxhighlight lang="picolisp">(de *Words

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

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

Line 2,241:

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

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

(smokescreen . 423) (speakeasy . -745) (vein . 813) )</~~lang~~>

(smokescreen . 423) (speakeasy . -745) (vein . 813) )</syntaxhighlight>

Minimal brute force solution:

<~~lang~~ ~~PicoLisp~~>(load "@lib/simul.l") # For 'subsets'

<syntaxhighlight lang="picolisp">(load "@lib/simul.l") # For 'subsets'

(pick

Line 2,249:

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

(subsets N *Words) ) )

(range 1 (length *Words)) )</~~lang~~>

(range 1 (length *Words)) )</syntaxhighlight>

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

Line 2,255:

=={{header|Python}}==

===Version 1===

<~~lang~~ python>words = { # some values are different from example

<syntaxhighlight lang="python">words = { # some values are different from example

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

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

Line 2,289:

for x in s[-neg]:

print(x, words[x])

break</~~lang~~>

break</syntaxhighlight>

{{out}}<pre>

('mycenae', 183)

Line 2,300:

</pre>

===Brute force===

<~~lang~~ python>>>> from itertools import combinations

<syntaxhighlight lang="python">>>> from itertools import combinations

>>>

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

Line 2,320:

>>> answer

[('archbishop', -915), ('gestapo', 915)]</~~lang~~>

[('archbishop', -915), ('gestapo', 915)]</syntaxhighlight>

=={{header|Racket}}==

<~~lang~~ racket>

#lang racket

Line 2,358:

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

(zero-subsets words)

</syntaxhighlight>

</lang>

<pre>

Line 2,371:

=={{header|Raku}}==

(formerly Perl 6)

<lang ~~perl6~~>my @pairs =

<syntaxhighlight lang="raku" line>my @pairs =

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

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

Line 2,388:

default { "Length $n: (none)" }

}

}</~~lang~~>

}</syntaxhighlight>

<pre>Length 1: (none)

Line 2,428:

Added was "que pasa" informational messages.   The sum   (which is zero for this task)   can be any number,

and can be specifiable on the command line.

<~~lang~~ rexx>/*REXX program finds some non─null subsets of a weighted list whose sum eqals zero.*/

<syntaxhighlight lang="rexx">/*REXX program finds some non─null subsets of a weighted list whose sum eqals zero.*/

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

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

Line 2,517:

call tello

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

call tello; return</~~lang~~>

call tello; return</syntaxhighlight>

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

──────── where   nnn   is the ''chunk'' number.

Line 2,583:

=={{header|Ring}}==

<~~lang~~ ring>

# Project : Subset sum problem

Line 2,664:

return alist

</syntaxhighlight>

</lang>

Output:

<pre>

Line 2,677:

=={{header|Ruby}}==

a brute force solution:

<~~lang~~ ruby>weights = {

<syntaxhighlight lang="ruby">weights = {

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

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

Line 2,699:

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

end

end</~~lang~~>

end</syntaxhighlight>

Line 2,737:

=={{header|Scala}}==

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

<~~lang~~ ~~Scala~~>object SubsetSum extends App {

<syntaxhighlight lang="scala">object SubsetSum extends App {

private val LIMIT = 5

private val n = items.length

Line 2,799:

zeroSum(0, 0)

}</~~lang~~>

}</syntaxhighlight>

=={{header|Sidef}}==

<~~lang~~ ruby>var pairs = Hash(

<syntaxhighlight lang="ruby">var pairs = Hash(

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

brute => 870, centipede => -658,

Line 2,834:

})

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

}</~~lang~~>

}</syntaxhighlight>

Line 2,870:

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

<~~lang~~ tcl>proc subsetsOfSize {set size} {

<syntaxhighlight lang="tcl">proc subsetsOfSize {set size} {

if {$size <= 0} {

return

Line 2,896:

# Nothing was found

return -code error "no subset sums to zero"

}</~~lang~~>

}</syntaxhighlight>

Demonstrating:

<~~lang~~ tcl>set wordweights {

<syntaxhighlight lang="tcl">set wordweights {

alliance -624

archbishop -915

Line 2,932:

}

set zsss [searchForSubset $wordweights]

puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</~~lang~~>

puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</syntaxhighlight>

<pre>

Line 2,940:

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

<~~lang~~ ~~Ursala~~>#import std

<syntaxhighlight lang="ursala">#import std

#import int

Line 2,982:

#cast %zm

main = nullset weights</~~lang~~>

main = nullset weights</syntaxhighlight>

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

Line 3,007:

=={{header|Wren}}==

<~~lang~~ ecmascript>import "/fmt" for Fmt

<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt

class Item {

Line 3,082:

System.print("The weights of the following %(LIMIT) subsets add up to zero:\n")

zeroSum.call(0, 0)</~~lang~~>

zeroSum.call(0, 0)</syntaxhighlight>

Line 3,204:

=={{header|zkl}}==

<~~lang~~ zkl>var items=T(

<syntaxhighlight lang="zkl">var items=T(

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

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

Line 3,230:

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

try{ subSum(set,0,0); }catch(TheEnd){}</~~lang~~>

try{ subSum(set,0,0); }catch(TheEnd){}</syntaxhighlight>

<pre>