Determinant and permanent: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
Line 18:
{{trans|Nim}}
<
V items = [[Int]()]
L(j) seq
Line 66:
print(‘perm: ’perm(a)‘ det: ’det(a))
print(‘perm: ’perm(b)‘ det: ’det(b))
print(‘perm: ’perm(c)‘ det: ’det(c))</
{{out}}
Line 79:
and two ASSIST macros (XDECO,XPRNT) to keep it as short as possible.
It works on OS/360 family (MVS,z/OS), on DOS/360 family (z/VSE) use GETVIS,FREEVIS instead of GETMAIN,FREEMAIN.
<
MATARI START
STM R14,R12,12(R13) save caller's registers
Line 230:
Q DS F sub matrix q((n-1)*(n-1)+1)
YREGS
END MATARI</
{{out}}
<pre>
Line 239:
=={{header|Arturo}}==
<
loop m 'row -> print map row 'val [pad to :string .format:".2f" val 6]
print "--------------------------------"
Line 314:
print ["A: perm ->" perm A "det ->" det A]
print ["B: perm ->" perm B "det ->" det B]
print ["C: perm ->" perm C "det ->" det C]</
{{out}}
Line 324:
=={{header|C}}==
C99 code. By no means efficient or reliable. If you need it for serious work, go find a serious library.
<
#include <stdlib.h>
#include <string.h>
Line 368:
return 0;
}</
A method to calculate determinant that might actually be usable:
<
#include <stdlib.h>
#include <tgmath.h>
Line 445:
printf("det: %19f\n", det(x, N));
return 0;
}</
=={{header|C++}}==
{{trans|Java}}
<
#include <vector>
Line 542:
return 0;
}</
{{out}}
<pre>[[1, 2], [3, 4]]
Line 556:
A recursive version, no libraries required, it doesn't use much consing, only for the list of columns to skip
<
(defun determinant (rows &optional (skip-cols nil))
(let* ((result 0) (sgn -1))
Line 600:
(dolist (m (list m2 m3 m4 m5))
(format t "~a determinant: ~a, permanent: ~a~%" m (determinant m) (permanent m)) )
</syntaxhighlight>
{{out}}
Line 612:
This requires the modules from the [[Permutations#D|Permutations]] and [[Permutations_by_swapping#D|Permutations by swapping]] tasks.
{{trans|Python}}
<
permutations_by_swapping1;
Line 666:
a.permanent, a.determinant);
}
}</
{{out}}
<pre>[[ 1, 2],
Line 687:
{{libheader| System.SysUtils}}
{{Trans|Java}}
<syntaxhighlight lang="delphi">
program Determinant_and_permanent;
Line 816:
writeln(#10'Permanent: ', perm(a): 3: 2);
readln;
end.</
{{out}}
<pre>Enter with matrix size:
Line 837:
=={{header|EchoLisp}}==
This requires the 'list' library for '''(in-permutations n)''' and the 'matrix' library for the built-in '''(determinant M)'''.
<
(lib 'list)
(lib 'matrix)
Line 866:
(permanent M) → 6778800
</syntaxhighlight>
=={{header|Factor}}==
<
: permanent ( matrix -- x )
dup square-matrix? [ "Matrix must be square." throw ] unless
[ dim first <iota> ] keep
'[ [ _ nth nth ] map-index product ] map-permutations sum ;</
Example output:
<pre>
Line 891:
{{works with|gforth|0.7.9_20170427}}
Requiring a permute.fs file from the [[Permutations_by_swapping#Forth|Permutations by swapping]] task.
<
S" fsl/dynmem.seq" REQUIRED
[UNDEFINED] defines [IF] SYNONYM defines IS [THEN]
Line 928:
m3{{ lmat lufact
lmat det F. 3 m3{{ permanent F. CR
lmat lu-free</
=={{header|Fortran}}==
Line 934:
Please find the compilation and example run at the start of the comments in the f90 source. Thank you.
<syntaxhighlight lang="fortran">
!-*- mode: compilation; default-directory: "/tmp/" -*-
!Compilation started at Sat May 18 23:25:42
Line 1,006:
end program f
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
'removes row j, column i from the matrix, stores result in S()
dim as uinteger ii, jj, size=ubound(M), ix, jx
Line 1,055:
print deperminant( A(), true ), deperminant( A(), false )
print deperminant( B(), true ), deperminant( B(), false )
print deperminant( C(), true ), deperminant( C(), false )</
{{out}}<pre>
-2 10
Line 1,064:
=={{header|FunL}}==
From the task description:
<
def perm( m ) = sum( product(m(i, sigma(i)) | i <- 0:m.length()) | sigma <- (0:m.length()).permutations() )
def det( m ) = sum( sgn(sigma)*product(m(i, sigma(i)) | i <- 0:m.length()) | sigma <- (0:m.length()).permutations() )</
Laplace expansion (recursive):
<
| m.length() == 1 and m(0).length() == 1 = m(0, 0)
| otherwise = sum( m(i, 0)*perm(m(0:i, 1:m.length()) + m(i+1:m.length(), 1:m.length())) | i <- 0:m.length() )
Line 1,077:
def det( m )
| m.length() == 1 and m(0).length() == 1 = m(0, 0)
| otherwise = sum( (-1)^i*m(i, 0)*det(m(0:i, 1:m.length()) + m(i+1:m.length(), 1:m.length())) | i <- 0:m.length() )</
Test using the first set of definitions (from task description):
<
( (1, 2),
(3, 4)),
Line 1,097:
for m <- matrices
println( m, 'perm: ' + perm(m), 'det: ' + det(m) )</
{{out}}
Line 1,109:
=={{header|GLSL}}==
<
mat4 m1 = mat3(1, 2, 3, 4,
5, 6, 7, 8
Line 1,116:
float d = det(m1);
</syntaxhighlight>
=={{header|Go}}==
===Implementation===
This implements a naive algorithm for each that follows from the definitions. It imports the permute packge from the [[Permutations_by_swapping#Go|Permutations by swapping]] task.
<
import (
Line 1,172:
fmt.Println(determinant(m2), permanent(m2))
fmt.Println(determinant(m3), permanent(m3))
}</
{{out}}
<pre>
Line 1,179:
</pre>
===Ryser permanent===
<
import "fmt"
Line 1,222:
}
return
}</
{{out}}
<pre>
Line 1,230:
===Library determinant===
'''go.matrix:'''
<
import (
Line 1,246:
{7, 5, 3},
{6, 1, 8}}).Det())
}</
{{out}}
<pre>
Line 1,253:
</pre>
'''gonum/mat:'''
<
import (
Line 1,269:
7, 5, 3,
6, 1, 8})))
}</
{{out}}
<pre>
Line 1,277:
=={{header|Haskell}}==
<
sPermutations = flip zip (cycle [1, -1]) . foldl aux [[]]
where
Line 1,335:
, [[2, 5], [4, 3]]
, [[4, 4], [2, 2]]
]</
{{Out}}
<pre>Matrix:
Line 1,395:
Here is code for computing the determinant and permanent very inefficiently, via [[wp:Cramer's rule|Cramer's rule]] (for the determinant, as well as its analog for the permanent):
<syntaxhighlight lang="haskell">
outer :: (a->b->c) -> [a] -> [b] -> [[c]]
outer f [] _ = []
Line 1,447:
perm m = (mul m (padj m)) !! 0 !! 0
</syntaxhighlight>
=={{header|J}}==
Line 1,455:
For example, given the matrix:
<
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24</
Its determinant is 0. When we use IEEE floating point, we only get an approximation of this result:
<
_1.30277e_44</
If we use exact (rational) arithmetic, we get a precise result:
<
0</
Meanwhile, the permanent does not have this problem in this example (the matrix contains no negative values and permanent does not use subtraction):
<
6778800</
As an aside, note also that for specific verbs (like <code>-/ .*</code>) J uses an algorithm which is more efficient than the brute force approach implied by the [http://www.jsoftware.com/help/dictionary/d300.htm definition of <code> .</code>]. (In general, where there are common, useful, concise definitions where special code can improve resource use by more than a factor of 2, the implementors of J try to make sure that that special code gets used for those definitions.)
Line 1,481:
=={{header|Java}}==
<
public class MatrixArithmetic {
Line 1,535:
System.out.println("Permanent: "+perm(a));
}
}</
Note that the first input is the size of the matrix.
Line 1,541:
For example:
<syntaxhighlight lang="text">2
1 2
3 4
Line 1,556:
Determinant: 0.0
Permanent: 6778800.0
</syntaxhighlight>
=={{header|JavaScript}}==
<
arr.length === 1 ? (
arr[0][0]
Line 1,587:
];
console.log(determinant(M));
console.log(permanent(M));</
{{Out}}
<pre>0
Line 1,595:
{{Works with|jq|1.4}}
====Recursive definitions====
<
def except(i;j):
reduce del(.[i])[] as $row ([]; . + [$row | del(.[j]) ] );
Line 1,612:
| reduce range(0; length) as $i
(0; . + $m[0][$i] * ( $m | except(0;$i) | perm) )
end ;</
'''Examples'''
<
[ [1, 2],
[3, 4]],
Line 1,635:
"Determinants: ", (matrices | det),
"Permanents: ", (matrices | perm)</
{{Out}}
<
Determinants:
-2
Line 1,647:
10
29556
6778800</
====Determinant via LU Decomposition====
The following uses the jq infrastructure at [[LU decomposition]] to achieve an efficient implementation of det/0:
<
def det:
def product_diagonal:
Line 1,658:
| (.[0]|product_diagonal) as $l
| if $l == 0 then 0 else $l * (.[1]|product_diagonal) | tidy end ;
</syntaxhighlight>
'''Examples'''
Using matrices/0 as defined above:
<syntaxhighlight lang
{{Output}}
$ /usr/local/bin/jq -M -n -f LU.rc
Line 1,671:
=={{header|Julia}}==
<syntaxhighlight lang
The determinant of a matrix <code>A</code> can be computed by the built-in function
<syntaxhighlight lang
{{trans|Python}}
The following function computes the permanent of a matrix A from the definition:
<
m, n = size(A)
if m != n; throw(ArgumentError("permanent is for square matrices only")); end
sum(σ -> prod(i -> A[i,σ[i]], 1:n), permutations(1:n))
end</
Example output:
<
julia> det(A), perm(A)
(-360.0,900)</
=={{header|Kotlin}}==
<
typealias Matrix = Array<DoubleArray>
Line 1,775:
println(" permanent = ${permanent(m)}\n")
}
}</
{{out}}
Line 1,797:
=={{header|Lambdatalk}}==
<
{require lib_matrix}
Line 1,821:
[7,8,-9]]}}
-> 216
</syntaxhighlight>
=={{header|Lua}}==
<
_JT={}
function JT(dim)
Line 1,910:
matrix2:dump();
print("det:",matrix2:det(), "permanent:",matrix2:perm())
</syntaxhighlight>
{{out}}
<pre>7 2 -2 4
Line 1,924:
=={{header|Maple}}==
<
with(LinearAlgebra):
Determinant(M);
Permanent(M);</
Output:
<pre> -360
Line 1,938:
[https://reference.wolfram.com/language/ref/Permanent.html Permanent] is also a built in function, but here is a way it could be implemented:
<
With[{v = Array[x, Length[m]]},
Coefficient[Times @@ (m.v), Times @@ v]
]</
=={{header|Maxima}}==
<
determinant(a);
Line 1,950:
permanent(a);
900</
=={{header|МК-61/52}}==
Line 1,971:
{{trans|Python}}
Using the permutationsswap module from [[Permutations by swapping#Nim|Permutations by swapping]]:
<
type Matrix[M,N: static[int]] = array[M, array[N, float]]
Line 2,007:
echo "perm: ", a.perm, " det: ", a.det
echo "perm: ", b.perm, " det: ", b.det
echo "perm: ", c.perm, " det: ", c.det</
Output:
<pre>perm: 10.0 det: -2.0
Line 2,014:
=={{header|Ol}}==
<
; helper function that returns rest of matrix by col/row
(define (rest matrix i j)
Line 2,081:
(20 21 22 23 24))))
; ==> 6778800
</syntaxhighlight>
=={{header|PARI/GP}}==
The determinant is built in:
<syntaxhighlight lang
and the permanent can be defined as
<
For better performance, here's a version using Ryser's formula:
<
{
my(n=matsize(M)[1],innerSums=vectorv(n));
Line 2,102:
(-1)^hammingweight(gray)*factorback(innerSums)
)*(-1)^n;
}</
{{works with|PARI/GP|2.10.0+}}
As of version 2.10, the matrix permanent is built in:
<syntaxhighlight lang
=={{header|Perl}}==
{{trans|C}}
<
use strict;
use warnings;
Line 2,136:
print "det(M) = " . $M->determinant . ".\n";
print "det(M) = " . $M->det . ".\n";
print "perm(M) = " . permanent($M) . ".\n";</
<code>determinant</code> and <code>det</code> are already defined in PDL, see[http://pdl.perl.org/?docs=MatrixOps&title=the%20PDL::MatrixOps%20manpage#det]. <code>permanent</code> has to be defined manually.
Line 2,156:
=={{header|Phix}}==
{{trans|Java}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">minor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
Line 2,246:
<span style="color: #0000FF;">?{</span><span style="color: #000000;">det</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">),</span><span style="color: #000000;">perm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 2,264:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function det-perm ($array) {
if($array) {
Line 2,309:
det-perm @(@(2,5),@(4,3))
det-perm @(@(4,4),@(2,2))
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 2,325:
Using the module file spermutations.py from [[Permutations by swapping#Python|Permutations by swapping]]. The algorithm for the determinant is a more literal translation of the expression in the task description and the Wikipedia reference.
<
from operator import mul
from math import fsum
Line 2,369:
print('')
pp(a)
print('Perm: %s Det: %s' % (perm(a), det(a)))</
;Sample output:
Line 2,389:
=={{header|R}}==
R has matrix algebra built in, so we do not need to import anything when calculating the determinant. However, we will use a library to generate the permutations of 1:n.
<
perm <- function(A)
{
Line 2,404:
"Test 3" = rbind(c(0, 1, 2, 3, 4), c(5, 6, 7, 8, 9), c(10, 11, 12, 13, 14),
c(15, 16, 17, 18, 19), c(20, 21, 22, 23, 24)))
print(sapply(testData, function(x) list(Determinant = det(x), Permanent = perm(x))))</
{{out}}
Line 2,412:
=={{header|Racket}}==
<
#lang racket
(require math)
Line 2,422:
(for/product ([i n] [σi σ])
(matrix-ref M i σi))))
</syntaxhighlight>
=={{header|Raku}}==
Line 2,429:
Uses the permutations generator from the [[Permutations by swapping#Raku|Permutations by swapping]] task. This implementation is naive and brute-force (slow) but exact.
<syntaxhighlight lang="raku"
sub order ($sg, @xs) { $sg > 0 ?? @xs !! @xs.reverse }
Line 2,485:
say "Permanent: \t", rat-or-int @matrix.&m_arith: <perm>;
say '-' x 40;
}</
'''Output'''
Line 2,517:
=={{header|REXX}}==
<
* Test the two functions determinant and permanent
* using the matrix specifications shown for other languages
Line 2,555:
Say ' permanent='right(permanent(as),7)
Say copies('-',50)
Return</
<
* determinant.rex
* compute the determinant of the given square matrix
Line 2,616:
Say 'invalid number of elements:' nn 'is not a square.'
Exit
End</
<
* permanent.rex
* compute the permanent of a matrix
Line 2,722:
Say 'invalid number of elements:' nn 'is not a square.'
Exit
End</
Output:
Line 2,748:
=={{header|Ruby}}==
Matrix in the standard library provides a method for the determinant, but not for the permanent.
<
class Matrix
Line 2,773:
puts "determinant:\t #{m.determinant}", "permanent:\t #{m.permanent}"
puts
end</
{{Output}}
<pre>
Line 2,787:
=={{header|Rust}}==
{{trans|Java}}
<
fn main() {
let mut m1: Vec<Vec<f64>> = vec![vec![1.0,2.0],vec![3.0,4.0]];
Line 2,869:
}
</syntaxhighlight>
{{Output}}
<pre>
Line 2,881:
=={{header|Scala}}==
<
def permutationsSgn[T]: List[T] => List[(Int,List[T])] = {
case Nil => List((1,Nil))
Line 2,907:
}
summands.toList.foldLeft(0)({case (x,y) => x + y})
</syntaxhighlight>
=={{header|Sidef}}==
The `determinant` method is provided by the Array class.
{{trans|Ruby}}
<
method permanent {
var r = @^self.len
Line 2,942:
[m1, m2, m3].each { |m|
say "determinant:\t #{m.determinant}\npermanent:\t #{m.permanent}\n"
}</
{{out}}
<pre>determinant: -2
Line 2,955:
=={{header|Simula}}==
<
BEGIN
Line 3,046:
! PERMANENT: 6778800.0 ;
END</
Input:
<pre>
Line 3,077:
{{works with|OpenAxiom}}
{{works with|Axiom}}
<
+2 9 4+
Line 3,092:
(3) 900
Type: PositiveInteger</
[http://fricas.github.io/api/Matrix.html?highlight=matrix Domain:Matrix(R)]
Line 3,102:
For x=-1, the main function '''sumrec(a,x)''' computes the determinant of a by developing the determinant along the first column. For x=1, one gets the permanent.
<syntaxhighlight lang="text">real vector range1(real scalar n, real scalar i) {
if (i < 1 | i > n) {
return(1::n)
Line 3,129:
}
return(s)
}</
Example:
<
: a
[symmetric]
Line 3,151:
: sumrec(a,1)
9</
=={{header|Tcl}}==
Line 3,158:
{{tcllib|math::linearalgebra}}
{{tcllib|struct::list}}
<
package require struct::list
Line 3,172:
}
return [::tcl::mathop::+ {*}$sum]
}</
Demonstrating with a sample matrix:
<
{1 2 3 4}
{4 5 6 7}
Line 3,181:
}
puts [::math::linearalgebra::det $mat]
puts [permanent $mat]</
{{out}}
<pre>
Line 3,190:
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<
Function Minor(a As Double(,), x As Integer, y As Integer) As Double(,)
Line 3,267:
End Sub
End Module</
{{out}}
<pre>[1, 2]
Line 3,294:
{{trans|Phix}}
As an extra, the results of the built in WorksheetFuction.MDeterm are shown. The latter does not work for scalars.
<
Private Function minor(a As Variant, x As Integer, y As Integer) As Variant
Dim l As Integer: l = UBound(a) - 1
Line 3,385:
Next i
Debug.Print det(tests(13)), "error", perm(tests(13))
End Sub</
<pre>Determinant Builtin det Permanent
-2 -2 10
Line 3,404:
{{libheader|Wren-matrix}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 3,432:
System.print("\nDeterminant: %(m.det)")
System.print("Permanent : %(m.perm)\n")
}</
{{out}}
Line 3,468:
=={{header|zkl}}==
<
fcn perm(A){ // should verify A is square
numRows:=A.rows;
Line 3,478:
println(A.format());
println("Permanent: %.2f, determinant: %.2f".fmt(perm(A),A.det()));
};</
<
B:=GSL.Matrix(4,4).set(1,2,3,4, 4,5,6,7, 7,8,9,10, 10,11,12,13);
C:=GSL.Matrix(5,5).set( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,
15,16,17,18,19, 20,21,22,23,24);
T(A,B,C).apply2(test);</
{{out}}
<pre>
|