Subset sum problem: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: optimized the combN subroutine a small bit. -- ~~~~) |
m (→{{header|REXX}}: made the compN subroutine faster. -- ~~~~) |
||
| Line 543: | Line 543: | ||
<br>This is a brute force solution. |
<br>This is a brute force solution. |
||
<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=0. */ |
<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=0. */ |
||
| ⚫ | |||
| ⚫ | |||
if target=='' then target=0 /*No TARGET given? Use default.*/ |
if target=='' then target=0 /*No TARGET given? Use default.*/ |
||
if |
if stopAt=='' then stopAt=1 /*No max sols given? Use default.*/ |
||
zzz= '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' |
|||
@.=0; y=0; |
@.=0; y=0; do N=1 until zzz=''; parse var zzz @.N #.N zzz |
||
call tell right('['N']',30) right(@.N,11) right(#.N,5) |
|||
end /*N*/ |
|||
solutions=0 |
|||
end /*size*/; @.0=target |
|||
call tell; call tell 'There are' N "entries in the table." |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
end /*chunk*/ |
end /*chunk*/ |
||
if |
if solutions==0 then solutions='no' |
||
call |
call tell 'Found' solutions "subsets whose summed weights =" target |
||
exit |
exit |
||
/*─────────────────────────────────────telly subroutine─────────────────*/ |
|||
/*─────────────────────────────────────tell subroutine──────────────────*/ |
|||
telly: |
telly: solutions=solutions+1; names= |
||
do |
do g=1 for y; o=!.g |
||
names=names |
names=names @.o |
||
/* names=names |
/* names=names @.o '{'#.o"}" <─── weights in this REXX statement.*/ |
||
end /* |
end /*g*/ |
||
call |
call tell '['y" names]" space(names) |
||
if |
if solutions>=stopAt &, |
||
stopAt\==0 then do |
|||
call |
call tell 'Stopped after finding' solutions "subsets." |
||
exit |
exit |
||
end |
end |
||
return |
return |
||
tell: say arg(1); call lineout 'SUBSET.'y,arg(1) /*write to file*/; return |
|||
/*─────────────────────────────────────combN subroutine─────────────────*/ |
/*─────────────────────────────────────combN subroutine─────────────────*/ |
||
combN: procedure expose @.; |
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*/ |
do j=1; L=!.d; do d=2 for ym; L=L !.d; end /*d*/ |
||
_=!.1; s= |
_=!.1; s=#._ |
||
do k=2 for |
do k=2 for y-1; _=!.k; s=s+#._; end /*sum the weights.*/ |
||
if s== |
if s==target then call telly |
||
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave |
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave |
||
end |
end |
||
| Line 603: | Line 605: | ||
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1 |
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1 |
||
p=!.d; do u=d to y; !.u=p+1 |
p=!.d; do u=d to y; !.u=p+1 |
||
if !.u>=bbase+u then return .combUp(u-1) |
if !.u>=bbase+u then return .combUp(u-1) |
||
p=!.u |
p=!.u |
||