Kronecker product
You are encouraged to solve this task according to the task description, using any language you may know.
This page uses content from Wikipedia. The original article was at Kronecker product. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
- Task
Implement the Kronecker product of two matrices (arbitrary sized) resulting in a block matrix.
- Test cases
Show results for each of the following 2 samples:
Sample 1 (from Wikipedia):
|1 2| x |0 5| = | 0 5 0 10| |3 4| |6 7| | 6 7 12 14| | 0 15 0 20| |18 21 24 28|
Sample 2:
|0 1 0| x |1 1 1 1| = |0 0 0 0 1 1 1 1 0 0 0 0| |1 1 1| |1 0 0 1| |0 0 0 0 1 0 0 1 0 0 0 0| |0 1 0| |1 1 1 1| |0 0 0 0 1 1 1 1 0 0 0 0| |1 1 1 1 1 1 1 1 1 1 1 1| |1 0 0 1 1 0 0 1 1 0 0 1| |1 1 1 1 1 1 1 1 1 1 1 1| |0 0 0 0 1 1 1 1 0 0 0 0| |0 0 0 0 1 0 0 1 0 0 0 0| |0 0 0 0 1 1 1 1 0 0 0 0|
See implementations and results below in JavaScript and PARI/GP languages.
- See also
AppleScript
<lang applescript>-- KRONECKER PRODUCT OF TWO MATRICES ------------------------------------------
-- kprod :: Num -> Num -> Num on kprod(xs, ys)
script concatTranspose on lambda(m) map(my concat, my transpose(m)) end lambda end script script -- Multiplication by N over a list of lists -- f :: Num -> Num -> Num on f(mx, n) script mapMult on product(a, b) a * b end product on lambda(xs) map(curry(product)'s lambda(n), xs) end lambda end script map(mapMult, mx) end f on lambda(zs) map(curry(f)'s lambda(ys), zs) end lambda end script concatMap(concatTranspose, map(result, xs))
end kprod
-- TEST ----------------------------------------------------------------------- on run
unlines(map(show, ¬ kprod({{1, 2}, {3, 4}}, ¬ {{0, 5}, {6, 7}}))) & ¬ linefeed & linefeed & ¬ unlines(map(show, ¬ kprod({{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, ¬ {{1, 1, 1, 1}, {1, 0, 0, 1}, {1, 1, 1, 1}})))
end run
-- GENERIC FUNCTIONS ----------------------------------------------------------
-- concat :: a -> [a] | [String] -> String on concat(xs)
script append on lambda(a, b) a & b end lambda end script if length of xs > 0 and class of (item 1 of xs) is string then set unit to "" else set unit to {} end if foldl(append, unit, xs)
end concat
-- concatMap :: (a -> [b]) -> [a] -> [b] on concatMap(f, xs)
set lst to {} set lng to length of xs tell mReturn(f) repeat with i from 1 to lng set lst to (lst & lambda(contents of item i of xs, i, xs)) end repeat end tell return lst
end concatMap
-- curry :: (Script|Handler) -> Script on curry(f)
script on lambda(a) script on lambda(b) lambda(a, b) of mReturn(f) end lambda end script end lambda end script
end curry
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to lambda(v, item i of xs, i, xs) end repeat return v end tell
end foldl
-- intercalate :: Text -> [Text] -> Text on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText} set strJoined to lstText as text set my text item delimiters to dlm return strJoined
end intercalate
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to lambda(item i of xs, i, xs) end repeat return lst end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then f else script property lambda : f end script end if
end mReturn
-- show :: a -> String on show(e)
set c to class of e if c = list then script serialized on lambda(v) show(v) end lambda end script "{" & intercalate(", ", map(serialized, e)) & "}" else if c = record then script showField on lambda(kv) set {k, v} to kv k & ":" & show(v) end lambda end script "{" & intercalate(", ", ¬ map(showField, zip(allKeys(e), allValues(e)))) & "}" else if c = date then ("date \"" & e as text) & "\"" else if c = text then "\"" & e & "\"" else try e as text on error ("«" & c as text) & "»" end try end if
end show
-- transpose :: a -> a on transpose(xss)
script column on lambda(_, iCol) script row on lambda(xs) item iCol of xs end lambda end script map(row, xss) end lambda end script map(column, item 1 of xss)
end transpose
-- unlines :: [String] -> String on unlines(xs)
intercalate(linefeed, xs)
end unlines</lang>
- Output:
{0, 5, 0, 10} {6, 7, 12, 14} {0, 15, 0, 20} {18, 21, 24, 28} {0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0} {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0} {0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0} {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} {1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1} {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} {0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0} {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0} {0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0}
Haskell
<lang haskell>import Data.List (transpose)
kprod
:: Num a => a -> a -> a
kprod xs ys =
let f = fmap . fmap . (*) -- Multiplication by n over list of lists in (concat <$>) . transpose =<< fmap (`f` ys) <$> xs
main :: IO () main = do
mapM_ print $ kprod [[1, 2], [3, 4]] [[0, 5], [6, 7]] putStrLn [] mapM_ print $ kprod [[0, 1, 0], [1, 1, 1], [0, 1, 0]] [[1, 1, 1, 1], [1, 0, 0, 1], [1, 1, 1, 1]]</lang>
- Output:
[0,5,0,10] [6,7,12,14] [0,15,0,20] [18,21,24,28] [0,0,0,0,1,1,1,1,0,0,0,0] [0,0,0,0,1,0,0,1,0,0,0,0] [0,0,0,0,1,1,1,1,0,0,0,0] [1,1,1,1,1,1,1,1,1,1,1,1] [1,0,0,1,1,0,0,1,1,0,0,1] [1,1,1,1,1,1,1,1,1,1,1,1] [0,0,0,0,1,1,1,1,0,0,0,0] [0,0,0,0,1,0,0,1,0,0,0,0] [0,0,0,0,1,1,1,1,0,0,0,0]
JavaScript
Imperative
Version #1.
<lang javascript>
// matkronprod.js
// Prime function:
// mkp arrow function: Return the Kronecker product of the a and b matrices.
// Note: both a and b must be matrices, i.e., 2D rectangular arrays.
mkp=(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t;
// Helper functions:
// Log title and matrix mat to console
function matl2cons(title,mat) {console.log(title); console.log(mat.join`\n`)}
// Print title to document
function pttl2doc(title) {document.write(''+title+'
')}
// Print title and matrix mat to document
function matp2doc(title,mat) {
document.write(''+title+':
'); for (var i = 0; i < mat.length; i++) { document.write(' '+mat[i].join(' ')+'
'); }
} </lang>
- Required tests
<lang html> <html><head>
<title>Kronecker product: Sample 1 (from Wikipedia) and Sample 2</title> <script src="matkronprod.js"></script> <script> var mr,ttl='Kronecker product of A and B matrices'; [ {a:[[1,2],[3,4]],b:[[0,5],[6,7]] }, {a:[[0,1,0],[1,1,1],[0,1,0]],b:[[1,1,1,1],[1,0,0,1],[1,1,1,1]] } ].forEach(m=>{ console.log(ttl); pttl2doc(ttl); matl2cons('A',m.a); matp2doc('A',m.a); matl2cons('B',m.b); matp2doc('B',m.b); mr=mkp(m.a,m.b); matl2cons('A x B',mr); matp2doc('A x B',mr); }) </script>
</head><body></body> </html> </lang>
- Output:
Console and page results
Kronecker product of A and B matrices A 1,2 3,4 B 0,5 6,7 A x B 0,5,0,10 6,7,12,14 0,15,0,20 18,21,24,28 Kronecker product of A and B matrices A 0,1,0 1,1,1 0,1,0 B 1,1,1,1 1,0,0,1 1,1,1,1 A x B 0,0,0,0,1,1,1,1,0,0,0,0 0,0,0,0,1,0,0,1,0,0,0,0 0,0,0,0,1,1,1,1,0,0,0,0 1,1,1,1,1,1,1,1,1,1,1,1 1,0,0,1,1,0,0,1,1,0,0,1 1,1,1,1,1,1,1,1,1,1,1,1 0,0,0,0,1,1,1,1,0,0,0,0 0,0,0,0,1,0,0,1,0,0,0,0 0,0,0,0,1,1,1,1,0,0,0,0
Version #2.
This version is more understandable for sure.
<lang javascript> // matkronprod2.js // Prime function: // mkp2(): Return the Kronecker product of the a and b matrices // Note: both a and b must be matrices, i.e., 2D rectangular arrays. function mkp2(a,b) {
var m=a.length, n=a[0].length, p=b.length, q=b[0].length; var rtn=m*p, ctn=n*q; var r=new Array(rtn); for (var i=0; i<rtn; i++) {r[i]=new Array(ctn) for (var j=0;j<ctn;j++) {r[i][j]=0} } for (var i=0; i<m; i++) { for (var j=0; j<n; j++) { for (var k=0; k<p; k++) { for (var l=0; l<q; l++) { r[p*i+k][q*j+l]=a[i][j]*b[k][l]; }}}}//all4forend return(r);
}
// Helper functions:
// Log title and matrix mat to console
function matl2cons(title,mat) {console.log(title); console.log(mat.join`\n`)}
// Print title to document
function pttl2doc(title) {document.write(''+title+'
')}
// Print title and matrix mat to document
function matp2doc(title,mat) {
document.write(''+title+':
'); for (var i=0; i < mat.length; i++) { document.write(' '+mat[i].join(' ')+'
'); }
} </lang>
- Required tests
<lang html> <html><head>
<title>Kronecker product v.2: Sample 1 (from Wikipedia) and Sample 2</title> <script src="matkronprod2.js"></script> <script> var mr,ttl='Kronecker product of A and B matrices'; [ {a:[[1,2],[3,4]],b:[[0,5],[6,7]] }, {a:[[0,1,0],[1,1,1],[0,1,0]],b:[[1,1,1,1],[1,0,0,1],[1,1,1,1]] } ].forEach(m=>{ console.log(ttl); pttl2doc(ttl); matl2cons('A',m.a); matp2doc('A',m.a); matl2cons('B',m.b); matp2doc('B',m.b); mr=mkp2(m.a,m.b); matl2cons('A x B',mr); matp2doc('A x B',mr); }) </script>
</head><body></body> </html> </lang>
- Output:
Console and page results
Output is identical to Version #1 above.
Functional
ES6
(As JavaScript is now widely embedded in non-browser contexts, a non-HTML string value is returned here, rather than invoking a DOM method, which will not always be available to a JavaScript interpreter) <lang javascript>(() => {
'use strict';
// GENERIC FUNCTIONS ------------------------------------------------------
// concat :: a -> [a] const concat = xs => [].concat.apply([], xs);
// concatMap :: (a -> [b]) -> [a] -> [b] const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// 2 or more arguments // curry :: Function -> Function const curry = (f, ...args) => { const go = xs => xs.length >= f.length ? (f.apply(null, xs)) : function () { return go(xs.concat([].slice.apply(arguments))); }; return go([].slice.call(args, 1)); };
// map :: (a -> b) -> [a] -> [b] const map = curry((f, xs) => xs.map(f));
// show :: a -> String const show = x => JSON.stringify(x); //, null, 2);
// transpose :: a -> a const transpose = xs => xs[0].map((_, col) => xs.map(row => row[col]));
// unlines :: [String] -> String const unlines = xs => xs.join('\n');
// KRONECKER PRODUCT OF TWO MATRICES --------------------------------------
// kprod :: Num -> Num -> Num const kprod = (xs, ys) => concatMap( m => map(concat, transpose(m)), map(map(f(ys)), xs) );
// (* n) mapped over each element in a matrix // f :: Num -> Num -> Num const f = curry((mx, n) => map(map(x => x * n), mx));
// TEST ------------------------------------------------------------------- return unlines(map(rows => unlines(map(show, rows)), [ kprod([ [1, 2], [3, 4] ], [ [0, 5], [6, 7] ]), [], // One empty output line kprod([ [0, 1, 0], [1, 1, 1], [0, 1, 0] ], [ [1, 1, 1, 1], [1, 0, 0, 1], [1, 1, 1, 1] ]) ]));
})();</lang>
- Output:
[0,5,0,10] [6,7,12,14] [0,15,0,20] [18,21,24,28] [0,0,0,0,1,1,1,1,0,0,0,0] [0,0,0,0,1,0,0,1,0,0,0,0] [0,0,0,0,1,1,1,1,0,0,0,0] [1,1,1,1,1,1,1,1,1,1,1,1] [1,0,0,1,1,0,0,1,1,0,0,1] [1,1,1,1,1,1,1,1,1,1,1,1] [0,0,0,0,1,1,1,1,0,0,0,0] [0,0,0,0,1,0,0,1,0,0,0,0] [0,0,0,0,1,1,1,1,0,0,0,0]
Kotlin
<lang scala>// version 1.1.1 (JVM)
typealias Matrix = Array<IntArray>
fun kroneckerProduct(a: Matrix, b: Matrix): Matrix {
val m = a.size val n = a[0].size val p = b.size val q = b[0].size val rtn = m * p val ctn = n * q val r: Matrix = Array(rtn) { IntArray(ctn) } // all elements zero by default for (i in 0 until m) for (j in 0 until n) for (k in 0 until p) for (l in 0 until q) r[p * i + k][q * j + l] = a[i][j] * b[k][l] return r
}
fun printMatrix(text: String, m: Matrix) {
println(text) for (i in 0 until m.size) println(m[i].contentToString()) println()
}
fun printAll(a: Matrix, b: Matrix, r: Matrix) {
printMatrix("Matrix A:", a) printMatrix("Matrix B:", b) printMatrix("Kronecker product:", r)
}
fun main(args: Array<String>) {
var a: Matrix var b: Matrix var r: Matrix a = arrayOf( intArrayOf(1, 2), intArrayOf(3, 4) ) b = arrayOf( intArrayOf(0, 5), intArrayOf(6, 7) ) r = kroneckerProduct(a, b) printAll(a, b, r)
a = arrayOf( intArrayOf(0, 1, 0), intArrayOf(1, 1, 1), intArrayOf(0, 1, 0) ) b = arrayOf( intArrayOf(1, 1, 1, 1), intArrayOf(1, 0, 0, 1), intArrayOf(1, 1, 1, 1) ) r = kroneckerProduct(a, b) printAll(a, b, r)
}</lang>
- Output:
Matrix A: [1, 2] [3, 4] Matrix B: [0, 5] [6, 7] Kronecker product: [0, 5, 0, 10] [6, 7, 12, 14] [0, 15, 0, 20] [18, 21, 24, 28] Matrix A: [0, 1, 0] [1, 1, 1] [0, 1, 0] Matrix B: [1, 1, 1, 1] [1, 0, 0, 1] [1, 1, 1, 1] Kronecker product: [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
PARI/GP
<lang parigp> \\ Print title and matrix mat rows. 4/17/16 aev matprows(title,mat)={print(title); for(i=1,#mat[,1], print(mat[i,]))} \\ \\ Create and return the Kronecker product of the a and b matrices. 4/17/16 aev matkronprod(a,b,pflg=0)={ my(m=#a[,1],n=#a[1,],p=#b[,1],q=#b[1,],r,rtn,ctn); rtn=m*p; ctn=n*q; if(pflg,print(" *** Kronecker product - a: ",m," x ",n," b: ",p," x ",q," result r: ",rtn," x ",ctn)); r=matrix(rtn,ctn); for(i=1,m, for(j=1,n, for(k=1,p, for(l=1,q,
r[p*(i-1)+k,q*(j-1)+l]=a[i,j]*b[k,l];
))));\\all4fend if(pflg,print(r)); return(r); } {\\ Requireq tests: my(a,b,r); \\ Sample 1 a=[1,2;3,4]; b=[0,5;6,7]; r=matkronprod(a,b); matprows("Sample 1 result:",r); \\ Sample 2 a=[0,1,0;1,1,1;0,1,0]; b=[1,1,1,1;1,0,0,1;1,1,1,1]; r=matkronprod(a,b); matprows("Sample 2 result:",r); } </lang>
- Output:
Sample 1 result: [0, 5, 0, 10] [6, 7, 12, 14] [0, 15, 0, 20] [18, 21, 24, 28] Sample 2 result: [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]