Subset sum problem: Difference between revisions
→{{header|Picat}}
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
|||
Line 2,036:
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|Picat}}==
Using constraint modelling.
<lang Picat>import cp.
%
% Get any solution.
%
go =>
things(Things),
subset_sum(Things, X, Z),
println(z=Z),
println(x=X),
println([Things[I] : I in 1..Things.length, X[I] == 1]),
nl.
%
% Solve subset problem for any length (wrapper).
%
subset_sum(Things, X, Z) =>
subset_sum(Things,_,X,Z).
%
% Solve for a specific length (if Len2 is nonvar).
%
subset_sum(Things, Len2, X, Z) =>
Weights = [ T[2] : T in Things],
Len = Things.length,
X = new_list(Len),
X :: 0..1,
Z #= sum(X),
if nonvar(Len2) then
Z #= Len2
end,
Z #> 0, % require at least one thing
sum([X[I] * Weights[I] : I in 1..Len]) #= 0,
solve($[ff], X).
things(Things) =>
Things = [
[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],
[escritoire, 856],
[exorcism, -983],
[fiat, 170],
[filmy, -874],
[flatworm, 503],
[gestapo, 915],
[infra, -847],
[isis, -982],
[lindholm, 999],
[markham, 475],
[mincemeat, -880],
[moresby, 756],
[mycenae, 183],
[plugging, -266],
[smokescreen, 423],
[speakeasy, -745],
[vein, 813 ]
].</lang>
{{out}}
<pre>z = 8
x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1,1,1,1]
[[flatworm,503],[infra,-847],[lindholm,999],[mincemeat,-880],[plugging,-266],[smokescreen,423],[speakeasy,-745],[vein,813]]
</pre>
Some other experiments.
Get a solution - if possible - for a specific number of selected things.
<lang Picat>go2 =>
things(Things),
foreach(Len in 1..Things.length)
println(len=Len),
(subset_sum(Things, Len, X, _Z) ->
println([Things[I,1] : I in 1..Things.length, X[I] == 1])
;
true
),
nl
end,
nl.</lang>
{{out}}
<pre>len = 1
len = 2
[archbishop,gestapo]
len = 3
[exorcism,fiat,vein]
len = 4
[exorcism,gestapo,speakeasy,vein]
len = 5
[fiat,infra,lindholm,smokescreen,speakeasy]
len = 6
[exorcism,flatworm,gestapo,isis,plugging,vein]
len = 7
[fiat,flatworm,infra,isis,lindholm,plugging,smokescreen]
len = 8
[flatworm,infra,lindholm,mincemeat,plugging,smokescreen,speakeasy,vein]
len = 9
[exorcism,filmy,flatworm,infra,markham,moresby,plugging,smokescreen,vein]
len = 10
[fiat,filmy,flatworm,gestapo,isis,markham,mincemeat,moresby,mycenae,plugging]
len = 11
[exorcism,fiat,flatworm,gestapo,infra,isis,lindholm,plugging,smokescreen,speakeasy,vein]
len = 12
[eradicate,fiat,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 13
[escritoire,fiat,filmy,gestapo,infra,isis,lindholm,markham,mincemeat,moresby,plugging,smokescreen,speakeasy]
len = 14
[escritoire,exorcism,fiat,flatworm,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 15
[efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,moresby,mycenae,smokescreen,speakeasy,vein]
len = 16
[diophantine,elysee,eradicate,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,moresby,mycenae,plugging,speakeasy,vein]
len = 17
[deploy,diophantine,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,moresby,speakeasy,vein]
len = 18
[deploy,diophantine,efferent,escritoire,exorcism,fiat,filmy,gestapo,infra,isis,lindholm,markham,mincemeat,mycenae,plugging,smokescreen,speakeasy,vein]
len = 19
[departure,deploy,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,mycenae,smokescreen,speakeasy,vein]
len = 20
[covariate,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 21
[cobol,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,mycenae,plugging,smokescreen,speakeasy,vein]
len = 22
[brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,markham,mincemeat,moresby,plugging,smokescreen,speakeasy,vein]
len = 23
[bonnet,centipede,cobol,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 24
[archbishop,brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,markham,mincemeat,moresby,plugging,smokescreen,speakeasy,vein]
len = 25
[archbishop,bonnet,centipede,cobol,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,gestapo,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 26
[alliance,archbishop,bonnet,brute,centipede,covariate,departure,deploy,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 27
[alliance,archbishop,balm,brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 28
len = 29
len = 30
len = 31</pre>
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.
</lang>
=={{header|PicoLisp}}==
| |||