Rosetta Code

Subset sum problem: Difference between revisions

Page Discussion

Subset sum problem (view source)

Revision as of 19:50, 6 November 2020

231 bytes removed ,  3 years ago
m
→‎{{header|REXX}}: added/changed comments and whitespace, re-arranged the list of words for a smaller footprint within the program.
(Added Wren)
m (→‎{{header|REXX}}: added/changed comments and whitespace, re-arranged the list of words for a smaller footprint within the program.)
Line 1,902:
if target=='' | target=="," then target= 0 /*Not specified? Then use the default.*/
if stopAt=='' | stopAt=="," then stopAt= 1 /* " " " " " " */
y= 0
zzzzz= 'alliance -624 archbishop -915 covariate 590 mycenae 183 brute 870 balm balm 397 fiat 397170' ,
'bonnetsmokescreen 423 eradicate 452376 efferent 54 bonnet 452 vein brute 813 870 centipede -658' ,
'coboldiophantine 645 departure 952 362 lindholm 999 moresby 756 isis -982 covariate 590 departure 952' ,
'deploymincemeat -880 alliance 44-624 flatworm 503 elysee -326 cobol 362 diophantine 645 efferent 54' ,
'elysee centipede -326658 exorcism -983 gestapo 915 filmy eradicate-874 deploy 37644 escritoire 856' ,
'exorcismspeakeasy -983745 plugging -266 markham 475 infra fiat-847 escritoire 856 170 filmy -874' ,
@.= 0▼
'flatworm 503 gestapo 915 infra -847' ,
'isis -982 do N=1 until zz='' lindholm 999 /*construct an array from the ZZ list. markham 475' ,*/
'mincemeat -880 parse var zz moresby @.N #.N 756zz /*pick from the list like a nose. 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. */
Line 1,931 ⟶ 1,926:
call tello center(' doing chunk:' chunk" ", 79, '─')
call combN N, chunk /*N items, a CHUNK at a time. */
_= ??; if _==0 then _= 'No' /*Englishise forset a zero count.temporary variable to ??. */
if _==0 then _= 'No' /*Englishise _ for a zero count. */
call tello _ 'solution's(??) "found so far."
end /*chunk*/
Line 1,940 ⟶ 1,936:
/*──────────────────────────────────────────────────────────────────────────────────────*/
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.= @.0
base= x + 1; bbase= base - y /*!.n are the combination digits. */
do n=1 for y; !.n=n /*construct the first combination. */
end /*n*/
ym= y - 1
do j=1; _= !.1; s= #._ /*obtain the first digit and the sum. */
if s>target then leave /*Is 1st dig>target? Then we're done.*/
do k=2 for ym; _= !.k; s= s + #._ /*Σ the weights; is sum > target ? */
Line 1,950 ⟶ 1,946:
end /*k*/
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.*/
end /*j*/; return /*done with this combination set. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
.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 one to digit we're pointing at. */
if !.u >= bbase+u then return .combUp(u-1)
p= !.u /*P will be used for the next digt. */
end /*u*/; return 0 /*go back and sum this combination. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
eSort: procedure expose #. @. $.; parse arg N,$; h= N
do while h>1; h= h % 2
do i=1 for N-h; j= i; k= h + i
if $==. then do while $.k<$.j; parse value $.j $.k with $.k $.j
if h>=j then leave; j= j - h; k= k - h
end /*while $.k<$.j*/
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
end /*while #.k<#.j*/
end /*i*/
end /*while h>1*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
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
/*──────────────────────────────────────────────────────────────────────────────────────*/
telly: ??= ?? + 1; nameL= /*start with a "null" name list. */
do gi=1 for y; ggg= !.gi /*build duplicate array (to be sorted).*/
$.gi= @.ggg /*transform from index ──► a name. */
end /*gi*/ /*build duplicate array (to be sorted).*/
call eSort y, . /*sort the names alphabetically. */
do gs=1 for y; nameL= nameL $.gs /*build a list of names whose sum = 0 */
Line 1,991 ⟶ 1,987:
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
<br> ──────── where &nbsp; nnn &nbsp; is the ''chunk'' number.
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210673"