Subset sum problem: Difference between revisions

Content added Content deleted
(Added Kotlin)
(→‎{{header|Perl}}: Sort hash for consistency, use new ntheory with loop exit construct)
Line 1,052: Line 1,052:
{{libheader|ntheory}}
{{libheader|ntheory}}
<lang perl>use ntheory qw/:all/;
<lang perl>use ntheory qw/:all/;
my $print_all_combinations = 0;


my %pairs = (
my %pairs = (
Line 1,063: Line 1,062:
mincemeat => -880, moresby => 756, mycenae => 183, plugging => -266,
mincemeat => -880, moresby => 756, mycenae => 183, plugging => -266,
smokescreen => 423, speakeasy => -745, vein => 813 );
smokescreen => 423, speakeasy => -745, vein => 813 );
# sort so we get the same order each time
my @names = keys(%pairs);
my @weights = values(%pairs);
my @names = sort keys(%pairs);
my @weights = @pairs{@names}; # hash slice gives all values in same order


⚫
foreach my $n (1 .. @names) {
if ($print_all_combinations) {

⚫
foreach my $n (1 .. @names) {
forcomb {
forcomb {
# Remove the "lastfor, " to get all combinations
print "Length $n: @names[@_]\n" unless vecsum(@weights[@_]);
lastfor, print "Length $n: @names[@_]\n" if vecsum(@weights[@_]) == 0;
} @names, $n;
} @names, $n;
}

} else {

foreach my $n (1 .. @names) {
eval {
forcomb {
if (vecsum(@weights[@_]) == 0) {
print "Length $n: @names[@_]\n";
die;
}
} @names, $n;
};
}
}</lang>
}</lang>
Printing just the first one found for each number of elements:
Printing just the first one found for each number of elements:
Line 1,091: Line 1,076:
<pre>
<pre>
Length 2: archbishop gestapo
Length 2: archbishop gestapo
Length 3: exorcism fiat vein
Length 3: centipede markham mycenae
Length 4: efferent plugging brute centipede
Length 4: alliance balm deploy mycenae
Length 5: efferent exorcism cobol fiat balm
Length 5: alliance brute covariate deploy mincemeat
Length 6: efferent exorcism isis vein gestapo mycenae
Length 6: alliance archbishop balm deploy gestapo mycenae
Length 7: efferent exorcism isis cobol covariate gestapo deploy
Length 7: alliance archbishop bonnet cobol departure exorcism moresby
Length 8: efferent exorcism isis speakeasy covariate vein escritoire balm
Length 8: alliance archbishop balm bonnet fiat flatworm isis lindholm
Length 9: alliance archbishop balm bonnet brute covariate eradicate mincemeat plugging
Length 9: efferent exorcism isis speakeasy cobol markham smokescreen lindholm balm
... to length 27 ...
... to length 27 ...
</pre>
</pre>


We can also use different modules. Assuming the same pairs/names/weights variables set and first combination only, this iterator style is a little cleaner when wanting to exit early:
We can also use different modules for this brute force method. Assuming the same pairs/names/weights variables:
<lang perl>use List::Util qw/sum/;
<lang perl>use List::Util qw/sum/;
use Algorithm::Combinatorics qw/combinations/;
use Algorithm::Combinatorics qw/combinations/;
Retrieved from "https://rosettacode.org/wiki/Subset_sum_problem"