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:

People should read this.

Post a Comment