Subset sum problem: Difference between revisions

=={{header|Julia}}==

<lang julia>using Combinatorics

const pairs = [

"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]

const weights = [v for (k, v) in pairs]

const weightkeyed = Dict(Pair(v, k) for (k, v) in pairs)

function zerosums()

for i in 1:length(weights)

print("\nFor length $i: ")

sets = [a for a in combinations(weights, i) if sum(a) == 0]

if (n = length(sets)) == 0

print("None")

else

print("$n sets, example: ", map(x -> weightkeyed[x], rand(sets)))

end

end

end

zerosums()

</lang>{{out}}

<pre>

For length 1: None

For length 2: 1 sets, example: ["archbishop", "gestapo"]

For length 3: 2 sets, example: ["centipede", "markham", "mycenae"]

For length 4: 9 sets, example: ["balm", "efferent", "filmy", "smokescreen"]

For length 5: 48 sets, example: ["departure", "elysee", "lindholm", "mincemeat", "speakeasy"]

For length 6: 178 sets, example: ["alliance", "bonnet", "centipede", "isis", "lindholm", "vein"]

For length 7: 629 sets, example: ["balm", "brute", "cobol", "deploy", "filmy", "isis", "mycenae"]

For length 8: 1634 sets, example: ["alliance", "brute", "centipede", "departure", "mincemeat", "mycenae", "plugging", "smokescreen"]

For length 9: 4040 sets, example: ["alliance", "brute", "deploy", "efferent", "elysee", "fiat", "filmy", "flatworm", "mycenae"]

For length 10: 8673 sets, example: ["archbishop", "brute", "escritoire", "filmy", "gestapo", "isis", "lindholm", "mincemeat", "moresby", "speakeasy"]

For length 11: 15680 sets, example: ["cobol", "covariate", "deploy", "efferent", "elysee", "eradicate", "exorcism", "filmy", "flatworm", "lindholm", "speakeasy"]

For length 12: 25492 sets, example: ["alliance", "balm", "diophantine", "efferent", "eradicate", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "mycenae"]

For length 13: 35940 sets, example: ["alliance", "archbishop", "bonnet", "departure", "deploy", "efferent", "fiat", "filmy", "gestapo", "infra", "moresby", "mycenae", "plugging"]

For length 14: 44920 sets, example: ["archbishop", "centipede", "cobol", "covariate", "deploy", "efferent", "eradicate", "escritoire", "fiat", "gestapo", "isis", "mincemeat", "speakeasy", "vein"]

For length 15: 49368 sets, example: ["alliance", "archbishop", "bonnet", "covariate", "departure", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "isis", "mincemeat", "plugging", "speakeasy", "vein"]

For length 16: 47835 sets, example: ["alliance", "archbishop", "balm", "bonnet", "centipede", "cobol", "covariate", "departure", "elysee", "flatworm", "infra", "isis", "moresby", "mycenae", "plugging", "smokescreen"]

For length 17: 40960 sets, example: ["balm", "bonnet", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "fiat", "filmy", "isis", "mincemeat", "smokescreen", "speakeasy"]

For length 18: 31139 sets, example: ["balm", "bonnet", "centipede", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "gestapo", "infra", "isis", "mincemeat", "mycenae", "speakeasy", "vein"]

For length 19: 20530 sets, example: ["alliance", "archbishop", "balm", "bonnet", "departure", "deploy", "elysee", "exorcism", "fiat", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "plugging", "smokescreen", "vein"]

For length 20: 11926 sets, example: ["archbishop", "bonnet", "brute", "centipede", "cobol", "deploy", "diophantine", "elysee", "eradicate", "exorcism", "fiat", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"]

For length 21: 6089 sets, example: ["alliance", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "escritoire", "exorcism", "filmy", "flatworm", "infra", "isis", "markham", "mincemeat", "moresby", "mycenae", "plugging"]

For length 22: 2688 sets, example: ["archbishop", "balm", "bonnet", "brute", "centipede", "covariate", "deploy", "diophantine", "elysee", "eradicate", "exorcism", "filmy", "flatworm", "gestapo", "isis", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"]

For length 23: 956 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "departure", "deploy", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "plugging", "speakeasy"]

For length 24: 341 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "plugging", "smokescreen", "speakeasy"]

For length 25: 73 sets, example: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "speakeasy", "vein"]

For length 26: 14 sets, example: ["alliance", "archbishop", "balm", "bonnet", "centipede", "cobol", "departure", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "mincemeat", "mycenae", "plugging", "smokescreen", "speakeasy", "vein"]

For length 27: 2 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "covariate", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy", "vein"]

For length 28: None

For length 29: None

For length 30: None

For length 31: None

</pre>