#-(and) "
P49 (**) Gray code.
An n-bit Gray code is a sequence of n-bit strings constructed
according to certain rules. For example,
n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].
Find out the construction rules and write a predicate with the
following specification:
% gray(N,C) :- C is the N-bit Gray code
Can you apply the method of \"result caching\" in order to make the
predicate more efficient, when it is to be used repeatedly?
"
;; In Lisp, we will instead implement a function (gray n) producing
;; the list of gray codes C(n).
;; Here is a solution giving the codes as strings of #\0 or #\1:
(defun gray (n)
(if (= 1 n)
(list "0" "1")
(let ((gray-1 (gray (1- n))))
(nconc (mapcar (lambda (code) (concatenate 'string "0" code))
gray-1)
(mapcar (lambda (code) (concatenate 'string "1" code))
(nreverse gray-1))))))
;; Since we call (gray (1- n)) only once per call to (gray n), there's
;; no gain in memoizing gray, unless it is called repeatitively, in
;; which case, memoizing could help as caching any other function.
;; (gray 3) --> ("000" "001" "011" "010" "110" "111" "101" "100")
;; Here is a version giving the codes as integers:
(defun gray (n)
(if (= 1 n)
(list 0 1)
(let ((gray-1 (gray (1- n))))
(nconc gray-1
(mapcar (lambda (code) (dpb 1 (byte 1 (1- n)) code))
(reverse gray-1))))))
;; (gray 3) --> (0 1 3 2 6 7 5 4)
;;;; THE END ;;;;