Multiplication de matrice symbolique

26

Il existe de nombreuses façons différentes d'expliquer la multiplication matricielle. Je vais m'en tenir à une seule figure car je pense que la plupart des gens ici la connaissent (et la figure est très descriptive). Si vous voulez des informations plus détaillées, je vous suggère de visiter l' article Wikipedia ou l'explication sur WolframMathWorld .

Explication simple:

Supposons que vous ayez deux matrices, A et B , où A est 3 par 2 et B est 2 par 3. Si vous effectuez une multiplication matricielle sur ces matrices, AB ou BA, vous obtiendrez les résultats ci-dessous:

entrez la description de l'image ici

Défi:

Implémentez la multiplication matricielle symbolique dans votre langue. Vous devez prendre deux matrices en entrée, où chaque élément des matrices est représenté par un caractère ASCII non blanc (points de code 33-126). Vous devez sortir le produit de ces matrices.

Règles concernant la sortie:

Un produit de deux entrées ne doit avoir aucun symbole entre les deux. Il est ab, non a*b, a·b, times(a,b)ou quelque chose de similaire. Ce n'est aapas le cas a^2.

La somme des termes doit avoir un espace (code ASCII point 32) entre les deux. Ce n'est a bpas le cas a+b, plus(a,b)ou quelque chose de similaire.

La justification de ces deux règles est la suivante: tous les caractères non blancs sont autorisés comme symboles dans les matrices, donc les utiliser comme symboles mathématiques serait désordonné. Donc, ce que vous pourriez normalement écrire a*b+c*dsera ab cd.

Vous pouvez choisir l'ordre des conditions. ab cd, dc abet cd baparlent mathématiquement de la même manière, vous pouvez donc également choisir l'ordre ici. L'ordre n'a pas besoin d'être cohérent tant qu'il est mathématiquement correct.

Règles concernant le formatage matriciel:

Une matrice peut être entrée dans le format de votre choix, à l'exception d'une seule chaîne sans délimiteur entre les lignes (c'est parce que la sortie serait complètement foirée). Les deux matrices doivent être entrées au même format. Tous les exemples ci-dessous sont des moyens valides d'entrer et de sortir une matrice.

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

"a,b\nc,d"

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

[a, b]
[c, d]

Je suis conscient que cela autorise beaucoup de formats qui auront l'air désordonnés, mais le défi consiste à multiplier les matrices, pas à formater la sortie.

Règles générales:

  • Vous pouvez supposer une entrée valide. La multiplication matricielle sera toujours possible avec les dimensions données.
  • Il n'y aura que deux matrices.
  • Vous pouvez supposer que les matrices ne sont pas vides
  • Les fonctions intégrées sont acceptées (mais probablement un peu lourdes en raison des exigences de formatage).
  • Vous pouvez bien sûr utiliser des caractères d'échappement dans l'entrée si nécessaire ( \'au lieu de ').
  • Toute méthode d'entrée et de sortie standard est OK .

Cas de test:

Les deux matrices d'entrée sont affichées avec une ligne vide entre les deux. La sortie est affichée après Output:. Lorsqu'il y a deux matrices de sortie, c'est juste pour montrer d'autres sorties qui seraient acceptées.

Cas de test # 1

Inputs:
[a]

[b]

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

Cas de test # 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]

Cas de test n ° 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 votre réponse aux règles exigeant ab cdau lieu de a*b+c*dest: vous devez éviter les formats d'entrée / sortie encombrants , alors je voudrais noter que les formats d'entrée et de sortie sont très flexibles. Le fait que vous ne puissiez pas utiliser *et +pour les produits et les sommes pourrait rendre plus difficile l'utilisation d'un simple intégré, mais je ne considère pas cette chose négative.

Stewie Griffin
la source
Pour une fonction, est-ce que prendre deux tableaux 2D de chaînes et renvoyer un tableau 2D de chaînes est acceptable?
Dennis
Oui pas de problème. Mais les dimensions doivent correspondre, vous ne pouvez pas transposer la deuxième entrée. Cela avait-il du sens?
Stewie Griffin du
Oui, merci d'avoir clarifié. Une dernière question: pourrais-je également prendre un tableau 2D de caractères en entrée et renvoyer un tableau 2D de chaînes?
Dennis
@Dennis, j'ai écrit: "Les deux matrices doivent être entrées sur le même format." J'ai oublié de mentionner la matrice de sortie là-bas, donc je vais la garder comme ça. Les entrées doivent être au même format mais vous pouvez avoir un format de sortie différent. (Je n'aime pas vraiment cette solution, mais je ne veux pas changer de choses maintenant, je pense qu'il y a déjà une réponse qui a différents formats d'entrée et de sortie)
Stewie Griffin
Si vous voulez dire la réponse Ruby, j'ai vérifié et celle-ci fonctionne aussi bien avec des chaînes que des caractères.
Dennis

Réponses:

9

Haskell , 62 61 octets

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

Essayez-le en ligne! Exemple d'utilisation:

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

J'ai trouvé un moyen d'obtenir une transposefonction dans un octet plus court que d'utiliser l'importation:

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

Ancienne version avec importation: (62 octets)

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

Essayez-le en ligne!

Ceci est assez similaire à ma réponse à la multiplication matricielle non symbolique : a!b=[sum.zipWith(*)r<$>transpose b|r<-a]remplacer la multiplication (*)par une concaténation de chaînes (++)et sumavec unwordslaquelle concatène une liste de chaînes avec un espace entre les deux. L'import est nécessaire pour la transposefonction, donc dans l'ensemble la transposition de la deuxième matrice utilise la moitié des octets ...


Ancienne version sans importation: (64 octets)

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

Essayez-le en ligne!

L'importation et la transposefonction prenant tellement d'octets, j'ai essayé de résoudre la tâche sans importer. Jusqu'à présent, cette approche s'est avérée être plus longue de deux octets, mais elle pourrait être plus jouable au golf. Edit: L'autre approche en haut bat désormais l'importation!

La compréhension de la liste [s:t|_:s:t<-b]obtient les queues non vides des listes b, en utilisant juste [t|_:t<-b]pour obtenir les queues serait 4 octets plus court (même en battant la version d'importation) mais ajoutez une ligne vide comme ["","",""]à la matrice qui, je suppose, n'est pas autorisée.

Laikoni
la source
6

Mathematica, 36 octets

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

Innerest une généralisation de Mathematica Dot(c'est-à-dire le produit matriciel / vectoriel habituel). Il généralise le produit scalaire en vous permettant de fournir deux fonctions fet g, qui seront utilisées à la place de la multiplication et de l'addition habituelles, respectivement. Nous remplaçons la multiplication par #<>#2&(qui joint les deux caractères en une seule chaîne) et l'addition avec StringRiffle@*List, qui enveloppe d'abord tous les sommets dans une liste, puis les StringRifflejoint avec des espaces.

On pourrait potentiellement utiliser l' Dotopérateur .puis transformer le résultat, mais le problème est que des choses comme celles-ci "a"*"a"seraient immédiatement transformées en "a"^2(même chose pour les sommes), ce qui serait ennuyeux de les séparer à nouveau.

Martin Ender
la source
6

Rubis, 61 octets

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

Exemple d'exécution:

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
}}}
Poignée de porte
la source
4

Clojure, 53 octets

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

Exécution avec arguments [["a" "b"]["c" "e"]]et [["f" "g"]["h" "i"]]retours ((("af" "bh") ("ag" "bi")) (("cf" "eh") ("cg" "ei"))). C'est en fait plus court que la version numérique .

NikoNyrh
la source
3

Dyalog APL , 10 octets

Prend les matrices de caractères comme arguments gauche et droit. Renvoie une matrice de listes de caractères. (APL représente les chaînes sous forme de listes de caractères.)

{∊⍺' '⍵}.,

TryAPL en ligne!

Le produit intérieur normal est en APL +.×, mais l'addition et la multiplication peuvent être n'importe quelles fonctions, en particulier:

L'addition a été remplacée par
{ une fonction anonyme:
 la
⍺ ' ' ⍵ liste aplatie composée de l'argument de gauche, d'un espace et de l'argument de droite
}

La multiplication a été remplacée par la concaténation, ,

Adam
la source
2

Gelée , 7 octets

Z;"þK€€

Il s'agit d'un lien dyadique qui prend B et A comme arguments (dans cet ordre) et renvoie AB . L'entrée et la sortie se présentent sous la forme de tableaux 2D de chaînes, qui sont en réalité des tableaux 3D de caractères. Un octet supplémentaire pourrait être enregistré en prenant des tableaux 2D de caractères en entrée. Je ne sais pas si c'est permis.

Essayez-le en ligne!

Il est un peu difficile de déterminer ce que Jelly fait sous le capot lorsque les cordes sont impliquées, car il fait beaucoup d'éclatement avant l'impression. C'est ainsi que Jelly représente les entrées et les sorties en interne.

Comment ça marche

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
la source
2

Prolog,> 256 octets

J'utilise {_ | _} qui est un findall / 3, _ [_, _] qui est un argument arg / 3, et sum (_) qui est un agrégat. Ils peuvent tous être utilisés à l'intérieur est / 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) }.

Avec les définitions supplémentaires pour les prédicats susmentionnés et le non standard est / 2 qui peut retourner plus que des nombres, son sûr> 256 octets.

Nombres transfinis
la source
1

JavaScript (ES6), 65 octets

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

Prend l'entrée comme deux tableaux 2D de caractères et renvoie un tableau 2D de chaînes. Ajoutez 10 octets pour prendre en charge l'entrée sous forme de deux tableaux 1D de chaînes.

Neil
la source
1

Pyth, 14 octets

clQmj;sMCd*QCE

Un programme qui prend en entrée deux listes de caractères bidimensionnels séparés par des sauts de ligne et imprime une liste bidimensionnelle de chaînes.

Suite de tests

Comment ça marche

[Explication à venir plus tard]

TheBikingViking
la source
1

Pip , 17 octets

{Y Zb{a._JsMy}Ma}

Il s'agit d'une fonction qui prend deux listes imbriquées de chaînes (à un seul caractère) et renvoie une liste imbriquée de chaînes. Essayez-le en ligne! (avec deux cas de test).

Explication

Les arguments d'une {}fonction délimitée sont affectés aux variables locales ade e. Le premier argument d'une fonction lambda est représenté par _.

{               }  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
la source