(defun take-at (list n)
  (values 
   (loop for i from 0
         for x in list
         unless (= i n) collect x)
   (elt list n)))

(defun combinations (list)
  (let ((result '()))
    (labels ((combinations2 (list current)
               (if (car list)
                   (loop for i below (length list) do
                         (multiple-value-bind (rest x)
                             (take-at list i)
                           (combinations2 rest (cons x current))))
                 (push current result))))
      (combinations2 list '()))
    result))

(defun iota (n)
  (loop for i below n collect i))

(defun gray-code-iteration (list)
  (let ((result '()))
    (loop for i in list do
          (push (cons 0 i) result))
    (loop for i in (reverse list) do
          (push (cons 1 i) result))
    result))

(defun gray-code (n)
  (let ((result '(())))
    (loop for i below n do
          (setf result (gray-code-iteration result)))
    result))

(defun permutate (list positions)
  (let ((result '()))
    (loop for i in positions do
          (push (elt list i) result))
    result))

(defun all-gray-codes (n)
  (let ((combinations (combinations (iota n)))
        (gray-code (gray-code n))
        (result '()))
    (loop for combination in combinations do
          (let ((permutated '()))
            (loop for code in gray-code do
                  (push (permutate code combination) permutated))
            (push permutated result)))
    result))

(defun join (list)
  (let ((s (make-string-output-stream)))
    (loop for i in list do (format s "~a" i))
    (get-output-stream-string s)))

(defun all-gray-codes-html (n)
  (let ((all-gray-codes (all-gray-codes n)))
    (format t "<table border=\"1\">~%")
    (loop for code in all-gray-codes
          for i from 1 do
          (format t "<tr>")
          (format t "<th>~a</th>" i)
          (loop for i in code do
                (format t "<td>~a</td>" (join i)))
          (format t "</tr>~%"))
    (format t "</table>~%")))

(defun test ()
  (loop for i from 1 to 5 do
        (format t "<h2>all gray codes for word length ~a</h2>~%" i)
        (all-gray-codes-html i)))