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!

1 comment:

Denali said...

People should read this.