Subset sum problem: Difference between revisions

===version 1===

===version 2===

This version requires the data to be in ascending order (by weight).

<br>Code could've been included to sort the table, but the extra code would've made the

<br>program more bulkier, so the list was just sorted externally.

<br>It's faster than version 1 (above) because it takes advantage of short-circuiting the

<br>summing process.

<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=0. */

arg target stopAt . /*get arguments from command line*/

if target=='' then target=0 /*No TARGET given? Use default.*/

if stopAt=='' then stopAt=1 /*No max sols given? Use default.*/

zzz= 'exorcism -983',

'isis -982',

'archbishop -915',

'mincemeat -880',

'filmy -874',

'infra -847',

'speakeasy -745',

'centipede -658',

'alliance -624',

'elysee -326',

'plugging -266',

'deploy 44',

'efferent 54',

'fiat 170',

'mycenae 183',

'cobol 362',

'eradicate 376',

'balm 397',

'smokescreen 423',

'bonnet 452',

'markham 475',

'flatworm 503',

'covariate 590',

'diophantine 645',

'moresby 756',

'vein 813',

'escritoire 856',

'brute 870',

'gestapo 915',

'departure 952',

'lindholm 999' /*list must be in ascending order by weight.*/

@.=0; y=0; do N=1 until zzz=''; parse var zzz @.N #.N zzz

call t right('['N']',30) right(@.N,11) right(#.N,5)

end /*N*/

solutions=0

call t; call t 'There are' N "entries in the table."

do chunk=1 for N

call combN N,chunk

end /*chunk*/

if solutions==0 then solutions='no'

call t 'Found' solutions "subsets whose summed weights =" target

exit

/*─────────────────────────────────────telly subroutine─────────────────*/

telly: solutions=solutions+1; names=

do g=1 for y; o=!.g

names=names @.o

/* names=names @.o '{'#.o"}" <─── weights in this REXX statement.*/

end /*g*/

call t '['y" names]" space(names)

if solutions>=stopAt &,

stopAt\==0 then do

call t 'Stopped after finding' solutions "subsets."

exit

end

return

t: say arg(1); call lineout 'SUBSET.'y,arg(1) /*write to file*/; return

/*─────────────────────────────────────combN subroutine─────────────────*/

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

base=x+1; bbase=base-y; ym=y-1 /*!.n are the combination digits*/

do n=1 for y; !.n=n; end /*build 1st combination*/

do j=1; L=!.d; do d=2 for ym; L=L !.d; end /*d*/

_=!.1; s=#._

do k=2 for y-1 until s>target; _=!.k; s=s+#._; end /*sum weights.*/

if s==target then call telly

!.y=!.y+1; if !.y==base then if .combUp(ym) then leave

end

return

.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1

p=!.d; do u=d to y; !.u=p+1

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

p=!.u

end

return 0</lang>