Rosetta Code

Subset sum problem: Difference between revisions

Page Discussion

Subset sum problem (view source)

Revision as of 17:28, 28 August 2022

1,541 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 95:
{{trans|Python}}
 
<langsyntaxhighlight 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</langsyntaxhighlight>
 
{{out}}
Line 148:
 
=={{header|Action!}}==
<langsyntaxhighlight Actionlang="action!">DEFINE PTR="CARD"
DEFINE PAIR_SIZE="4"
 
Line 260:
Test(10)
Test(27)
RETURN</langsyntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Subset_sum_problem.png Screenshot from Atari 8-bit computer]
Line 278:
 
=={{header|Ada}}==
<langsyntaxhighlight Adalang="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 loop;
end SubsetSum;</langsyntaxhighlight>
{{out}}
<pre>2: archbishop gestapo
Line 363:
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 427:
subsum(0, 0);
return 0;
}</langsyntaxhighlight>
 
{{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#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
 
Line 515:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
Line 531:
=={{header|C++}}==
{{trans|C#}}
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <vector>
 
Line 598:
subsum(0, 0);
return 0;
}</langsyntaxhighlight>
{{out}}
<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.
{{trans|Ruby}}
<langsyntaxhighlight lang="d">void main() {
import std.stdio, std.algorithm, std.typecons, combinations3;
 
Line 632:
comb.map!q{ a[0] });
"No solution found.".writeln;
}</langsyntaxhighlight>
{{out}}
<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.
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm;
 
enum showAllSolutions = true;
Line 735:
 
writeln("Zero sums: ", sols);
}</langsyntaxhighlight>
{{out}}
<pre>Zero sums: 349167</pre>
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.
<langsyntaxhighlight 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>
{{out}}
<pre>
Line 845:
===Brute force===
We use the '''powerset''' procrastinator which gives in sequence all subsets of the input list.
<langsyntaxhighlight lang="scheme">
(lib 'sequences) ;; for powerset
 
Line 872:
("deploy" . 44) ("diophantine" . 645) ("efferent" . 54)
("elysee" . -326) ("eradicate" . 376))
</syntaxhighlight>
</lang>
 
=={{header|FunL}}==
<langsyntaxhighlight 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() )</langsyntaxhighlight>
 
{{out}}
Line 933:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 999:
}
fmt.Println("no subset sums to 0")
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,015:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations _ [] = []
Line 1,046:
W "vein" 813]
 
main = print $ map word $ head $ solver items</langsyntaxhighlight>
{{out}}
<pre>["archbishop","gestapo"]</pre>
 
Non brute-force: the list of numbers used here are different, and difficult for a bruteforce method.
<langsyntaxhighlight 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</langsyntaxhighlight>
{{out}}
<pre>[-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>
Line 1,079:
=={{header|Icon}} and {{header|Unicon}}==
{{trans|Ruby}}
<langsyntaxhighlight Iconlang="icon">link printf,lists
 
procedure main()
Line 1,124:
 
return T
end</langsyntaxhighlight>
 
{{libheader|Icon Programming Library}}
Line 1,166:
Task data:
 
<langsyntaxhighlight Jlang="j">text=:0 :0
alliance -624
archbishop -915
Line 1,201:
 
words=:{.@;:;._2 text
numbs=:+/|:0&".;._2 text</langsyntaxhighlight>
 
Implementation:
 
<langsyntaxhighlight Jlang="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
)</langsyntaxhighlight>
 
Task example:
 
<langsyntaxhighlight Jlang="j"> words wsum0 numbs
centipede markham mycenae</langsyntaxhighlight>
 
Note also that there are over 300,000 valid solutions here. More than can be comfortably displayed:
 
<langsyntaxhighlight Jlang="j"> Ps=: </.~ /:~ (I.P e. N){P
Ns=: </.~ /:~ (I.N e. P){N
+/#@,@{"1 Ps,.Ns
349168</langsyntaxhighlight>
 
(One of those is the empty solution, but the rest of them are valid.)
Line 1,232:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">public class SubsetSum {
private static class Item {
private String word;
Line 1,309:
zeroSum(0, 0);
}
}</langsyntaxhighlight>
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
Line 1,326:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq''' (provided `keys_unsorted` is replaced by `keys`)
<syntaxhighlight lang="jq">
<lang jq>
# 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'''
<langsyntaxhighlight lang="jq">def weights:
{
"alliance": -624,
Line 1,381:
};
 
weights | first(zero_sums)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,398:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Combinatorics
 
const pairs = [
Line 1,428:
 
zerosums()
</langsyntaxhighlight>{{out}}
<pre>
For length 1: None
Line 1,467:
=={{header|Kotlin}}==
{{trans|C}}
<langsyntaxhighlight 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)
}</langsyntaxhighlight>
 
{{out}}
Line 1,548:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="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 ]</langsyntaxhighlight>
 
<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.
 
<langsyntaxhighlight Mathematicalang="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}}==
<syntaxhighlight lang="minizinc">
<lang 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>
{{out}}
<pre>
Line 1,637:
</pre>
=={{header|Modula-2}}==
<langsyntaxhighlight lang="modula2">MODULE SubsetSum;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,738:
 
ReadChar;
END SubsetSum.</langsyntaxhighlight>
 
=={{header|Nim}}==
{{libheader|itertools}}
We need the third party module "itertools" to compute the combinations.
<langsyntaxhighlight Nimlang="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."</langsyntaxhighlight>
 
{{out}}
Line 1,831:
Just search randomly until a result is found:
 
<langsyntaxhighlight 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</langsyntaxhighlight>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/:all/;
 
my %pairs = (
Line 1,889:
lastfor, print "Length $n: @names[@_]\n" if vecsum(@weights[@_]) == 0;
} @names, $n;
}</langsyntaxhighlight>
Printing just the first one found for each number of elements:
{{out}}
Line 1,905:
 
We can also use different modules for this brute force method. Assuming the same pairs/names/weights variables:
<langsyntaxhighlight lang="perl">use List::Util qw/sum/;
use Algorithm::Combinatorics qw/combinations/;
foreach my $n (1 .. @names) {
Line 1,914:
last;
}
}</langsyntaxhighlight>
 
=={{header|Phix}}==
Simple Brute force
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">words</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({{</span><span style="color: #008000;">"alliance"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">624</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"archbishop"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">915</span><span style="color: #0000FF;">},</span>
Line 1,957:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<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.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">373</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">311</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">249</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">311</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">185</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">433</span><span style="color: #0000FF;">,</span>
Line 2,031:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 2,040:
Using constraint modelling.
 
<langsyntaxhighlight Picatlang="picat">import cp.
 
%
Line 2,109:
[speakeasy, -745],
[vein, 813 ]
].</langsyntaxhighlight>
 
{{out}}
Line 2,120:
 
Get a solution - if possible - for a specific number of selected things.
<langsyntaxhighlight Picatlang="picat">go2 =>
things(Things),
foreach(Len in 1..Things.length)
Line 2,131:
nl
end,
nl.</langsyntaxhighlight>
 
{{out}}
Line 2,223:
 
There are in total 349167 solutions of any number of items (the empty set is not a solution in our book).
<langsyntaxhighlight Picatlang="picat">go3 =>
things(Things),
Count = count_all(subset_sum(Things, _X, _Z)),
println(count=Count),
nl.
</syntaxhighlight>
</lang>
 
 
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="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) )</langsyntaxhighlight>
Minimal brute force solution:
<langsyntaxhighlight PicoLisplang="picolisp">(load "@lib/simul.l") # For 'subsets'
 
(pick
Line 2,249:
(find '((L) (=0 (sum cdr L)))
(subsets N *Words) ) )
(range 1 (length *Words)) )</langsyntaxhighlight>
{{Out}}
<pre>-> ((archbishop . -915) (gestapo . 915))</pre>
Line 2,255:
=={{header|Python}}==
===Version 1===
<langsyntaxhighlight 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</langsyntaxhighlight>
{{out}}<pre>
('mycenae', 183)
Line 2,300:
</pre>
===Brute force===
<langsyntaxhighlight lang="python">>>> from itertools import combinations
>>>
>>> word2weight = {"alliance": -624, "archbishop": -915, "balm": 397, "bonnet": 452,
Line 2,320:
>>> answer
[('archbishop', -915), ('gestapo', 915)]</langsyntaxhighlight>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
 
Line 2,358:
(for ([i (sub1 len)]) (loop l len (add1 i) '() 0)))
(zero-subsets words)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,371:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>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)" }
}
}</langsyntaxhighlight>
{{out}}
<pre>Length 1: (none)
Line 2,428:
Added was "que pasa" informational messages. &nbsp; The sum &nbsp; (which is zero for this task) &nbsp; can be any number,
<br>and can be specifiable on the command line.
<langsyntaxhighlight 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</langsyntaxhighlight>
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.
Line 2,583:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Subset sum problem
 
Line 2,664:
next
return alist
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,677:
=={{header|Ruby}}==
a brute force solution:
<langsyntaxhighlight 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</langsyntaxhighlight>
 
{{out}}
Line 2,737:
=={{header|Scala}}==
{{Out}}Best seen running in your browser by [https://scastie.scala-lang.org/KnhJimmSTL6QXIGTAdZjBQ Scastie (remote JVM)].
<langsyntaxhighlight Scalalang="scala">object SubsetSum extends App {
private val LIMIT = 5
private val n = items.length
Line 2,799:
zeroSum(0, 0)
 
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">var pairs = Hash(
alliance => -624, archbishop => -915,
brute => 870, centipede => -658,
Line 2,834:
})
found || say "Length #{n}: (none)"
}</langsyntaxhighlight>
{{out}}
<pre style="height: 40ex; overflow: scroll">
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.
<langsyntaxhighlight lang="tcl">proc subsetsOfSize {set size} {
if {$size <= 0} {
return
Line 2,896:
# Nothing was found
return -code error "no subset sums to zero"
}</langsyntaxhighlight>
Demonstrating:
<langsyntaxhighlight lang="tcl">set wordweights {
alliance -624
archbishop -915
Line 2,932:
}
set zsss [searchForSubset $wordweights]
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</langsyntaxhighlight>
{{Out}}
<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.
<langsyntaxhighlight Ursalalang="ursala">#import std
#import int
 
Line 2,982:
#cast %zm
 
main = nullset weights</langsyntaxhighlight>
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}}==
{{trans|Kotlin}}
<langsyntaxhighlight 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)</langsyntaxhighlight>
 
{{out}}
Line 3,204:
=={{header|zkl}}==
{{trans|C}}
<langsyntaxhighlight 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){}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328515"