Calcule la suma de Kronecker de dos matrices

9

En los ejemplos a continuación, Ay Bserán matrices de 2 por 2, y las matrices están indexadas en uno.

Un producto Kronecker tiene las siguientes propiedades:

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)

Una suma de Kronecker tiene las siguientes propiedades:

A⊕B = A⊗Ib + Ia⊗B

Iay Ibson las matrices de identidad con las dimensiones de Ay Brespectivamente. Ay Bson matrices cuadradas. Tenga en cuenta que Ay Bpuede ser de diferentes tamaños.

A⊕B =  A(1,1)+B(1,1)  B(1,2)         A(1,2)         0
        B(2,1)         A(1,1)+B(2,2)  0              A(1,2)
        A(2,1)         0              A(2,2)+B(1,1)  B(1,2)
        0              A(2,1)         B(2,1)         A(2,2)+B(2,2)

Dadas dos matrices cuadradas Ay Bcalcula la suma de Kronecker de las dos matrices.

  • El tamaño de las matrices será al menos 2-by-2. El tamaño máximo será lo que su computadora / idioma pueda manejar por defecto, pero la 5-by-5entrada mínima (salida de 5 MB).
  • Todos los valores de entrada serán enteros no negativos
  • Las funciones integradas que calculan la suma de Kronecker o los productos Kronecker no están permitidos
  • En general: Reglas estándar sobre formato de E / S, programa y funciones, lagunas, etc.

Casos de prueba:

A =
     1     2
     3     4
B =
     5    10
     7     9

A⊕B =
     6    10     2     0
     7    10     0     2
     3     0     9    10
     0     3     7    13

----

A =
    28    83    96
     5    70     4
    10    32    44
B =
    39    19    65
    77    49    71
    80    45    76

A⊕B =
    67    19    65    83     0     0    96     0     0
    77    77    71     0    83     0     0    96     0
    80    45   104     0     0    83     0     0    96
     5     0     0   109    19    65     4     0     0
     0     5     0    77   119    71     0     4     0
     0     0     5    80    45   146     0     0     4
    10     0     0    32     0     0    83    19    65
     0    10     0     0    32     0    77    93    71
     0     0    10     0     0    32    80    45   120

----

A =
    76    57    54
    76     8    78
    39     6    94
B =
    59    92
    55    29

A⊕B =
   135    92    57     0    54     0
    55   105     0    57     0    54
    76     0    67    92    78     0
     0    76    55    37     0    78
    39     0     6     0   153    92
     0    39     0     6    55   123
Stewie Griffin
fuente

Respuestas:

2

Jalea , 26 21 20 19 bytes

æ*9Bs2¤×€€/€S;"/€;/

La entrada es una lista de dos listas 2D, la salida es una sola lista 2D. Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

æ*9Bs2¤×€€/€S;"/€;/  Main link.
                     Argument: [A, B] (matrices of dimensions n×n and m×m)

      ¤              Evaluate the four links to the left as a niladic chain.
  9B                 Convert 9 to base 2, yielding [1, 0, 0, 1].
    s2               Split into sublists of length 2, yielding [[1, 0], [0, 1]].
æ*                   Vectorized matrix power.
                     This yields [[A¹, B⁰], [A⁰, B¹]], where B⁰ and A⁰ are the
                     identity matrices of dimensions m×m and n×n.
          /€         Reduce each pair by the following:
        €€             For each entry of the first matrix:
       ×                 Multiply the second matrix by that entry.
            S        Sum the two results, element by element.
                     This yields the Kronecker sum, in form of a n×n matrix of
                     m×m matrices.
               /€    Reduce each row of the outer matrix...
             ;"        by zipwith-concatenation.
                     This concatenates the columns of the matrices in each row,
                     yielding a list of length n of n×nm matrices.
                 ;/  Concatenate the lists, yielding a single nm×nm matrix.
Dennis
fuente
Tantos euros ... ¡tu programa es rico!
Luis Mendo
5

CJam, 40 39 38 bytes

9Yb2/q~f{.{_,,_ff=?}:ffff*::.+:~}:..+p

El formato de entrada es una lista que contiene Ay Bcomo listas 2D, p. Ej.

[[[1 2] [3 4]] [[5 10] [7 9]]]

El formato de salida es una única lista 2D de estilo CJam.

Banco de pruebas. (Con un formato de salida más legible).

Explicación

Este código es un ejercicio en operadores compuestos (o infijos). Estos son generalmente útiles para la manipulación de matrices, pero este desafío exacerbó la necesidad de ellos. Aquí hay un resumen rápido:

  • fespera una lista y algo más en la pila y asigna el siguiente operador binario sobre la lista, pasando el otro elemento como segundo argumento. Por ejemplo, [1 2 3] 2 f*y 2 [1 2 3] f*ambos dan[2 4 6] . Si ambos elementos son listas, el primero se asigna y el segundo se usa para cursar el operador binario.
  • :tiene dos usos: si el operador que lo sigue es unario, este es un mapa simple. Por ejemplo, [1 0 -1 4 -3] :zes [1 0 1 4 3], donde zobtiene el módulo de un número. Si el operador que lo sigue es binario, esto doblará al operador en su lugar. Por ejemplo, [1 2 3 4] :+es 10.
  • .vectoriza un operador binario. Espera dos listas como argumentos y aplica el operador a los pares correspondientes. Por ejemplo, [1 2 3] [5 7 11] .*da [5 14 33].

Tenga en cuenta que :en sí siempre es un operador unitario, mientras que fy .ellos mismos son siempre los operadores binarios. Estos pueden anidarse arbitrariamente (siempre que tengan las aridades correctas). Y eso es lo que haremos ...

9Yb      e# Push the binary representation of 9, i.e. [1 0 0 1].
2/       e# Split into pairs, i.e. [[1 0] [0 1]]. We'll use these to indicate
         e# which of the two inputs we turn into an identity matrix.
q~       e# Read and evaluate input, [A B].
f{       e# This block is mapped over the [[1 0] [0 1]] list, also pushing
         e# [A B] onto the stack for each iteration.
  .{     e#   The stack has either [1 0] [A B] or [0 1] [A B]. We apply this
         e#   block to corresponding pairs, e.g. 1 A and 0 B.
    _,   e#     Duplicate the matrix and get its length/height N.
    ,_   e#     Turn into a range [0 1 ... N-1] and duplicate it.
    ff=  e#     Double f on two lists is an interesting idiom to compute an
         e#     outer product: the first f means that we map over the first list
         e#     with the second list as an additional parameter. That means for
         e#     the remaining operator the two arguments are a single integer
         e#     and a list. The second f then maps over the second list, passing
         e#     in the the number from the outer map as the first parameter.
         e#     That means the operator following ff is applied to every possible
         e#     pair of values in the two lists, neatly laid out in a 2D list.
         e#     The operator we're applying is an equality check, which is 1
         e#     only along the diagonal and 0 everywhere else. That is, we've
         e#     created an NxN identity matrix.
    ?    e#     Depending on whether the integer we've got along with the matrix
         e#     is 0 or 1, either pick the original matrix or the identity.
  }
         e#   At this point, the stack contains either [A Ib] or [Ia B]. 
         e#   Note that A, B, Ia and Ib are all 2D matrices.
         e#   We now want to compute the Kronecker product of this pair.
  :ffff* e#   The ffff* 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#   The leading : is a fold operation, but it's a bit of a degenerate
         e#   fold operation that is only used to apply the following binary operator
         e#   to the two elements of a list.
         e#   Now the ffff* works essentially the same as the ff= above, but
         e#   we have to deal with two more dimensions now. The first ff maps
         e#   over the cells of the first matrix, passing in the second matrix
         e#   as an additional argument. The second ff then maps over the second
         e#   matrix, passing in the cell from the outer map. We multiply them
         e#   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.
}
         e# Phew: we've now got a list containing the two Kronecker products
         e# on the stack. The rest is easy, just perform pairwise addition.
:..+     e# Again, the : is a degenerate fold which is used to apply a binary
         e# operation to the two list elements. The ..+ then simply vectorises
         e# addition twice, such that we add corresponding cells of the 2D matrices.
p        e# All done, just pretty-print the matrix.
Martin Ender
fuente
fffffffffff qué demonios ... espero que sobreviva al golf para que pueda explicarlo eventualmente: P
FryAmTheEggman
@FryAmTheEggman :ffff*podría ser el operador (compuesto) más largo que he usado en CJam ... Sin embargo, un byte más podría volverse aún más loco: 9Yb2/Q~f.{\{,,_ff=}&}::ffff*:::.+::~:..+p(y sí, agregaré una explicación cuando termine de jugar al golf).
Martin Ender
4

J - 38 33 31 bytes

i=:=@i.@#
[:,./^:2(*/i)+(*/~i)~

Uso

   f =: [:,./^:2(*/i)+(*/~i)~
   (2 2 $ 1 2 3 4) f (2 2 $ 5 10 7 9)
6 10 2  0
7 10 0  2
3  0 9 10
0  3 7 13
   (3 3 $ 28 83 96 5 70 4 10 32 44) f (3 3 $ 39 19 65 77 49 71 80 45 76)
67 19  65  83   0   0 96  0   0
77 77  71   0  83   0  0 96   0
80 45 104   0   0  83  0  0  96
 5  0   0 109  19  65  4  0   0
 0  5   0  77 119  71  0  4   0
 0  0   5  80  45 146  0  0   4
10  0   0  32   0   0 83 19  65
 0 10   0   0  32   0 77 93  71
 0  0  10   0   0  32 80 45 120
   (3 3 $ 76 57 54 76 8 78 39 6 94) f (2 2 $ 59 92 55 29)
135  92 57  0  54   0
 55 105  0 57   0  54
 76   0 67 92  78   0
  0  76 55 37   0  78
 39   0  6  0 153  92
  0  39  0  6  55 123
millas
fuente
El uso de la división matricial fallará si una de las matrices es singular. Por ejemplo, (2 2 $ 1 2 3 4) f (2 2 $ 1 1 1 1)generará un error de dominio.
Dennis
@Dennis buena captura, solo estaba probando contra valores aleatorios ? 4 4 $ 100. No estoy seguro de si hay una manera de utilizar la composición de díada x f&g y = (g x) f (g y)o algo más aquí.
millas
2

Julia, 60 59 58 56 bytes

A%B=hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...)

Pruébalo en línea!

Cómo funciona

  • Para las matrices A y B , map(a->a*B,A')calcula el producto Kronecker A⊗B .

    El resultado es un vector de los bloques de la matriz con las dimensiones de B .

    Tenemos que transponer A (con ') ya que las matrices se almacenan en orden de columna mayor.

  • Como NO a nivel de bits con el complemento a dos satisface la identidad ~ n = - (n + 1) para todos los enteros n , tenemos que - ~ -n = - (~ (-n)) = - ((- n) + 1) = 1 - n , entonces - ~ -0 = 1 y - ~ -1 = 0 .

    De esta manera la función anónima i->map(a->a*B^i,A'^-~-i)se aplica el mapa de arriba a B⁰ (la matriz de identidad con B dimensiones 's) y A $ ¹ $ = A cuando i = 0 , y para B $ ¹ $ y A⁰ cuando i = 1 .

  • sum(i->map(a->a*B^i,A'^-~-i),0:1)suma más de {0,1} con la función anónima anterior, calculando la suma de Kronecker A⊕B como A¹⊗B⁰ + A⁰⊗B¹ .

    El resultado es un vector de los bloques de la matriz con las dimensiones de B .

  • sum(A^0)calcula la suma de todas las entradas de la matriz de identidad de las dimensiones de A. Para una matriz n × n A , esto produce n .

  • Finalmente, hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...)concatena los bloques de la matriz que forman A⊕B .

    Con el primer argumento n , hvcatconcatena n bloques de matriz horizontalmente y los bloques resultantes (más grandes) verticalmente.

Dennis
fuente
0

Ruby, 102

->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}

En programa de prueba

f=->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}

aa =[[1,2],[3,4]]
bb =[[5,10],[7,9]]
f[aa,bb].each{|e|p e}
puts

aa =[[28,83,96],[5,70,4],[10,32,44]]
bb =[[39,19,65],[77,49,71],[80,45,76]]
f[aa,bb].each{|e|p e}
puts

aa =[[76,57,54],[76,8,78],[39,6,94]]
bb =[[59,92],[55,29]]
f[aa,bb].each{|e|p e}
puts

Requiere dos matrices 2D como entrada y devuelve una matriz 2D.

Probablemente hay mejores formas de hacerlo: usar una función para evitar la repetición; usando un solo bucle e imprimiendo la salida. Los miraré más tarde.

Level River St
fuente
0

JavaScript (ES6), 109

Basado en la respuesta al otro desafío

(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),t.push(r=[]))),t=[])&&t

Prueba

f=(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),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,10],[7,9]]},
  {a:[[28,83,96],[5,70,4],[10,32,44]], b:[[39,19,65],[77,49,71],[80,45,76]]},
  {a:[[76,57,54],[76,8,78],[39,6,94]], b:[[59,92],[55,29]]}
].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>

edc65
fuente