Matrix chain multiplication: Difference between revisions
→{{header|Perl 6}}: simplified code to directly address the task specifications
SqrtNegInf (talk | contribs) (→{{header|Perl 6}}: simplified code to directly address the task specifications) |
|||
Line 592:
=={{header|Perl 6}}==
This example is based on Moritz Lenz's code, written for Carl Mäsak's Perl 6 Coding Contest, in 2010. Slightly simplified, it fulfills the Rosetta Code task as well.
<lang perl6>sub matrix-mult-chaining(@dimensions) {▼
my @cp;▼
# * the upper triangle of the diagonal matrix stores the cost (c) for
# * the lower triangle stores the path (p) that was used for the lowest cost▼
# multiplication to get from $i to $j.▼
# a matrix never needs to be multiplied with itself, so it has cost 0▼
▲sub matrix-mult-chaining(@dimensions) {
▲ # @cp has a dual function: the upper triangle of the diagonal matrix
▲ # stores the cost (c) for mulplying matrices $i and $j in @cp[$j][$i],
▲ # the lower triangle stores the path (p) that was used for the lowest cost
▲ # multiplication to get from $i to $j.
▲ my @cp;
▲ # a matrix never needs to be multiplied with itself,
@cp[$_][$_] = 0 for @dimensions.keys;
my @path;
Line 636 ⟶ 612:
for $start .. $end - 1 -> $step {
my $new-cost = @cp[$step][$start]
if $new-cost < @cp[$end][$start] {
@cp[$end][$start] = $new-cost; # cost
@cp[$
}
}
}
}
sub find-path(Int $start, Int $end) {
if $start == $end {
Line 657 ⟶ 632:
}
}
}
is matrix-mult-chaining(<6 2 5 1 6 3 9 1 25 18>),▼
{{Out}}▼
<pre>(38120 ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12)))
(1773740 (A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11)))</pre>▼
▲1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10
▲(A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11))
=={{header|Phix}}==
| |||