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)
(cons (cons prefix (car items))
(add-prefix prefix (cdr items)))))

(define (reverse-list items)
(if (null? 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 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, If you want to add some formula to web, just use <img src=" LaTeX text" />. You can use this method to add any math formula to any website.

Wednesday, February 28, 2007

Hello, Programmer Club

In my college there is a group -- Programmer Club. Most of the members like computer programming. Since I am good at it, I became a VIP not for a long time. In fact, I am better at algorithm design and analytics. Dijkstra (how to pronounce?), a computer scientist, said: program=data structure+algorithm. Algorithm is interesting. When I take a long time to solve a difficulty problem, I feel excited. A few years ago, I often visited ACM, USACO. There were a lot of interesting problem.
So I want to try share my experience with my partner. So far, there are three groupmates like programming very much, Zhao Yupei, Li Zhijei and Zhou Wei. Especially Yupei, she has enough patience to study programming. I think she is a genius.
Programming is exciting, so is getting together with my groupmates.
Gook luck!