Subset sum problem: Difference between revisions

Content added Content deleted
(→‎version 1: optimized part of the combN subroutine for faster execution. -- ~~~~)
(→‎version 2: optimized the previous version, it's faster by a facter of four or so. -- ~~~~)
Line 813: Line 813:
===version 2===
===version 2===
This version requires the data to be in ascending order (by weight).
This version requires the data to be in ascending order (by weight).
Code could've been included to sort the table, but the extra code would've made the
<br>Code could've been included to sort the table, but the extra code would've made the
program more bulkier, so the list was just sorted externally.
program more bulkier, so the list was just sorted externally.
It's about three times faster than version 1 (above) because it takes advantage of short-circuiting the
<br>It's quite a bit faster because it takes advantage of short-circuiting the summing process,
summing process. This version is still a brute-force method, though maybe less so than version 1.
<br>and is an order of magnitude faster than the brute-force method (version 1).
<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.*/
arg target stopAt . /*get arguments from command line*/
arg target stopAt . /*get arguments from command line*/
if target=='' then target=0 /*No TARGET given? Use default.*/
if target=='' then target=0 /*No TARGET given? Use default.*/
Line 855: Line 855:


@.=0; y=0; do N=1 until zzz=''; parse var zzz @.N #.N zzz
@.=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)
call tello right('['N']',30) right(@.N,11) right(#.N,5)
end /*N*/
end /*N*/
solutions=0
solutions=0
call t; call t 'There are' N "entries in the table."
call tello 'There are' N "entries in the table."


do chunk=1 for N
do chunk=1 for N
call combN N,chunk
call combN N,chunk
end /*chunk*/
end /*chunk*/


if solutions==0 then solutions='no'
if solutions==0 then solutions='no'
call t 'Found' solutions "subsets whose summed weights =" target
call tello 'Found' solutions "subsets whose summed weights =" target
exit
exit
/*─────────────────────────────────────telly subroutine─────────────────*/
/*─────────────────────────────────────telly subroutine─────────────────*/
Line 875: Line 875:
end /*g*/
end /*g*/


call t '['y" names]" space(names)
call tello '['y" names]" space(names)
if solutions>=stopAt &,
if solutions>=stopAt &,
stopAt\==0 then do
stopAt\==0 then do
call t 'Stopped after finding' solutions "subsets."
call tello 'Stopped after finding' solutions "subsets."
exit
exit
end
end
return
return


t: say arg(1); call lineout 'SUBSET.'y,arg(1) /*write to file*/; return
tello: say arg(1); call lineout 'SUBSET.'y,arg(1) /*write to file*/; return
/*─────────────────────────────────────combN subroutine─────────────────*/
/*─────────────────────────────────────combN subroutine─────────────────*/
combN: procedure expose @. #. solutions stopAt target; parse arg x,y; !.=0
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*/
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 n=1 for y; !.n=n; end /*build 1st combination*/


do j=1
do j=1; L=!.d; do d=2 for ym; L=L !.d; end /*d*/
_=!.1; s=#._
_=!.1; s=#._; if s>target then leave
⚫
do k=2 for ym 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


⚫
do k=2 for ym; _=!.k; s=s+#._; /*Σ weights; >target? */
if s>target then do; if .combUp(k-1) then return; iterate j; end
end /*k*/

⚫
if s==target then call telly /*found a pot of gold? */
⚫
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave /*bump dig*/
end /*j*/
return
return


Retrieved from "https://rosettacode.org/wiki/Subset_sum_problem"