Multiplicación simbólica de matrices

26

Hay muchas formas diferentes de explicar la multiplicación de matrices. Me quedaré con una sola figura, ya que creo que la mayoría de las personas aquí están familiarizadas con ella (y la figura es muy descriptiva). Si desea información más detallada, le sugiero que visite el artículo de Wikipedia o la explicación sobre WolframMathWorld .

Explicación simple:

Suponga que tiene dos matrices, A y B , donde A es 3 por 2 y B es 2 por 3. Si realiza la multiplicación de matrices en estas matrices, ya sea AB o BA , obtendrá los resultados a continuación:

ingrese la descripción de la imagen aquí

Reto:

Implemente la multiplicación simbólica de matrices en su idioma. Deberá tomar dos matrices como entrada, donde cada elemento de las matrices está representado por un carácter ASCII sin espacios en blanco (puntos de código 33-126). Debe generar el producto de estas matrices.

Reglas con respecto a la salida:

Un producto de dos entradas no tendrá ningún símbolo en el medio. Es ab, no a*b, a·b, times(a,b)o algo similar. Es aa, no a^2.

La suma de términos debe tener un espacio (punto de código ASCII 32) en el medio. Es a b, no a+b, plus(a,b)o algo similar.

La justificación de esas dos reglas es: todos los caracteres que no sean espacios en blanco están permitidos como símbolos en las matrices, por lo que usarlos como símbolos matemáticos sería complicado. Entonces, lo que normalmente podrías escribir como a*b+c*dserá ab cd.

Puede elegir el orden de los términos. ab cd, dc aby cd bamatemáticamente hablando lo mismo, así que puedes elegir el orden aquí también. El orden no necesita ser consistente siempre que sea matemáticamente correcto.

Reglas sobre el formato de matriz:

Se puede ingresar una matriz en el formato que desee, excepto una sola cadena sin delimitadores entre filas (esto se debe a que la salida estaría completamente desordenada). Ambas matrices deben ingresarse en el mismo formato. Todos los ejemplos a continuación son formas válidas de ingresar y emitir una matriz.

"ab;cd"     <- This will look awful, but it's still accepted.

"a,b\nc,d"

[[a,b],[c,d]] 

[a, b]
[c, d]

Soy consciente de que esto permite muchos formatos que se verán desordenados, pero el desafío consiste en multiplicar matrices, no formatear la salida.

Reglas generales:

  • Puede asumir una entrada válida. La multiplicación de matrices siempre será posible con las dimensiones dadas.
  • Solo habrá dos matrices.
  • Puede suponer que las matrices no están vacías
  • Se aceptan funciones incorporadas (pero probablemente un poco engorrosas debido a los requisitos de formato).
  • Por supuesto, puede usar caracteres de escape en la entrada si es necesario (en \'lugar de ').
  • Cualquier método de entrada y salida estándar está bien .

Casos de prueba:

Las dos matrices de entrada se muestran con una línea vacía en el medio. La salida se muestra después Output:. Cuando hay dos matrices de salida, es solo para mostrar otras salidas que serían aceptadas.

Caso de prueba n. ° 1

Inputs:
[a]

[b]

Output:
[ab]
[ba]      <- Also OK

Caso de prueba n. ° 2

Inputs:
[a, b]
[1, 4] 
[y, {]

[%, 4, 1] 
[a, b, c]

Output:    
[a% ba, a4 bb, a1 bc] 
[1% 4a, 14 4b, 11 4c] 
[y% {a, y4 {b, y1 {c]

Caso de prueba # 3:

Inputs:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 1, 2, 3]
[4, 5, 6, 7]

[a]
[b]
[c]
[d]

Output:
[1a 2b 3c 4d]
[5a 6b 7c 8d]
[9a 1b 2c 3d]
[4a 5b 6c 7d]

[d4 c3 b2 a1]      <-- Also OK
[d8 c7 b6 a5]
[1b 9a c2 3d]
[a4 b5 d7 6c]

Si su respuesta a las reglas sobre requerir en ab cdlugar de a*b+c*des: debe evitar formatos de entrada / salida engorrosos , entonces me gustaría tener en cuenta que los formatos de entrada y salida son muy flexibles. El hecho de que no pueda usar *y +para productos y sumas puede dificultar el uso de un simple incorporado, pero no considero eso negativo.

Stewie Griffin
fuente
Para una función, ¿es aceptable tomar dos matrices 2D de cadenas y devolver una matriz 2D de cadenas?
Dennis
Si no hay problema. Pero las dimensiones deben coincidir, no se puede transponer la segunda entrada. ¿Eso tiene sentido?
Stewie Griffin
Lo hizo, gracias por aclarar. Una última pregunta: ¿podría también tomar una matriz 2D de caracteres como entrada y devolver una matriz 2D de cadenas?
Dennis
@ Dennis, escribí: "Ambas matrices deben ingresarse en el mismo formato". Olvidé mencionar la matriz de salida allí, así que la mantendré así. Las entradas deben estar en el mismo formato, pero es posible que tenga un formato de salida diferente. (I no me gusta mucho esa solución, pero no quiero cambiar las cosas ahora, creo que hay una respuesta ya que tiene diferentes formatos de entrada y de salida)
Stewie Griffin
Si te refieres a la respuesta de Ruby, verifiqué y esa funciona igual de bien con cadenas en lugar de caracteres.
Dennis

Respuestas:

9

Haskell , 62 61 bytes

e=[]:e
a!b=[unwords.zipWith(++)r<$>foldr(zipWith(:))e b|r<-a]

Pruébalo en línea! Ejemplo de uso:

Prelude> [["a","b"],["c","e"]] ! [["f","g"],["h","i"]]
[["af bh","ag bi"],["cf eh","cg ei"]]

Encontré una manera de obtener una transposefunción en un byte más corto que usar la importación:

import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

Versión anterior con importación: (62 bytes)

import Data.List
a!b=[unwords.zipWith(++)r<$>transpose b|r<-a]

Pruébalo en línea!

Esto es bastante similar a mi respuesta a la multiplicación matricial no simbólica : a!b=[sum.zipWith(*)r<$>transpose b|r<-a]sustituyendo la multiplicación (*)por concatenación de cadenas (++)y sumcon la unwordsque concatena una lista de cadenas con un espacio en el medio. La importación es necesaria para la transposefunción, por lo que, en general, la transposición de la segunda matriz utiliza la mitad de los bytes ...


Versión anterior sin importación: (64 bytes)

a![]=[];a!b=(unwords.zipWith(++)[h|h:_<-b]<$>a):a![s:t|_:s:t<-b]

Pruébalo en línea!

Con la importación y la transposefunción ocupando tantos bytes, intenté resolver la tarea sin importar. Hasta ahora, este enfoque resultó ser dos bytes más largo, pero podría ser más fácil de jugar. Editar: ¡El otro enfoque en la parte superior ahora supera a la importación!

La comprensión de la lista [s:t|_:s:t<-b]obtiene las colas no vacías de las listas b, usar solo [t|_:t<-b]para obtener las colas sería 4 bytes más corto (incluso superando la versión de importación), pero agrega una fila vacía como ["","",""]a la matriz que supongo que no está permitido.

Laikoni
fuente
6

Mathematica, 36 bytes

Inner[#<>#2&,##,StringRiffle@*List]&

Inneres una generalización de Mathematica Dot(es decir, el producto matriz / vector habitual). Generaliza el producto de puntos al permitirle proporcionar dos funciones fy g, que se utilizarán en lugar de la multiplicación y suma habituales, respectivamente. Estamos reemplazando la multiplicación con #<>#2&(que une los dos caracteres en una sola cadena) y la suma con StringRiffle@*List, que primero envuelve todos los sumandos en una lista y luego los StringRiffleune con espacios.

Uno podría potencialmente usar el Dotoperador .y luego transformar el resultado, pero el problema es que cosas como "a"*"a"se transformarían inmediatamente "a"^2(lo mismo para sumas), lo que sería molesto volver a separar.

Martin Ender
fuente
6

Ruby, 61 bytes

->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}

Ejecución de muestra:

main(0):007> ->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}[[[?a, ?b], [?1, ?4], [?y, ?{]], [[?%, ?4, ?1], [?a, ?b, ?c]]]
=> [["a% ba", "a4 bb", "a1 bc"], ["1% 4a", "14 4b", "11 4c"], ["y% {a", "y4 {b", "y1 {c"]]
->a,b{
a.map{|x|            # for each row of a
b.transpose.map{|y|  # and for each column of b
x.zip(y)             # match up corresponding elements
.map(&:join)         # join each pair together
*' '                 # join the entire thing on space
}}}
Pomo de la puerta
fuente
4

Clojure, 53 bytes

#(for[a %](for[b(apply map vector %2)](map str a b)))

Ejecutando con argumentos [["a" "b"]["c" "e"]]y [["f" "g"]["h" "i"]]devoluciones ((("af" "bh") ("ag" "bi")) (("cf" "eh") ("cg" "ei"))). Esto es en realidad más corto que la versión numérica .

NikoNyrh
fuente
3

Dyalog APL , 10 bytes

Toma matrices de caracteres como argumentos izquierdo y derecho. Devuelve la matriz de listas de caracteres. (APL representa cadenas como listas de caracteres).

{∊⍺' '⍵}.,

TryAPL en línea!

El producto interno normal está en APL +.×, pero la suma y la multiplicación pueden ser cualquier función, en particular:

La adición ha sido reemplazada por
{ una función anónima:
 la
⍺ ' ' ⍵ lista aplanada que consiste en el argumento izquierdo, un espacio y el argumento derecho
}

La multiplicación ha sido reemplazada por concatenación, ,

Adán
fuente
2

Jalea , 7 bytes

Z;"þK€€

Este es un enlace diádico que toma B y A como argumentos (en ese orden) y devuelve AB . La entrada y la salida están en forma de matrices 2D de cadenas, que en realidad son matrices 3D de caracteres. Se podría guardar un byte adicional tomando matrices 2D de caracteres como entrada. No estoy seguro si eso está permitido.

Pruébalo en línea!

Es un poco difícil determinar qué hace Jelly debajo del capó cuando hay cuerdas involucradas, ya que salpica mucho antes de imprimir. Así es como Jelly representa la entrada y salida internamente.

Cómo funciona

Z;"þK€€  Dyadic link. Left argument: B. Right argument: A

Z        Zip/transpose B.
 ;"þ     Table vectorized concatenation; for each row in B' and each row in A,
         concatenate the corresponding strings.
    K€€  Join the arrays that correspond to the rows of A by spaces.
Dennis
fuente
2

Prólogo,> 256 bytes

Estoy usando {_ | _} que es un findall / 3, _ [_, _] que es un poco de arg / 3, y sum (_) que es un agregado. Todos se pueden usar dentro de / 2:

*(X, Y, Z) :- functor(Y, matrice, _), L is len(X[1]), L =:= len(Y), !,
   M is len(X), N is len(Y[1]),
   Z is { { sum({ X[J,K] * Y[K,I] | between(1,L,K) })
                                  | between(1,N,I) }
                                  | between(1,M,J) }.

Junto con las definiciones adicionales para los predicados antes mencionados y el no estándar es / 2 que puede devolver más que números, es seguro> 256 bytes.

Números Transfinitos
fuente
1

JavaScript (ES6), 65 bytes

(a,b)=>a.map(c=>b[0].map((_,j)=>c.map((e,i)=>e+b[i][j]).join` `))

Toma datos como dos matrices 2D de caracteres y devuelve una matriz 2D de cadenas. Agregue 10 bytes para admitir la entrada como dos matrices 1D de cadenas.

Neil
fuente
1

Pyth, 14 bytes

clQmj;sMCd*QCE

Un programa que toma la entrada de dos listas de caracteres bidimensionales separadas por una nueva línea e imprime una lista bidimensional de cadenas.

Banco de pruebas

Cómo funciona

[Explicación más tarde]

TheBikingViking
fuente
1

Pip , 17 bytes

{Y Zb{a._JsMy}Ma}

Esta es una función que toma dos listas anidadas de cadenas (de un solo carácter) y devuelve una lista anidada de cadenas. Pruébalo en línea! (con dos casos de prueba).

Explicación

Los argumentos a una {}función delimitada se asignan a las variables locales aa e. El primer argumento de una función lambda está representado por _.

{               }  Define a function:
   Zb              Zip rows of b, transposing it
 Y                 Yank into global variable y for access in nested function
     {       }Ma   To the rows of a, map this function:
           My       To the rows of y (i.e. columns of b), map this function:
      a._           Concatenate, itemwise, the current row of a and row of y
         Js         Join the resulting list on space
                   The result of the outer map operation is returned
DLosc
fuente