Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #51014

Rosetta Code: Subset sum problem

Show all headers | View raw

> Subset sum problem is a draft programming task.

> Implement a function/procedure/method/subroutine that takes a
> set/array/list/stream/table/collection of words with integer
> weights, and identifies a non-empty subset of them whose
> weights sum to zero


Ruby:

words = %w(
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).each_slice(2).map{|a,b| [a,b.to_i]}

def total(ary); ary.map(&:last).reduce(:+); end

(2 .. words.size).each{|i|
  print i, ": "
  found = words.combination(i).find{|ary| 0 == total(ary)}
  print found.map(&:first).join(" ") if found
  puts
}

2: archbishop gestapo
3: centipede markham mycenae
4: alliance balm deploy mycenae
5: alliance brute covariate deploy mincemeat
6: alliance archbishop balm deploy gestapo mycenae
7: alliance archbishop bonnet cobol departure exorcism moresby
8: alliance archbishop balm bonnet fiat flatworm isis lindholm
9: alliance archbishop balm bonnet brute covariate eradicate mincemeat plugging
10: alliance archbishop balm bonnet brute centipede cobol departure deploy
 mincemeat
11: alliance archbishop balm bonnet brute centipede cobol departure infra
 moresby speakeasy
12: alliance archbishop balm bonnet brute centipede cobol covariate
 diophantine efferent elysee infra
13: alliance archbishop balm bonnet brute centipede cobol covariate departure
 efferent eradicate filmy isis
14: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy elysee filmy markham speakeasy
15: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy elysee exorcism flatworm infra mycenae
16: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine elysee exorcism filmy gestapo infra
17: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine exorcism isis mincemeat mycenae plugging vein
18: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee exorcism filmy isis mycenae vein
19: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee eradicate exorcism fiat infra isis
 smokescreen
20: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee eradicate exorcism gestapo infra isis
 smokescreen speakeasy
21: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee eradicate exorcism flatworm infra lindholm
 mincemeat plugging speakeasy
22: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy
 flatworm mincemeat plugging speakeasy
23: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee eradicate escritoire exorcism infra isis
 mincemeat moresby mycenae smokescreen speakeasy
24: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine efferent elysee exorcism filmy gestapo infra markham
 mincemeat moresby mycenae plugging smokescreen speakeasy
25: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine eradicate exorcism fiat filmy flatworm infra isis lindholm
 markham mincemeat moresby mycenae plugging speakeasy
26: alliance archbishop balm bonnet brute centipede cobol covariate departure
 deploy diophantine elysee eradicate escritoire exorcism fiat filmy gestapo
 infra isis markham mincemeat mycenae plugging speakeasy vein
27: alliance archbishop balm bonnet brute centipede covariate departure deploy
 efferent elysee eradicate escritoire exorcism fiat filmy flatworm infra isis
 lindholm markham mincemeat moresby mycenae plugging smokescreen speakeasy
28:
29:
30:
31:

In Forth?


-- 
[H]e was prosecuted ... for "denying" the gas chambers and the six million
figure....  [A] Swiss court sentenced him to 15 months imprisonment....  Rather
than serve the sentence, ... Graf went into exile.  In 2001 he married a
Russian historian in Moscow.  www.revisionists.com/revisionists/graf.html

Back to comp.lang.forth | Previous | Next | Find similar | Unroll thread

Thread

Rosetta Code: Subset sum problem "WJ" <w_a_x_man@yahoo.com> - 2016-09-16 00:25 +0000

csiph-web