## Saturday, July 28, 2007

### A Scheme Program -- Generating Gray Binary Code

See The Art of Computer Programming, Volume 4, Generating All Tuples and Permutations, Fascicle 2 by Donald E. Knuth.

Formula (5) on Page 3 told us a recursive algorithm for generating all permutations of 0 and 1 in Gray Binary Code order. I use Scheme language to implement the algorithm. It looks simple and elegant. See below:

`; Add a prefix to each element in items.; e.g. If the items is ((1 3 4)(2 4 5)) and the prefix is 0,; the result is ((0 1 3 4)(0 2 4 5))(define (add-prefix prefix items)  (if (null? items)      items      (cons (cons prefix (car items))            (add-prefix prefix (cdr items)))))(define (reverse-list items)  (if (null? items)      items      (append (reverse-list(cdr items))              (list (car items))))); Generating all permutation of 0 and 1; in Gray binary code order(define (gray-binary-code n)  (if (= n 0)      '(())      (append (add-prefix 0 (gray-binary-code (- n 1)))              (add-prefix 1 (reverse-list                               (gray-binary-code (- n 1)))))))`

For example, execute (gray-binary-code 3), we will get:
`(list (list 0 0 0) (list 0 0 1) (list 0 1 1) (list 0 1 0) (list 1 1 0) (list 1 1 1) (list 1 0 1) (list 1 0 0))`

I am very glad to write this program as a Scheme beginner. Scheme language tastes good!

### LaTeX on Web

Look at these:

$\LaTeX$

$x_{1,2}=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$

They are all produced by LaTeX. LaTeX is a publishing tool which is very fit for people to handle articles which contain a lot of math formula. But LaTeX produces DVI or PDF files, instead of images. So they can not be insert into a web page directly. Furtunately, there is a free software, mimeTeX, a CGI program, can produce image files through LaTeX strings. It runs at server, so it can provide images for any web pages.
Even better, there is a free public mimeTeX service, www.forkosh.dreamhost.com. If you want to add some formula to web, just use <img src="http://www.forkosh.dreamhost.com/mimetex.cgi?Your LaTeX text" />. You can use this method to add any math formula to any website.