En mathématiques, la multiplication matricielle ou le produit matriciel est une opération binaire qui produit une matrice à partir de deux matrices. La définition est motivée par des équations linéaires et des transformations linéaires sur des vecteurs, qui ont de nombreuses applications en mathématiques appliquées, en physique et en génie. Plus en détail, si A est une matrice n × m et B est une matrice m × p, leur produit matriciel AB est une matrice n × p, dans lequel les m entrées sur une ligne de A sont multipliées par les m entrées vers le bas a colonnes de B et additionnées pour produire une entrée de AB. Lorsque deux transformations linéaires sont représentées par des matrices, le produit matriciel représente la composition des deux transformations.

^{Source: Wikipedia}

En d'autres termes, pour multiplier deux matrices, par exemple:

1 2 3   1 4
2 3 4 × 3 1 = 
3 4 5   4 6

Tout d'abord, prenez la ligne numéro 1 dans la première matrice, la colonne numéro 1 dans la deuxième matrice et multipliez 1par 1, 2par 3et 3par 4.

1 × 1 = 1
2 × 3 = 6
3 × 4 = 12

Maintenant, ajoutez-les ensemble pour obtenir votre premier article:

1 2 3   1 4   19
2 3 4 × 3 1 = 
3 4 5   4 6

Pour le deuxième numéro de la première colonne du résultat, vous devrez prendre la ligne numéro 2 au lieu de la ligne numéro 1 et faire la même chose.

1 × 2 = 2
3 × 3 = 9
4 × 4 = 16
      = 27

Après avoir fait la première colonne entière, le résultat ressemble à ceci:

1 2 3   1 4   19
2 3 4 × 3 1 = 27
3 4 5   4 6   35

Maintenant, refaites exactement la même chose, mais prenez la deuxième colonne au lieu de la première, ce qui donne:

1 2 3   1 4   19 24
2 3 4 × 3 1 = 27 35
3 4 5   4 6   35 46

Ta tâche

Étant donné deux matrices (dimensions maximales 200x200), contenant des nombres compris entre -10000 et 10000, où le nombre de colonnes sur la première est égal au nombre de lignes sur la seconde, multipliez la première par la seconde. (La multiplication matricielle n'est pas commutative.)

Vous pouvez prendre des entrées et donner des sorties sous forme de tableau de tableaux (ou équivalent), de matrice (si votre langue a ce format) ou de chaîne multiligne.

Vous ne pouvez pas utiliser de modules intégrés pour la multiplication de matrice.

Cas de test

1 2   1 2 3 4 5    13 16 19 22 25
3 4 × 6 7 8 9 10 = 27 34 41 48 55
5 6                41 52 63 74 85

2 3   3 5   15 13
3 4 × 3 1 = 21 19

5 3            11    27
1 3      1 3   7     15
9 3    × 2 4 = 15    39
1 -1000        -1999 -3997

N'oubliez pas qu'il s'agit de code-golf , donc le code avec le moins d'octets gagne.

Gelée , 7 5 octets

Z×þḅ1

Prend B et A comme arguments et renvoie A × B .

Essayez-le en ligne!

Comment ça fonctionne

Z×þḅ1  Main link. Left argument: B. Right argument: A

Z      Zip; transpose B's rows and columns.
 ×þ    Table multiplication; multiply all columns of B (rows of B's transpose) by
       all rows of A, element by element. Results are grouped by the rows of A.
   ḅ1  Unbase 1; compute the sum of all flat arrays in the result.

05AB1E , 13 octets

vyU²øvyX*O})ˆ

Essayez-le en ligne!

Explication

v               # for each row in the first matrix
 yU             # save the row in X
   ²øv          # for each row in the transposition of the second matrix
      yX*       # multiply the rows
         O      # sum the elements of the resulting row
          }     # end inner loop
           )    # wrap elements of the new row in a list
            ˆ   # push to global list
                # implicitly output global list

Python 2, 69 66 octets

Cela suit juste la formule standard, mais lambda-d pour plus de concision :) Le code non golfé est extrêmement simple!

lambda x,y:[[sum(map(int.__mul__,r,c))for c in zip(*y)]for r in x]

^{Merci à Alexi Torhamo pour avoir économisé 3 octets! :)}

Code non golfé:

x = [[1,2],[3,4],[5,6]]
y = [[1,2,3,4,5],[6,7,8,9,10]]

output = []
for row in x:
    nrow = []
    for col in zip(*y):                             # zip(*[]) transposes a matrix
        nrow += [sum(a*b for a,b in zip(row,col))]  # multiplication for each pair summed
    output += [nrow]

print output

J, 13 9 octets

4 octets enregistrés grâce aux miles!

[:+/*"#:~

Ceci est une fourche plafonnée:

[: +/ *"#:~

Ce qui équivaut à:

[: +/ (*"#:)~
[: +/ (*"_ 1 0)~

Qui effectue la multiplication souhaitée; ceux-ci sont ensuite additionnés.

Avec un produit scalaire intégré, 5 octets: +/ .*

Cas de test

   f =: [: +/ *"#:~
   (3 3$1 2 3 2 3 4 3 4 5)f(3 2$1 4 3 1 4 6)
19 24
27 35
35 46
   (3 3$1 2 3 2 3 4 3 4 5);(3 2$1 4 3 1 4 6)
+-----+---+
|1 2 3|1 4|
|2 3 4|3 1|
|3 4 5|4 6|
+-----+---+
   (2 2$2 3 3 4)f(2 2$3 5 3 1)
15 13
21 19
   (2 2$2 3 3 4);(2 2$3 5 3 1)
+---+---+
|2 3|3 5|
|3 4|3 1|
+---+---+

Haskell , 57 56 54 octets

e=[]:e
z=zipWith
a!b=[sum.z(*)r<$>foldr(z(:))e b|r<-a]

Essayez-le en ligne!

Usage:

Prelude> [[1,2],[3,4],[5,6]] ! [[1,2,3,4,5],[6,7,8,9,10]]
[[13,16,19,22,25],[27,34,41,48,55],[41,52,63,74,85]]

foldr(zipWith(:))eavec e=[]:eest une forme plus courte de transpose.

Haskell , 45 octets

map.(foldr1(z(+)).).flip(z$map.(*))
z=zipWith

Essayez-le en ligne!

Prend les arguments dans l'ordre inverse.

R, 66 octets

function(A,B)apply(B,2,function(i)apply(A,1,function(j)sum(j*i)))

Fonction sans nom prenant deux matrices R en entrée et retourne le produit. Il utilise applyce qui est utilisé pour appliquer des fonctions à travers les marges des tableaux. Cela fonctionne comme un doublefor boucle dans ce cas: pour chaque colonne de Bet pour chaque ligne de A, retourne la somme des produits (vectorisés).

Comparer à l'approche pure pour la boucle ( 101octets):

function(A,B){M=matrix(NA,m<-nrow(A),n<-ncol(B));for(i in 1:n)for(j in 1:m)M[j,i]=sum(A[j,]*B[,i]);M}

Mathematica, 20 octets

Inner[1##&,##,Plus]&

Fonction anonyme. Prend deux listes de nombres de rang 2 en entrée et renvoie une liste de nombres de rang 2 en sortie. Pour les curieux, Innerc'est une fonction qui fait une application matricielle-multiplication de deux fonctions à deux tenseurs.

C #, 168 167 octets

(A,B)=>{int n=A.Length,p=B[0].Length,i=0,j=0,k=0,s;var R=new int[n,p];while(i++<n)for(j=0;j<p;){s=0;for(k=0;k<A[0].Length;)s+=A[i][k]*B[k++][j];R[i,j++]=s;}return R;};

Merci @Mukul Kumar d'avoir sauvé 1 octet, la boucle while était en fait plus courte cette fois: P

Programme complet avec cas de test:

using System;
class Matrix
{
    static void Main()
    {
        Func<int[][], int[][], int[,]> a = null;

        a = (A,B)=>
        {
            int n=A.Length,p=B[0].Length,i=0,j=0,k=0,s;
            var R=new int[n,p];
            while(i++<n)
                for(j=0;j<p;)
                {
                    s=0;
                    for(k=0;k<A[0].Length;)
                        s+=A[i][k]*B[k++][j];
                    R[i,j++]=s;
                }
            return R;
        };

        int[,] t1 = a(new int[][] { new int[] { 1, 2 }, new int[] { 3, 4 }, new int[] { 5, 6 } },
            new int[][] { new int[] { 1, 2, 3, 4, 5 }, new int[] { 6, 7, 8, 9, 10 } } );
        int[,] t2 = a(new int[][] { new int[] { 2, 3 }, new int[] { 3, 4 } },
            new int[][] { new int[] { 3, 5 }, new int[] { 3, 1 } });
        int[,] t3 = a(new int[][] { new int[] { 5, 3 }, new int[] { 1, 3 }, new int[] { 9, 3 }, new int[] { 1, -1000 } },
            new int[][] { new int[] { 1, 3 }, new int[] { 2, 4 } });

        Console.WriteLine(IsCorrect(t1, new int[,] { { 13, 16, 19, 22, 25 }, { 27, 34, 41, 48, 55 }, { 41, 52, 63, 74, 85 } } ));
        Console.WriteLine(IsCorrect(t2, new int[,] { { 15, 13 }, { 21, 19 } } ));
        Console.WriteLine(IsCorrect(t3, new int[,] { { 11, 27 }, { 7, 15 }, { 15, 39 }, { -1999, -3997 } } ));

        Console.Read();
    }

    static bool IsCorrect(int[,] answer, int[,] valid)
    {
        if (answer.Length != valid.Length)
            return false;
        for (int i = 0; i < answer.GetLength(0); i++)
            for (int j = 0; j < answer.GetLength(1); j++)
                if (answer[i, j] != valid[i, j])
                    return false;
        return true;
    }
}

MATL , 12 11 octets

7L&!*Xs6Be!

Les matrices sont entrées en utilisant ;comme séparateur de lignes.

Essayez-le en ligne!

La multiplication matricielle sans la fonction intégrée faisait partie de ma réponse à Showcase of languages . Cependant, lorsque j'ai essayé de réutiliser le code d'origine pour cette réponse, j'ai réalisé qu'il y avait un bogue (la sortie du vecteur ligne a été incorrectement convertie en vecteur colonne). Ceci est maintenant corrigé, ici et là. Pour une explication du fonctionnement du code, consultez l'article référencé (extrait de longueur 11).

C ++ 14, 173 168 156 156 146 octets

• -5 octets pour le retour via le paramètre de référence
• -12 octets pour utiliser foreach et C.back()compter suri
• -10 octets à supprimer C.clear()et nécessitant Cd'être vide au démarrage

En tant que lambda sans nom:

[](auto A,auto B,auto&C){int j,k,s=B[0].size();for(auto a:A){C.emplace_back(s);for(j=-1;++j<s;)for(k=-1;++k<B.size();C.back()[j]+=a[k]*B[k][j]);}}

Nécessite une entrée et une sortie car vector<vector<int>>et la sortie doit être vide au préalable.

Non golfé:

auto f=
[](auto A, auto B, auto&C){
 int j,k,s=B[0].size();
 for (auto a:A){
  C.emplace_back(s);
  for (j=-1;++j<s;)
   for (k=-1;++k<B.size();
    C.back()[j]+=a[k]*B[k][j]
   );
 }
}
;

Échantillon:

int main() {
 using M=std::vector<std::vector<int>>;
 M a = {
  {1,2,3},
  {2,3,4},
  {3,4,5},
 };
 M b = {
  {1,4},
  {3,1},
  {4,6},
 };
 M c;
 f(a,b,c);
 for (auto&r:c){
  for (auto&i:r) std::cout << i << ", ";
  std::cout << "\n";
 }
}

Husk , 7 6 octets

mMδṁ*T

Veuillez noter l'ordre des arguments, essayez-le en ligne!

-1 octet grâce à @Zgarb!

Explication

Fondamentalement, juste ce que dit la définition de la multiplication matricielle:

mMδṁ*T  -- takes arguments in reverse order, eg: [[1],[0],[-1]] [[1,2,3],[4,5,6]]
     T  -- transpose the first argument: [[1,0,-1]] [[1,2,3],[4,5,6]]
m       -- map the following function (example element [1,0,-1])
 M      --   map the following function applied to [1,0,-1] (example element [1,2,3])
  δṁ    --     accumulate a sum of element-wise..
    *    --    ..multiplication: -2
          -- [[-2],[-2]]

JavaScript (ES6), 66 octets

(a,b)=>a.map(c=>b[0].map((_,i)=>b.reduce((s,d,j)=>s+d[i]*c[j],0)))

C #, 131 octets

(A,B)=>new List<List<int>>(A.Select(x=>new List<int>
    (B[0].Select((f,i)=>B.Select(r=>r[i])).Select(y=>x.Zip(y,(p,q)=>p*q).Sum()))));

J'ai volé la solution de Yodle en supposant que je pouvais écrire cela plus efficacement en utilisant LINQ (par opposition aux boucles). A pris quelques tentatives, mais l'a quelque peu écrasé.

Ici, il se décompose un peu:

a = (A, B) => new List<List<int>>(
            from x in A
            select new List<int>(
                from y in B.First().Select((f, i) => B.Select(r => r.ElementAt(i)))
                select x.Zip(y, (p, q) => p * q).Sum()));

Le seul vrai « truc » est ici la matrice transposée, B.First().Select((f, i) => B.Select(r => r.ElementAt(i))). Une fois que nous avons transposé la deuxième matrice, nous avons deux tableaux A[i,x]et B[j,x]. Prenez le produit cartésien ( i*j) et zippez chacun de ces xtableaux de longueur ensemble.

Code de test:

using System;
class Matrix
{
    static void Main()
    {
        Func<int[][], int[][], List<List<int>>> a = null;
        a = (A, B) => new List<List<int>>(A.Select(x => new List<int>(B[0].Select((f, i) => B.Select(r => r[i])).Select(y => x.Zip(y, (p, q) => p * q).Sum()))));

        List<List<int>> t1 = a(new int[][] { new int[] { 1, 2 }, new int[] { 3, 4 }, new int[] { 5, 6 } },
            new int[][] { new int[] { 1, 2, 3, 4, 5 }, new int[] { 6, 7, 8, 9, 10 } });
        List<List<int>> t2 = a(new int[][] { new int[] { 2, 3 }, new int[] { 3, 4 } },
            new int[][] { new int[] { 3, 5 }, new int[] { 3, 1 } });
        List<List<int>> t3 = a(new int[][] { new int[] { 5, 3 }, new int[] { 1, 3 }, new int[] { 9, 3 }, new int[] { 1, -1000 } },
            new int[][] { new int[] { 1, 3 }, new int[] { 2, 4 } });

        Console.WriteLine(IsCorrect(t1, new int[,] { { 13, 16, 19, 22, 25 }, { 27, 34, 41, 48, 55 }, { 41, 52, 63, 74, 85 } }));
        Console.WriteLine(IsCorrect(t2, new int[,] { { 15, 13 }, { 21, 19 } }));
        Console.WriteLine(IsCorrect(t3, new int[,] { { 11, 27 }, { 7, 15 }, { 15, 39 }, { -1999, -3997 } }));

        Console.Read();
    }

    static bool IsCorrect(List<List<int>> answer, int[,] valid)
    {
        if (answer.Count*answer[0].Count != valid.Length)
            return false;
        for (int i = 0; i < answer.Count; i++)
            for (int j = 0; j < answer[0].Count; j++)
                if (answer[i][j] != valid[i, j])
                    return false;
        return true;
    }

}

Haskell , 49 octets

z=zipWith
m a=map(\x->foldr1(z(+))$z(map.(*))x a)

Essayez-le en ligne!

L'entrée et la sortie sont des listes de colonnes. Mappe chaque colonne de la deuxième matrice à cette ligne, zippée avec les colonnes de la première matrice et mise à l'échelle chacune, additionnée en tant que vecteur.

Je pense qu'il doit y avoir un bon moyen de rendre ce point gratuit et d'économiser une poignée d'octets, mais je ne le vois pas encore.

Javascript, 128 octets

m=(a,b)=>{$=[];q=0;for(x in b){c=[];j=0;for(y in a[0]){_=i=0;for(z in b[0]){_+=a[i][j]*b[q][i];i++}c.push(_);j++}$.push(c);q++}}

Vous obtenez le résultat en vérifiant simplement $ - c'est un peu de la triche, mais bon, cela a économisé quelques octets.

PHP, 110 octets

function f($a,$b){foreach($a as$n=>$x)foreach($b as$m=>$y)foreach($y as$p=>$v)$z[$n][$p]+=$v*$x[$m];return$z;}

Trois boucles pour les tableaux elfiques. C'est tellement simple ... mais il n'y a pas grand-chose au golf.

En fait , 14 octets

Suggestions de golf bienvenues! Essayez-le en ligne!

┬@;l)∙`i♀*Σ`M╡

Ungolfing

         Implicit input A, then B.
┬        Transpose B's rows and columns. Call it B_T.
@        Swap A to TOS.
;l)      Get len(A) and move to BOS for later.
∙        Push the Cartesian product of A and B_T. Call it cart_prod.
`...`M   Map the following function over cart_prod. Variable xs.
  i        Flatten xs onto the stack, getting a row of A and column of B.
  ♀*       Multiply each element of A_row by each element of B_column.
  Σ        Sum the resulting list to get an element of A*B.
         The result of the map returns every element of A*B, but in one flat list.
╡        Push a list containing len(A) non-overlapping sublists of A*B.
         This separates A*B into rows.
         Implicit return.

C, 618 octets

M(char*a,char*b){char*P[2];P[0]=malloc(strlen(a));P[1]=malloc(strlen(b));for(int A=0;A<strlen(a);A++){P[0][A]=a[A];};for(int B=0;B<strlen(b);B++){P[1][B]=b[B];};int H[200][200],B[200][200];int O,N,m,J;for(int Y=0;Y<2;Y++){int y=0,z=0,r=0;char j[7];int p=strlen(P[Y]);for(int i=0;i<=p;i++){if(P[Y][i]==' '||P[Y][i]==','||i==p){(Y<1)?H[y][z]=atoi(j):(B[y][z]=atoi(j));memset(j,'\0',4);(P[Y][i]==' ')?z++:y++;z=(P[Y][i]==',')?0:z;r=0;}else{j[r]=P[Y][i];r++;};};(Y<1)?O=z+1,N=y:(m=y,J=z+1);};for(int U=0;U<N;U++){for(int F=0;F<J;F++){int T=0;for(int d=0;d<O;d++){T+=H[U][d]*B[d][F];};printf("%d ",T);T=0;};printf("\n");};}

Une fonction nommée et par loin la soumission la plus longue ici, en partie due au fait que la conversion des entrées du tableau de caractères en tableaux entiers en 2D prend le plus d'octets, et aussi parce que je n'ai pas joué au golf en C depuis le plus longtemps. Je travaille toujours à raccourcir cela autant que possible, et tous les conseils pour le faire sont très appréciés.

Maintenant, avec cela à l'écart, cela prend une entrée via la ligne de commande avec les deux matrices représentées par deux chaînes, chacune contenant les lignes séparées par des virgules et chaque ligne représentée par des entiers séparés par des espaces. Par exemple, les matrices:

   1 2 3     44 52
A= 4 5 6  B= 67 -79
   7 8 9     83 90

serait entré comme:

./a.out "1 2 3,4 5 6,7 8 9" "44 52,67 -79,83 90"

La matrice résultante est sortie dans STDOUT sous la forme d'une chaîne multiligne. Par exemple, la sortie de l'entrée ci-dessus serait:

 427 164 
1009 353 
1591 542 

Clojure, 60 octets

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

Beaucoup d'octets dépensés pour transposer le 2ème argument.

Rubis , 59 octets

->m,n{m.map{|r|n.transpose.map{|c|r.zip(c).sum{|i,j|i*j}}}}

Essayez-le en ligne!