Tuesday 26 February 2008 — This is more than 15 years old. Be careful.

There’s something magical about complex algorithms. They take a hard problem and build a strong fence around it. Once you’ve got an implementation working, you don’t have to worry about what’s inside any more. Take the specifics of the problem at hand, drop them into the algorithm, and out pops an answer. It’s like a cartoon machine with lights and wheels on the outside, and magic happens on the inside.

I’ve been poking around looking at Python implementations of algorithms for solving. Roughly speaking, these tools take a system of constraints, and produce an answer comprising the values that satisfy the constraints. I’m sure there are more, but these are what I’ve turned up in a quick search.

¶ Simple Gauss-Jordan Elimination is a classic math technique for solving a system of linear equations. This works great, but is crying out to be implemented as a C extension.

¶ SMAWK (an awk-like acronym of the authors’ initials) finds the maxima in each row of a large matrix of values, provided the matrix is totally monotone. This sounds esoteric, but has applications in computational geometry and other areas. David Eppstein used it to implement Knuth’s paragraph wrapping algorithm, and if an algorithm lets you re-implement Knuth-Plass in 65 lines of Python, I’m guessing you have a powerful algorithm. David has a bunch of other algorithmic stuff for Python too.

¶ logilab-constraint and python-constraint are two Python implementations of constraint solvers. These seem to be good at discrete problems like solving Sudoku or eight queens. BTW: Roman Barták maintains a list of constraint system implementations which could be useful.

Beyond these, there are tons of fascinating techniques: simulated annealing (with some Python implementations), genetic algorithms (Python implementations), and optimization algorithms of all sorts.

## Comments

Iain10:57 AM on 26 Feb 2008I'm sure you linked to this because it's neat to see pure-python implementations. But anyone wanting to do serious work with matrices should use numpy and scipy. These use decent Fortran libraries for things like linear system solving.

Ned Batchelder11:25 AM on 26 Feb 2008Carlos Santos12:38 PM on 26 Feb 2008http://code.google.com/p/aima-python/

I believe there is also a debian package for this stuff (python-aima).

Pedro Lima5:25 PM on 27 Feb 2008http://abel.ee.ucla.edu/cvxopt

D. Kelson9:37 PM on 27 Feb 2008Didrik Pinte3:18 AM on 28 Feb 2008K. Hatch2:12 AM on 4 Mar 2008There is another application where python is invaluable because of the infinitely long integer capability. I wanted to solve electronic circuits symbolically (e.g. the answer is (R1*R2)/(R4+R5), not 4.6374853e-7). This required solving determinants with pure integers that can be huge. Python does a real nice job of that.

I am not a python programmer, so my code is very cumbersome and non-standard. But it works! I would like to see someone include a determinant library routine that does pure integer arithmetic, where the integers can be any size.

## Add a comment: