Hitung jumlah Kronecker dari dua matriks

9

Dalam contoh di bawah ini, Adan Bakan menjadi 2-by-2 matriks, dan matriks satu-diindeks.

Sebuah Kronecker produk memiliki sifat sebagai berikut:

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)

Sebuah Kronecker sum memiliki sifat sebagai berikut:

A⊕B = A⊗Ib + Ia⊗B

Iadan Ibapakah matriks identitas dengan dimensi Adan Bmasing - masing. Adan Bmatriks persegi. Catat itu Adan Bbisa dari berbagai ukuran.

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)

Diberi dua matriks persegi, Adan B, hitung jumlah Kronecker dari dua matriks tersebut.

  • Ukuran matriks setidaknya akan menjadi 2-by-2. Ukuran maksimum adalah apa pun yang dapat ditangani oleh komputer / bahasa Anda secara default, tetapi 5-by-5input minimum (output 5 MB).
  • Semua nilai input akan berupa bilangan bulat non-negatif
  • Fungsi bawaan yang menghitung jumlah Kronecker atau produk Kronecker tidak diizinkan
  • Secara umum: Aturan standar tentang format I / O, program & fungsi, celah dll.

Kasus uji:

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
sumber

Jawaban:

2

Jelly , 26 21 20 19 byte

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

Input adalah daftar dua daftar 2D, output adalah daftar 2D tunggal. Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

æ*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
sumber
Begitu banyak euro ... programmu kaya!
Luis Mendo
5

CJam, 40 39 38 byte

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

Format input adalah daftar yang berisi Adan Bsebagai daftar 2D, mis

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

Format output adalah daftar 2D gaya CJam tunggal.

Suite uji. (Dengan format output yang lebih mudah dibaca.)

Penjelasan

Kode ini adalah latihan operator majemuk (atau infiks). Ini umumnya berguna untuk manipulasi array, tetapi tantangan ini memperburuk kebutuhan mereka. Berikut ini gambaran singkatnya:

  • fmengharapkan daftar dan sesuatu yang lain di stack dan memetakan operator biner berikut dari daftar, meneruskan elemen lain sebagai argumen kedua. Misalnya [1 2 3] 2 f*dan 2 [1 2 3] f*keduanya memberi [2 4 6]. Jika kedua elemen adalah daftar, yang pertama dipetakan dan yang kedua digunakan untuk menjelajah operator biner.
  • :memiliki dua kegunaan: jika operator mengikutinya unary, ini adalah peta sederhana. Misalnya [1 0 -1 4 -3] :zadalah [1 0 1 4 3], di mana zmendapatkan modulus nomor. Jika operator mengikutinya adalah biner, ini akan melipat operator sebagai gantinya. Misalnya [1 2 3 4] :+adalah 10.
  • .membuat vektor operator biner. Ini mengharapkan dua daftar sebagai argumen dan berlaku operator untuk pasangan yang sesuai. Misalnya [1 2 3] [5 7 11] .*memberi [5 14 33].

Perhatikan bahwa :itu sendiri selalu merupakan operator unary, sedangkan fdan .mereka sendiri selalu operator biner. Ini dapat disarang sewenang-wenang (asalkan mereka memiliki hak arities). Dan itulah yang akan kami lakukan ...

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
sumber
fffffffffff apa yang ada di bumi ... Saya harap bisa bertahan bermain golf sehingga Anda bisa menjelaskannya pada akhirnya: P
FryAmTheEggman
@FryAmTheEggman :ffff*mungkin operator (senyawa) terpanjang yang pernah saya gunakan di CJam ... Untuk satu byte lagi, orang bisa lebih gila lagi: 9Yb2/Q~f.{\{,,_ff=}&}::ffff*:::.+::~:..+p(dan ya, akan menambahkan penjelasan ketika saya selesai bermain golf).
Martin Ender
4

J - 38 33 31 byte

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

Pemakaian

   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
mil
sumber
Menggunakan pembagian matriks akan gagal jika salah satu matriks adalah singular. Misalnya, (2 2 $ 1 2 3 4) f (2 2 $ 1 1 1 1)akan memunculkan kesalahan domain.
Dennis
@ Dennis tangkapan yang bagus, saya hanya menguji terhadap nilai acak ? 4 4 $ 100. Saya tidak yakin apakah ada cara untuk menggunakan komposisi angka dua x f&g y = (g x) f (g y)atau sesuatu yang lain di sini.
mil
2

Julia, 60 59 58 56 byte

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

Cobalah online!

Bagaimana itu bekerja

  • Untuk matriks A dan B , hitungmap(a->a*B,A') produk Kronecker A⊗B .

    Hasilnya adalah vektor dari blok matriks dengan dimensi B .

    Kita harus mengubah urutan A (dengan ') karena matriks disimpan dalam urutan kolom-utama.

  • Karena bitwise TIDAK dengan komplemen dua memenuhi identitas ~ n = - (n +1) untuk semua bilangan bulat n , kami memiliki itu - ~ -n = - (~ (-n)) = - ((- n) + 1) = 1 - n , jadi - ~ -0 = 1 dan - ~ -1 = 0 .

    Dengan cara ini fungsi anonim i->map(a->a*B^i,A'^-~-i)berlaku peta di atas untuk B⁰ (matriks identitas dengan B dimensi 's) dan A¹ = A ketika saya = 0 , dan untuk dan A⁰ ketika saya = 1 .

  • sum(i->map(a->a*B^i,A'^-~-i),0:1)menjumlahkan lebih dari {0,1} dengan fungsi anonim di atas, menghitung jumlah Kronecker A⊕B sebagai A¹⊗B⁰ + A⁰⊗B¹ .

    Hasilnya adalah vektor dari blok matriks dengan dimensi B .

  • sum(A^0)menghitung jumlah semua entri dari matriks identitas dimensi A. Untuk n × n matriks A , ini menghasilkan n .

  • Akhirnya, hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...)menyatukan blok matriks yang membentuk A⊕B .

    Dengan argumen pertama n , hvcatmenyatukan n blok matriks secara horizontal, dan blok yang dihasilkan (lebih besar) secara vertikal.

Dennis
sumber
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)}}}

Dalam program uji

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

Membutuhkan dua array 2D sebagai input dan mengembalikan array 2D.

Mungkin ada cara yang lebih baik untuk melakukan ini: menggunakan fungsi untuk menghindari pengulangan; menggunakan satu loop dan mencetak output. Akan melihat mereka nanti.

Level River St
sumber
0

JavaScript (ES6), 109

Dibangun di atas jawaban untuk tantangan lain

(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

Uji

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
sumber