Code Golf Asked by Stewie Griffin on February 7, 2021
Related, but very different.
In the examples below, $A$ and $B$ will be $2times2$ matrices, and the matrices are one-indexed.
A Kronecker product has the following properties:
A⊗B = A(1,1)*B A(1,2)*B
A(2,1)*B A(2,2)*B
= A(1,1)*B(1,1) A(1,1)*B(1,2) A(1,2)*B(1,1) A(1,2)*B(1,2)
A(1,1)*B(2,1) A(1,1)*B(2,2) A(1,2)*B(2,1) A(1,2)*B(2,2)
A(2,1)*B(1,1) A(2,1)*B(1,2) A(2,2)*B(1,1) A(2,2)*B(1,2)
A(2,2)*B(2,1) A(2,2)*B(1,2) A(2,2)*B(2,1) A(2,2)*B(2,2)
Challenge: Given two matrices, $A$ and $B$, return $Aotimes B$.
Test cases:
A =
1 2
3 4
B =
5 6
7 8
A⊗B =
5 6 10 12
7 8 14 16
15 18 20 24
21 24 28 32
B⊗A =
5 10 6 12
15 20 18 24
7 14 8 16
21 28 24 32
------------------------
A =
1
2
B =
1 2
A⊗B =
1 2
2 4
------------------------
A =
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
B =
1 1
0 1
A⊗B =
16 16 2 2 3 3 13 13
0 16 0 2 0 3 0 13
5 5 11 11 10 10 8 8
0 5 0 11 0 10 0 8
9 9 7 7 6 6 12 12
0 9 0 7 0 6 0 12
4 4 14 14 15 15 1 1
0 4 0 14 0 15 0 1
B⊗A =
16 2 3 13 16 2 3 13
5 11 10 8 5 11 10 8
9 7 6 12 9 7 6 12
4 14 15 1 4 14 15 1
0 0 0 0 16 2 3 13
0 0 0 0 5 11 10 8
0 0 0 0 9 7 6 12
0 0 0 0 4 14 15 1
------------------------
A = 2
B = 5
A⊗B = 10
function(x,y,`+`=array)aperm(apply(x,1:2,`*`,y)+c(w<-dim(y),v<-dim(x)),c(1,3,2,4))+v*w
Reimplementation of .kronecker
and outer
for matrices. I do think there's a golfier approach out there, maybe using 6 bytes golfed using apply
?apply
and array
thanks to Dominic van Essen!
The builtins are %x%
for kronecker(A,B,"*")
and %o%
for outer(A,B,"*")
.
function(A,B){l=list()
a=dim(A)
for(i in 1:a[2]-1)l[[i+1]]<-do.call(rbind,lapply(A,"*",B)[1:a+a[2]*i])
do.call(cbind,l)}
Naive approach: calculate the subarrays $a_{ij}B$ and bind them together in the appropriate order. There are probably golfs here too, but I don't think it'll be shorter than the one above.
Answered by Giuseppe on February 7, 2021
{⍪/,/⍺×⊂⍵}
{ ... } ⍝ dfn that takes ⍺=A and ⍵=B
⍺×⊂⍵ ⍝ Product of each element of A with all of matrix B
⍝ Gives a nested array: an matrix of matrices
./ ⍝ Join rows
⍪/ ⍝ Join columns
Answered by fireflame241 on February 7, 2021
This is one possible implementation.
[:,./^:2*/
This is a similar implementation, but instead uses J's ability to define ranks. It applies *
between each element on the LHS with the entire RHS.
[:,./^:2*"0 _
f =: <either definition>
(2 2 $ 1 2 3 4) f (2 2 $ 5 6 7 8)
5 6 10 12
7 8 14 16
15 18 20 24
21 24 28 32
(2 1 $ 1 2) f (1 2 $ 1 2)
1 2
2 4
2 f 5
10
Answered by miles on February 7, 2021
A%B=hvcat(sum(A^0),map(a->a*B,A')...)
For matrices A and B, map(a->a*B,A')
computes the Kronecker product A⊗B.
The result is a vector of matrix blocks with the dimensions of B.
We have to transpose A (with '
) since matrices are stored in column-major order.
sum(A^0)
computes the sum of all entries of the identity matrix of A's dimensions. For an n×n matrix A, this yields n.
With first argument n, hvcat
concatenates n matrix blocks horizontally, and the resulting (larger) blocks vertically.
Answered by Dennis on February 7, 2021
Saved 41 bytes, thanks to FryAmTheEggman!
@(A,B)cell2mat(arrayfun(@(n)n*B,A,'un',0))
Breakdown
arrayfun
is a disguised for-loop that multiplies n*B
, for a variable n
defined by the second argument. This works because looping through a 2D matrix is the same as looping through a vector. I.e. for x = A
is the same as for x = A(:)
.
'un',0
is equivalent to the more verbose 'UniformOutput', False
, and specifies that the output contains cells instead of scalars.
cell2mat
is used to convert the cells back to a numeric matrix, which is then outputted.
Answered by Stewie Griffin on February 7, 2021
Straightforward implementation with nested looping
(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t
Test
f=(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t
console.log=x=>O.textContent+=x+'n'
function show(label, mat)
{
console.log(label)
console.log(mat.join`n`)
}
;[
{a:[[1,2],[3,4]],b:[[5,6],[7,8]] },
{a:[[1],[2]],b:[[1,2]]},
{a:[[16,2,3,13],[5,11,10,8],[9,7,6,12],[4,14,15,1]],b:[[1,1],[0,1]]},
{a:[[2]],b:[[5]]}
].forEach(t=>{
show('A',t.a)
show('B',t.b)
show('A⊗B',f(t.a,t.b))
show('B⊗A',f(t.b,t.a))
console.log('-----------------')
})
<pre id=O></pre>
Answered by edc65 on February 7, 2021
JEsMs*RRRRJ
Translation of Jelly answer, which is based on Büttner's Algorithm (ü
pronounced when trying to make an ee
sound [as in meet] in the mouth-shape of an oo
sound [as in boot]).
B⊗A
in the same number of bytesJEsMs*LRLRJ
Answered by Leaky Nun on February 7, 2021
×€€;"/€;/
Uses Büttner's Algorithm (ü
pronounced when trying to make an ee
sound [as in meet] in the mouth-shape of an oo
sound [as in boot]).
The ;"/€;/
is inspired by Dennis Mitchell. It was originally Z€F€€;/
(which costs one more byte).
Answered by Leaky Nun on February 7, 2021
{ffff*::.+:~}
This is an unnamed block that expects two matrices on top of the stack and leaves their Kronecker product in their place.
This is just the Kronecker product part from the previous answer, therefore I'm here just reproducing the relevant parts of the previous explanation:
Here is a quick overview of CJam's infix operators for list manipulation:
f
expects a list and something else on the stack and maps the following binary operator over the list, passing in the other element as the second argument. E.g. [1 2 3] 2 f*
and 2 [1 2 3] f*
both give [2 4 6]
. If both elements are lists, the first one is mapped over and the second one is used to curry the binary operator.:
has two uses: if the operator following it is unary, this is a simple map. E.g. [1 0 -1 4 -3] :z
is [1 0 1 4 3]
, where z
gets the modulus of a number. If the operator following it is binary, this will fold the operator instead. E.g. [1 2 3 4] :+
is 10
..
vectorises a binary operator. It expects two lists as arguments and applies the operator to corresponding pairs. E.g. [1 2 3] [5 7 11] .*
gives [5 14 33]
.ffff* e# This is the important step for the Kronecker product (but
e# not the whole story). It's an operator which takes two matrices
e# and replaces each cell of the first matrix with the second matrix
e# multiplied by that cell (so yeah, we'll end up with a 4D list of
e# matrices nested inside a matrix).
e# Now the ffff* is essentially a 4D version of the standard ff* idiom
e# for outer products. For an explanation of ff*, see the answer to
e# to the Kronecker sum challenge.
e# The first ff maps over the cells of the first matrix, passing in the
e# second matrix as an additional argument. The second ff then maps over
e# the second matrix, passing in the cell from the outer map. We
e# multiply them with *.
e# Just to recap, we've essentially got the Kronecker product on the
e# stack now, but it's still a 4D list not a 2D list.
e# The four dimensions are:
e# 1. Columns of the outer matrix.
e# 2. Rows of the outer matrix.
e# 3. Columns of the submatrices.
e# 4. Rows of the submatrices.
e# We need to unravel that into a plain 2D matrix.
::.+ e# This joins the rows of submatrices across columns of the outer matrix.
e# It might be easiest to read this from the right:
e# + Takes two rows and concatenates them.
e# .+ Takes two matrices and concatenates corresponding rows.
e# :.+ Takes a list of matrices and folds .+ over them, thereby
e# concatenating the corresponding rows of all matrices.
e# ::.+ Maps this fold operation over the rows of the outer matrix.
e# We're almost done now, we just need to flatten the outer-most level
e# in order to get rid of the distinction of rows of the outer matrix.
:~ e# We do this by mapping ~ over those rows, which simply unwraps them.
Answered by Martin Ender on February 7, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP