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

@Kaligulaa · Регистрация: 18.05.2015

Студворк — интернет-сервис помощи студентам

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

@_Ivana · 08.07.2016, 05:26

В лоб функционально:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defn next-gen (l)
    (defn go (x) (map (lambda (e) (cons x e)) l))
    (append (go 0) (reverse (go 1))) )
 
(defn gray (n)
    (defn go (n l) (cond (<= n 1) l (go (- n 1) (next-gen l))) )
    (go n '((0) (1))) )
=> OK
gray 1
=> ((0) (1))
gray 2
=> ((0 0) (0 1) (1 1) (1 0))
gray 3
=> ((0 0 0) (0 0 1) (0 1 1) (0 1 0) (1 1 0) (1 1 1) (1 0 1) (1 0 0))
gray 4
=> ((0 0 0 0) (0 0 0 1) (0 0 1 1) (0 0 1 0) (0 1 1 0) (0 1 1 1) (0 1 0 1) (0 1 0 0) (1 1 0 0) (1 1 0 1) (1 1 1 1) (1 1 1 0) (1 0 1 0) (1 0 1 1) (1 0 0 1) (1 0 0 0))

По лбу функционально:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defn gray (n)
    (defn go (x l) (map (lambda (e) (cons x e)) l))
    (cond (<= n 1) '((0) (1))
        ((def p (gray (- n 1))) (append (go 0 p) (reverse (go 1 p)))) ))
=> OK
gray 1
=> ((0) (1))
gray 2
=> ((0 0) (0 1) (1 1) (1 0))
gray 3
=> ((0 0 0) (0 0 1) (0 1 1) (0 1 0) (1 1 0) (1 1 1) (1 0 1) (1 0 0))
gray 4
=> ((0 0 0 0) (0 0 0 1) (0 0 1 1) (0 0 1 0) (0 1 1 0) (0 1 1 1) (0 1 0 1) (0 1 0 0) (1 1 0 0) (1 1 0 1) (1 1 1 1) (1 1 1 0) (1 0 1 0) (1 0 1 1) (1 0 0 1) (1 0 0 0))

UPD текущий append в стандартной библиотеке был не хвосторекурсивный, переделал в хвостовую рекурсию (за счет предварительного реверса списка - неоптимально, зато недеструктивно и иммутабельно) - и Java-интерпретатор (имея TCO) стал считать неприличные 15-20 значные коды без переполнения небольшого стандартного стека Java-потока по умолчанию.

@Catstail · 08.07.2016, 10:25

Common Lisp:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(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))

@_sg · 08.07.2016, 19:48

https://rosettacode.org/wiki/Gray_code#Common_Lisp :

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(defun gray-encode (n)
  (logxor n (ash n -1)))
 
(defun gray-decode (n)
  (do ((p n (logxor p n)))
      ((zerop n) p)
    (setf n (ash n -1))))
 
(loop for i to 31 do
      (let* ((g (gray-encode i)) (b (gray-decode g)))
    (format t "~2d:~6b =>~6b =>~6b :~2d~%" i i g b b)))
 
 0:     0 =>     0 =>     0 : 0
 1:     1 =>     1 =>     1 : 1
 2:    10 =>    11 =>    10 : 2
 3:    11 =>    10 =>    11 : 3
 4:   100 =>   110 =>   100 : 4
 5:   101 =>   111 =>   101 : 5
 6:   110 =>   101 =>   110 : 6
 7:   111 =>   100 =>   111 : 7
 8:  1000 =>  1100 =>  1000 : 8
 9:  1001 =>  1101 =>  1001 : 9
10:  1010 =>  1111 =>  1010 :10
11:  1011 =>  1110 =>  1011 :11
12:  1100 =>  1010 =>  1100 :12
13:  1101 =>  1011 =>  1101 :13
14:  1110 =>  1001 =>  1110 :14
15:  1111 =>  1000 =>  1111 :15
16: 10000 => 11000 => 10000 :16
17: 10001 => 11001 => 10001 :17
18: 10010 => 11011 => 10010 :18
19: 10011 => 11010 => 10011 :19
20: 10100 => 11110 => 10100 :20
21: 10101 => 11111 => 10101 :21
22: 10110 => 11101 => 10110 :22
23: 10111 => 11100 => 10111 :23
24: 11000 => 10100 => 11000 :24
25: 11001 => 10101 => 11001 :25
26: 11010 => 10111 => 11010 :26
27: 11011 => 10110 => 11011 :27
28: 11100 => 10010 => 11100 :28
29: 11101 => 10011 => 11101 :29
30: 11110 => 10001 => 11110 :30
31: 11111 => 10000 => 11111 :31

@Lambdik · 10.07.2016, 21:45

Из раннего и нерекурсивно.

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun gray (k &optional (init '((0 0) (0 1) (1 1) (1 0))))
  (if (= k 1) '((0) (1))
  (loop
    (if (= k 2) (return init))
      (setf init (nconc
        (mapcar #'(lambda (x) (cons 0 x)) init)
        (mapcar #'(lambda (x) (cons 1 x)) (reverse init))))
      (decf k))))
 
; (gray 3)
; ((0 0 0) (0 0 1) (0 1 1) (0 1 0) (1 1 0) (1 1 1) (1 0 1) (1 0 0))

@_Ivana · 10.07.2016, 21:55

Я на следующий день после ответа подумал, что можно начинать с

Lisp
1
cond (<= n 0) '(())

и дальше так же разворачивать и консить 0 и 1. На русской википедии это не особо объяснено, но конечно собственные мысли никто не отменял...

@route66 · 10.08.2016, 13:21

Scala:

Java
1
2
3
4
5
6
7
def gray(n: Int): List[List[Int]] = {
  if (n == 1) List(List(0), List(1))
  else {
    val v = gray(n - 1)
    v.map(0 :: _) ++ v.reverse.map(1 :: _)
  }
}

Java
1
2
3
4
5
6
def gray(n: Int): List[List[Int]] = n match {
  case 1 => List(List(0), List(1))
  case _ =>
    val v = gray(n - 1)
    v.map(0 :: _) ::: v.reverse.map(1 :: _)
}

Java
1
2
scala> gray(2) 
List[List[Int]] = List(List(0, 0), List(0, 1), List(1, 1), List(1, 0))

Java
1
2
3
4
5
6
7
8
9
(for {
  (code, index) <- gray(2).zipWithIndex
} yield s"$index : (${code.mkString(" ")})").mkString("\n")
 
String =
0 : (0 0)
1 : (0 1)
2 : (1 1)
3 : (1 0)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

@Kaligulaa 6 / 7 / 2 Регистрация: 18.05.2015 Сообщений: 124

	Коды Грея рекурсивно 08.07.2016, 01:55. Показов 1598. Ответов 6 Метки нет (Все метки) Очень интересно для себя стало: как на LISP с помощью рекурсии можно было бы выдать коды Грея? Все таки алгоритм их построения требуют зеркального принципа, но как это реализовать? Заранее спасибо 0

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

Решение