Determinant and permanent: Difference between revisions

* [[Permutations by swapping]]

<br><br>

 

=={{header|360 Assembly}}==

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

Q DS F sub matrix q((n-1)*(n-1)+1)

YREGS

{{out}}

<pre>

permanent= 900

</pre>

 

=={{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>

 

return 0;

A method to calculate determinant that might actually be usable:

#include <stdlib.h>

#include <tgmath.h>

printf("det: %19f\n", det(x, N));

return 0;

 

=={{header|C++}}==

{{trans|Java}}

#include <vector>

 

 

return 0;

{{out}}

<pre>[[1, 2], [3, 4]]

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))

(dolist (m (list m2 m3 m4 m5))

(format t "~a determinant: ~a, permanent: ~a~%" m (determinant m) (permanent m)) )

 

{{out}}

This requires the modules from the [[Permutations#D|Permutations]] and [[Permutations_by_swapping#D|Permutations by swapping]] tasks.

{{trans|Python}}

permutations_by_swapping1;

 

a.permanent, a.determinant);

}

{{out}}

<pre>[[ 1, 2],

[20, 21, 22, 23, 24]]

Permanent: 6778800, determinant: 0</pre>

 

=={{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)

(permanent M) → 6778800

 

 

=={{header|Factor}}==

 

: permanent ( matrix -- x )

dup square-matrix? [ "Matrix must be square." throw ] unless

[ dim first <iota> ] keep

Example output:

<pre>

900

</pre>

 

=={{header|Forth}}==

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

m3{{ lmat lufact

lmat det F. 3 m3{{ permanent F. CR

 

=={{header|Fortran}}==

Please find the compilation and example run at the start of the comments in the f90 source. Thank you.

 

!-*- mode: compilation; default-directory: "/tmp/" -*-

!Compilation started at Sat May 18 23:25:42

 

end program f

 

=={{header|FunL}}==

From the task description:

 

def perm( m ) = sum( 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() )

def det( m )

| m.length() == 1 and m(0).length() == 1 = m(0, 0)

 

Test using the first set of definitions (from task description):

( (1, 2),

(3, 4)),

 

for m <- matrices

 

{{out}}

 

=={{header|GLSL}}==

mat4 m1 = mat3(1, 2, 3, 4,

5, 6, 7, 8

 

float d = det(m1);

 

=={{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 (

fmt.Println(determinant(m2), permanent(m2))

fmt.Println(determinant(m3), permanent(m3))

{{out}}

<pre>

</pre>

===Ryser permanent===

 

import "fmt"

}

return

{{out}}

<pre>

===Library determinant===

'''go.matrix:'''

 

import (

{7, 5, 3},

{6, 1, 8}}).Det())

{{out}}

<pre>

</pre>

'''gonum/mat:'''

 

import (

7, 5, 3,

6, 1, 8})))

{{out}}

<pre>

 

=={{header|Haskell}}==

sPermutations = flip zip (cycle [1, -1]) . foldl aux [[]]

where

, [[2, 5], [4, 3]]

, [[4, 4], [2, 2]]

{{Out}}

<pre>Matrix:

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):

 

outer :: (a->b->c) -> [a] -> [b] -> [[c]]

outer f [] _ = []

perm m = (mul m (padj m)) !! 0 !! 0

 

 

=={{header|J}}==

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

 

Its determinant is 0. When we use IEEE floating point, we only get an approximation of this result:

 

 

If we use exact (rational) arithmetic, we get a precise result:

 

 

Meanwhile, the permanent does not have this problem in this example (the matrix contains no negative values and permanent does not use subtraction):

 

 

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.)

=={{header|Java}}==

 

 

public class MatrixArithmetic {

System.out.println("Permanent: "+perm(a));

}

 

Note that the first input is the size of the matrix.

For example:

 

1 2

3 4

Determinant: 0.0

Permanent: 6778800.0

 

=={{header|JavaScript}}==

arr.length === 1 ? (

arr[0][0]

];

console.log(determinant(M));

{{Out}}

<pre>0

{{Works with|jq|1.4}}

====Recursive definitions====

def except(i;j):

reduce del(.[i])[] as $row ([]; . + [$row | del(.[j]) ] );

| reduce range(0; length) as $i

(0; . + $m[0][$i] * ( $m | except(0;$i) | perm) )

'''Examples'''

[ [1, 2],

[3, 4]],

 

"Determinants: ", (matrices | det),

{{Out}}

Determinants:

-2

10

29556

====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:

| (.[0]|product_diagonal) as $l

| if $l == 0 then 0 else $l * (.[1]|product_diagonal) | tidy end ;

'''Examples'''

 

Using matrices/0 as defined above:

{{Output}}

$ /usr/local/bin/jq -M -n -f LU.rc

 

=={{header|Julia}}==

The determinant of a matrix <code>A</code> can be computed by the built-in function

 

{{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))

 

Example output:

julia> det(A), perm(A)

 

=={{header|Kotlin}}==

 

typealias Matrix = Array<DoubleArray>

println(" permanent = ${permanent(m)}\n")

}

 

{{out}}

 

=={{header|Lambdatalk}}==

{require lib_matrix}

 

[7,8,-9]]}}

-> 216

 

=={{header|Lua}}==

_JT={}

function JT(dim)

matrix2:dump();

print("det:",matrix2:det(), "permanent:",matrix2:perm())

{{out}}

<pre>7 2 -2 4

 

=={{header|Maple}}==

 

with(LinearAlgebra):

 

Determinant(M);

Output:

<pre> -360

900</pre>

 

Determinant is a built in function Det

With[{v = Array[x, Length[m]]},

Coefficient[Times @@ (m.v), Times @@ v]

 

=={{header|Maxima}}==

 

determinant(a);

 

permanent(a);

 

=={{header|МК-61/52}}==

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

echo "perm: ", a.perm, " det: ", a.det

echo "perm: ", b.perm, " det: ", b.det

Output:

<pre>perm: 10.0 det: -2.0

 

=={{header|Ol}}==

; helper function that returns rest of matrix by col/row

(define (rest matrix i j)

(20 21 22 23 24))))

; ==> 6778800

 

=={{header|PARI/GP}}==

The determinant is built in:

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));

(-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:

 

=={{header|Perl}}==

{{trans|C}}

use strict;

use warnings;

print "det(M) = " . $M->determinant . ".\n";

print "det(M) = " . $M->det . ".\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.

=={{header|Phix}}==

{{trans|Java}}

{{out}}

<pre>

 

=={{header|PowerShell}}==

function det-perm ($array) {

if($array) {

det-perm @(@(2,5),@(4,3))

det-perm @(@(4,4),@(2,2))

<b>Output:</b>

<pre>

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

print('')

pp(a)

 

;Sample output:

 

The second matrix above is that used in the Tcl example. The third matrix is from the J language example. Note that the determinant seems to be 'exact' using this method of calculation without needing to resort to other than Pythons default numbers.

 

=={{header|Racket}}==

#lang racket

(require math)

(for/product ([i n] [σi σ])

(matrix-ref M i σi))))

 

=={{header|Raku}}==

Uses the permutations generator from the [[Permutations by swapping#Raku|Permutations by swapping]] task. This implementation is naive and brute-force (slow) but exact.

 

sub order ($sg, @xs) { $sg > 0 ?? @xs !! @xs.reverse }

 

say "Permanent: \t", rat-or-int @matrix.&m_arith: <perm>;

say '-' x 40;

 

'''Output'''

 

=={{header|REXX}}==

* Test the two functions determinant and permanent

* using the matrix specifications shown for other languages

Say ' permanent='right(permanent(as),7)

Say copies('-',50)

 

* determinant.rex

* compute the determinant of the given square matrix

Say 'invalid number of elements:' nn 'is not a square.'

Exit

 

* permanent.rex

* compute the permanent of a matrix

Say 'invalid number of elements:' nn 'is not a square.'

Exit

 

Output:

permanent=6778800

--------------------------------------------------</pre>

 

=={{header|Ruby}}==

Matrix in the standard library provides a method for the determinant, but not for the permanent.

 

class Matrix

puts "determinant:\t #{m.determinant}", "permanent:\t #{m.permanent}"

puts

{{Output}}

<pre>

permanent: 6778800

</pre>

{{trans|Java}}

fn main() {

let mut m1: Vec<Vec<f64>> = vec![vec![1.0,2.0],vec![3.0,4.0]];

 

println!("Determinant of m1: {}", determinant(rr_m1));

 

println!("Determinant of m2: {}", determinant(rr_m2));

 

println!("Determinant of m3: {}", determinant(rr_m3));

 

}

}

 

{{Output}}

<pre>

Determinant of m1: -2

Determinant of m2: 0

Determinant of m3: 0

</pre>

=={{header|Scala}}==

def permutationsSgn[T]: List[T] => List[(Int,List[T])] = {

case Nil => List((1,Nil))

}

summands.toList.foldLeft(0)({case (x,y) => x + y})

 

=={{header|Sidef}}==

The `determinant` method is provided by the Array class.

{{trans|Ruby}}

method permanent {

var r = @^self.len

[m1, m2, m3].each { |m|

say "determinant:\t #{m.determinant}\npermanent:\t #{m.permanent}\n"

{{out}}

<pre>determinant: -2

 

=={{header|Simula}}==

BEGIN

 

! PERMANENT: 6778800.0 ;

 

Input:

<pre>

{{works with|OpenAxiom}}

{{works with|Axiom}}

 

+2 9 4+

 

(3) 900

 

[http://fricas.github.io/api/Matrix.html?highlight=matrix Domain:Matrix(R)]

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.

 

if (i < 1 | i > n) {

return(1::n)

}

return(s)

 

Example:

 

: a

[symmetric]

 

: sumrec(a,1)

 

=={{header|Tcl}}==

{{tcllib|math::linearalgebra}}

{{tcllib|struct::list}}

package require struct::list

 

}

return [::tcl::mathop::+ {*}$sum]

Demonstrating with a sample matrix:

{1 2 3 4}

{4 5 6 7}

}

puts [::math::linearalgebra::det $mat]

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{trans|Java}}

 

Function Minor(a As Double(,), x As Integer, y As Integer) As Double(,)

End Sub

 

{{out}}

<pre>[1, 2]

{{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

Next i

Debug.Print det(tests(13)), "error", perm(tests(13))

<pre>Determinant Builtin det Permanent

-2 -2 10

{{libheader|Wren-matrix}}

{{libheader|Wren-fmt}}

 

var arrays = [

System.print("\nDeterminant: %(m.det)")

System.print("Permanent : %(m.perm)\n")

 

{{out}}

 

=={{header|zkl}}==

fcn perm(A){ // should verify A is square

numRows:=A.rows;

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);

{{out}}

<pre>