Subset sum problem: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: added/changed comments and whitespace, used a template for the outputs.)
Line 1,482: Line 1,482:
=={{header|REXX}}==
=={{header|REXX}}==
This REXX solution isn't limited to integers for the weights.     This isn't a brute force solution.
This REXX solution isn't limited to integers for the weights.     This isn't a brute force solution.

<br><br>While optimizing the original program, it was found that sorting the names by weight could yield a vastly
While optimizing the original program, it was found that sorting the names by weight could yield a vastly
<br>improved algorithm (by an order of magnitude), so the extra code to sort the list was included, as well as
<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
<br>another sort to show the solutions in alphabetical order. &nbsp; Support was also added to allow specification of
<br>which "chunk" to search for solutions (that is, out of the 31 names, take a "chunk" at a time).
<br>which "chunk" to search for solutions &nbsp; (that is, out of the 31 names, take a "chunk" at a time).
<br><br>Showing of the timing (elapsed time) was also added, as well as "que pasa" informational messages. &nbsp; The
<br>sum &nbsp; (which is zero for this task) can be any number, and can be specifiable on the command line.
<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=zero*/
parse arg target stopAt chunkette . /*get args from the command line*/
if target==''|target==',' then target=0 /*TARGET given? No, use default*/
if stopAt==''|stopAt==',' then stopAt=1 /*Max solutions? " " " */


Showing of the timing (elapsed time) was also added, as well as "que pasa" informational messages. &nbsp; The
zzz = 'alliance -624 archbishop -915 balm 397' ,
<br>sum &nbsp; (which is zero for this task) &nbsp; can be any number, and can be specifiable on the command line.
'bonnet 452 brute 870 centipede -658' ,
<lang rexx>/*REXX program finds some non─null subsets of a weighted list whose sum eqals zero.*/
'cobol 362 covariate 590 departure 952' ,
parse arg target stopAt chunkette . /*option optional arguments from the CL*/
'deploy 44 diophantine 645 efferent 54' ,
if target=='' | target=="," then target=0 /*Not specified? Then use the default.*/
'elysee -326 eradicate 376 escritoire 856' ,
'exorcism -983 fiat 170 filmy -874' ,
if stopAt=='' | stopAt=="," then stopAt=1 /* " " " " " " */
y=0
'flatworm 503 gestapo 915 infra -847' ,
'isis -982 lindholm 999 markham 475' ,
zzz= 'alliance -624 archbishop -915 balm 397' ,
'mincemeat -880 moresby 756 mycenae 183' ,
'bonnet 452 brute 870 centipede -658' ,
'plugging -266 smokescreen 423 speakeasy -745' ,
'cobol 362 covariate 590 departure 952' ,
'deploy 44 diophantine 645 efferent 54' ,
'vein 813'
'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'
@.=0
do N=1 until zzz='' /*construct an array from the ZZZ list.*/
parse var zzz @.N #.N zzz /*pick from the list like a nose. */
end /*N*/
call eSort N /*sort the names with weights. */
call tellZ 'sorted' /*display the sorted list. */
chunkStart=1 /*the default place to start. */
chunkEnd =N /* " " " " end. */
if chunkette\=='' then do /*solutions just for a chunkette. */
chunkStart= chunkette
chunkEnd = chunkette
end
call time 'Reset' /*reset the REXX elapsed time. */
??=0 /*the number of solutions (so far). */
do chunk=chunkStart to chunkEnd /*traipse through the items. */
call tello center(' doing chunk:' chunk" ", 79, '─')
call combN N, chunk /*N items, a CHUNK at a time. */
_=??; if _==0 then _= 'No' /*Englishise for a zero count. */
call tello _ 'solution's(??) "found so far and took",
format( time('Elapsed'), , 2) "seconds so far.", .
end /*chunk*/


@.=0; y=0; do N=1 until zzz='' /*build an array from a list. */
if ??==0 then ??= 'no' /*Englishise the solutions number. */
parse var zzz @.N #.N zzz /*pick from list like a nose. */
call tello 'Found' ?? "subset"s(??) 'whose summed weight's(??) "=" target
end /*N*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
call esort N /*sort the names with weights.*/
call tellZ 'sorted' /*show the sorted list. */
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.=0
chunkStart=1 /*the default place to start. */
base= x+1; bbase= base-y /*!.n are the combination digits. */
chunkEnd =N /* " " " " end. */
do n=1 for y; !.n=n /*construct the first combination. */
if chunkette\=='' then do /*solutions just for chunkette*/
end /*n*/
ym= y-1
chunkStart=chunkette
chunkEnd =chunkette
do j=1; _=!.1; s=#._ /*obtain the first digit and the sum. */
end
if s>target then leave /*Is 1st dig>target? Then we're done.*/
call time 'Reset' /*reset the REXX elapsed time.*/
do k=2 for ym; _=!.k; s=s + #._ /*Σ the weights; is sum > target ? */
??=0 /*number of solutions so far. */
if s>target then do; if .combUp(k-1) then return; iterate j; end
end /*k*/

do chunk=chunkStart to chunkEnd /*traipse through the items. */
if s==target then call telly /*have we found a pot of gold? */
!.y= !.y + 1; if !.y==base then if .combUp(ym) then leave /*bump digit.*/
call tello center(' doing chunk:' chunk" ",79,'─')
call combN N, chunk /*N items, a CHUNK at a time. */
end /*j*/
_=??; if _==0 then _='No' /*Englishise for a zero count.*/
return /*done with this combination set. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
call tello _ 'solution's(??) "found so far and took",
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1
format(time('Elapsed'),,2) 'seconds so far.',.
p=!.d; do u=d to y; !.u=p + 1 /*add one to digit we're pointing at. */
end /*chunk*/
if !.u >= bbase+u then return .combUp(u-1)

if ??==0 then ??='no' /*Englishise solutions number.*/
p=!.u /*P will be used for the next digt. */
end /*u*/
call tello 'Found' ?? "subset"s(??) 'whose summed weight's(??) "=" target
exit /*stick a fork in it, we done.*/
return 0 /*go back and sum this combination. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────COMBN subroutine────────────────────*/
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.=0
eSort: procedure expose #. @. $.; parse arg N,$; h=N
base=x+1; bbase=base-y; ym=y-1 /*!.n are the combination digits*/
do while h>1; h=h%2
do i=1 for N-h; j=i; k=h+i

do n=1 for y; !.n=n; end /*build the first combination. */
if $==. then do while $.k<$.j; parse value $.j $.k with $.k $.j
if h>=j then leave; j=j-h; k=k-h

do j=1; _=!.1; s=#._ /*get the first digit and the sum*/
end /*while $.k<$.j*/
if s>target then leave /*1st dig>target? Then we're done*/
else do while #.k<#.j; parse value @.j @.k #.j #.k with @.k @.j #.k #.j
if h>=j then leave; j=j-h; k=k-h

do k=2 for ym; _=!.k; s=s+#._ /*Σ the weights; is sum > target?*/
end /*while #.k<#.j*/
end /*i*/
if s>target then do; if .combUp(k-1) then return; iterate j; end
end /*k*/
end /*while h>1*/
return

/*──────────────────────────────────────────────────────────────────────────────────────*/
if s==target then call telly /*have we found a pot of gold? */
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave /*bump dig*/
s: if arg(1)==1 then return arg(3); return word(arg(2) 's',1) /*simple pluralizer*/
tello: parse arg _,e; if e==. then say; say _; call lineout 'SUBSET.'y, _; return
end /*j*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
return /*done with this combination set.*/
telly: ??=??+1; nameL= /*start with a "null" name list. */

do gi=1 for y; ggg= !.gi /*build duplicate array (to be sorted).*/
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1
p=!.d; do u=d to y; !.u=p+1 /*add 1 to dig we're pointing at.*/
$.gi= @.ggg /*transform from index ──► a name. */
end /*gi*/ /*build duplicate array (to be sorted).*/
if !.u>=bbase+u then return .combUp(u-1)
p=!.u /*P will be used for the next dig*/
call eSort y, . /*sort the names alphabetically. */
end /*u*/
do gs=1 for y; nameL=nameL $.gs /*build a list of names whose sum = 0 */
return 0 /*go back & sum this combination.*/
end /*gs*/ /*the list of names could be sorted. */
call tello '['y" name"s(y)']' space(nameL)
/*──────────────────────────────────ESORT subroutine────────────────────*/
if ??<stopAt | stopAt==0 then return /*see if we reached a (or the) limit.*/
esort: procedure expose #. @. $.; parse arg N,$; h=N
do while h>1; h=h%2
call tello 'Stopped after finding ' ?? " subset"s(??)'.', .
do i=1 for N-h; j=i; k=h+i
exit /*a short─timer, we should quit then. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
if $==. then do while $.k<$.j; parse value $.j $.k with $.k $.j
if h>=j then leave; j=j-h; k=k-h
tellz: do j=1 for N /*show a list of names and weights. */
end /*while $.k<$.j*/
call tello right('['j']', 30) right(@.j, 11) right(#.j, 5)
else do while #.k<#.j; parse value @.j @.k #.j #.k with @.k @.j #.k #.j
end /*j*/
call tello
if h>=j then leave; j=j-h; k=k-h
end /*while #.k<#.j*/
call tello 'There are ' N " entries in the (above)" arg(1) 'table.'
end /*i*/
call tello; return</lang>
end /*while h>1*/
return
/*──────────────────────────────────one─liner subroutines─────────────────────*/
s: if arg(1)==1 then return arg(3); return word(arg(2) 's',1) /*plural*/
tello: parse arg _,e; if e==. then say; say _; call lineout 'SUBSET.'y,_; return
/*──────────────────────────────────TELLY subroutine────────────────────*/
telly: ??=??+1; nameL= /*start with a "null" name list. */
do gi=1 for y; ggg=!.gi /*build dup array (to be sorted).*/
$.gi=@.ggg /*transform from index──► a name.*/
end /*gi*/ /*build dup array (to be sorted).*/
call eSort y,. /*sort the names alphabetically. */
do gs=1 for y; nameL=nameL $.gs /*build list of names whose sum=0*/
end /*gs*/ /*list of names could be sorted */
call tello '['y" name"s(y)']' space(nameL)
if ??<stopAt | stopAt==0 then return /*see if we reached a (the) limit*/
call tello 'Stopped after finding ' ?? " subset"s(??)'.',.
exit /*a short─timer, we have to quit.*/
/*──────────────────────────────────TELLZ subroutine────────────────────*/
tellz: do j=1 for N /*show list of names and weights.*/
call tello right('['j']',30) right(@.j,11) right(#.j,5)
end /*j*/
call tello
call tello 'There are ' N " entries in the (above)" arg(1) 'table.'
call tello; return</lang>
Output note: &nbsp; this program also writes the displayed output to file(s): &nbsp; SUBSET.nnn
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.
<br> ──────── where &nbsp; nnn &nbsp; is the ''chunk'' number.
<br>


{{Out}} when using the input of: &nbsp; <tt> 0 12 </tt><br>
{{out|output|text= &nbsp;when using the input of: &nbsp; &nbsp; <tt> 0 &nbsp; 12 </tt>}}

(The above arguments set the target sum to zero and limits finding of a dozen solutions.)
(The above arguments set the target sum to zero, and limits the finding of a dozen solutions.)
<pre style="height:90ex">
<pre style="height:90ex">
[1] exorcism -983
[1] exorcism -983
Retrieved from "https://rosettacode.org/wiki/Subset_sum_problem"