• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Python Puzzle #1: List multiplication

Contents

  • Basic concepts
  • Question
  • Answer

Basic concepts

Image you had to multiply two small matrices in Python. You could just use the definition of a matrix product:

$A, B \in \mathbb{R}^{n \times n}$: $C = A \cdot B, C \in \mathbb{R}^{n \times n}$ where the components of C are definied by $c_{i,j} = \sum_{k=1}^n a_{i,k} \cdot b_{k, j}$

Note that this means: $\begin{pmatrix} 1 & 2 \ 3 & 4 \end{pmatrix} \cdot \begin{pmatrix} 5 & 6 \ 7 & 8 \end{pmatrix} = \begin{pmatrix} 19 & 22 \ 43 & 50 \end{pmatrix}$

You might also have heard of Pythons overloaded multiplication:

print([0] * 4)
print([[0] * 4] * 4)
print("abc" * 4)

Output:

[0, 0, 0, 0]
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
abcabcabcabc

Question

What do you think does the following piece of Python-Code print?

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def standardMatrixProduct(A, B):
    n = len(A)
    C = [[0] * n] * n
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C


A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(standardMatrixProduct(A, B))

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Answer

[[32, 32], [32, 32]]

Python creates only one list and makes pointers to it!

So this is one that works:

def standardMatrixProduct(A, B):
    n = len(A)
    C = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(C)
                C[i][j] += A[i][k] * B[k][j]
    return C

Published

Jun 18, 2012
by Martin Thoma

Category

Code

Tags

  • Programming 52
  • puzzle 22
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor