Rosetta Code

Subset sum problem: Difference between revisions

Page Discussion

Subset sum problem (view source)

Revision as of 01:14, 22 October 2012

87 bytes removed ,  11 years ago
Simpler D entry, updated
m (→‎{{header|REXX}}: re-did the REXX program, combined some statements, removed some blank lines. -- ~~~~)
(Simpler D entry, updated)
Line 343:
A simple brute-force solution.
{{trans|Ruby}}
<lang d>import std.stdio, std.algorithm, std.string, std.typecons;
 
T[][] combinations(T)(in T[] arr, in int k) pure nothrow {
if (k == 0) return [[]];
T[][] result;
foreach (i, x; arr)
foreach (suffix; combinations(arr[i + 1 .. $], k - 1))
result ~= x ~ suffix;
return result;
Line 355:
 
void main() {
alias tuple TP;
immutable items = [
TP("alliance", -624), TP("archbishop", -915), TP("balm", 397),
TP("bonnet", 452), TP("brute", 870), TP("centipede", -658),
TP("cobol", 362), TP("covariate", 590), TP("departure", 952),
TP("deploy", 44), TP("diophantine", 645), TP("efferent", 54),
TP("elysee", -326), TP("eradicate", 376), TP("escritoire", 856),
TP("exorcism", -983), TP("fiat", 170), TP("filmy", -874),
TP("flatworm", 503), TP("gestapo", 915), TP("infra", -847),
TP("isis", -982), TP("lindholm", 999), TP("markham", 475),
TP("mincemeat", -880), TP("moresby", 756), TP("mycenae", 183),
TP("plugging", -266), TP("smokescreen", 423), TP("speakeasy", -745),
TP("vein", 813)];
 
foreach (n; 1 .. items.length)
foreach (comb; combinations(items, n))
if (reduce!q{ a + b[1] }(0, comb) == 0) {
return writefln("A subset of length %d: %-(%s, %)", n,
// comb.map!q{ a[0] }().join(", "));
writeflnwriteln("No solution found.");▼
comb.map!q{ cast()a[0] }().join(", "));
return;
}
▲ writefln("No solution found.");
}</lang>
{{out}}
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210615"