Коды Грея рекурсивно - Lisp

Формулировка задачи:

Очень интересно для себя стало: как на LISP с помощью рекурсии можно было бы выдать коды Грея? Все таки алгоритм их построения требуют зеркального принципа, но как это реализовать? Заранее спасибо

Решение задачи: «Коды Грея рекурсивно»

Листинг программы

(defun gray (n)
  (if (= n 1) (list (list 0) (list 1))
              (let ((v (gray (- n 1))))
                    (append (mapcar (lambda (x) (cons 0 x)) v)
                            (mapcar (lambda (x) (cons 1 x)) (reverse v))))))
 
==> gray
(gray 2)
 
==> ((0 0) (0 1) (1 1) (1 0))
(gray 5)
 
==> ((0 0 0 0 0) (0 0 0 0 1) (0 0 0 1 1) (0 0 0 1 0) (0 0 1 1 0) (0 0 1 1 1) (0 0 1 0 1) (0 0 1 0 0) (0 1 1 0 0) (0 1 1 0 1) (0 1 1 1 1) (0 1 1 1 0) (0 1 0 1 0) (0 1 0 1 1) (0 1 0 0 1) (0 1 0 0 0) (1 1 0 0 0) (1 1 0 0 1) (1 1 0 1 1) (1 1 0 1 0) (1 1 1 1 0) (1 1 1 1 1) (1 1 1 0 1) (1 1 1 0 0) (1 0 1 0 0) (1 0 1 0 1) (1 0 1 1 1) (1 0 1 1 0) (1 0 0 1 0) (1 0 0 1 1) (1 0 0 0 1) (1 0 0 0 0))

Объяснение кода листинга программы

В данном коде реализован алгоритм Коды Грея для генерации всех возможных комбинаций двоичного числа. Алгоритм основан на рекурсивной функции gray, которая принимает на вход число n — количество бит в двоичном числе, которое необходимо сгенерировать. Если n равно 1, то функция возвращает список с двумя элементами: (0, 1). Это базовый случай, так как для n равного 1 существует только одна комбинация. В общем случае, функция gray рекурсивно вызывает саму себя с аргументом n-1, затем применяет операцию append к результатам рекурсивных вызовов и добавляет в конец каждого подсписка элемент 0 или 1, в зависимости от того, четный или нечетный является индекс подсписка. В итоге получается список всех возможных комбинаций двоичного числа. Например, при вызове gray 2 будет возвращен список: ((0 0) (0 1) (1 1) (1 0)). Это означает, что для двоичного числа из двух бит существует 4 возможных комбинации: 00, 01, 11, 10. При вызове gray 5 будет возвращен список: ((0 0 0 0 0) (0 0 0 0 1) (0 0 0 1 1) (0 0 0 1 0) (0 0 1 1 0) (0 0 1 1 1) (0 0 1 0 1) (0 0 1 0 0) (0 1 1 0 0) (0 1 1 0 1) (0 1 1 1 1) (0 1 1 1 0) (0 1 0 1 0) (0 1 0 1 1) (0 1 0 0 1) (0 1 0 0 0) (1 1 0 0 0) (1 1 0 0 1) (1 1 0 1 1) (1 1 0 1 0) (1 1 1 1 0) (1 1 1 1 1) (1 1 1 0 1) (1 1 1 0 0) (1 0 1 0 0) (1 0 1 0 1) (1 0 1 1 1) (1 0 1 1 0) (1 0 0 1 0) (1 0 0 1 1) (1 0 0 0 1) (1 0 0 0 0)). Это означает, что для двоичного числа из пяти бит существует 32 возможных комбинации.