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:





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.