De decimal a binario en Lisp: crea una lista no anidada

recursion binary

Question

Al llegar a mis casos de recursividad, uso list para anexar el resultado futuro con el actual, pero termino con una lista anidada debido a la recursión. Esto causa un error cuando tengo un número que causa recursión por más de cinco veces.

Alguna idea de cómo puedo obtener resultados en una sola lista simple no anidada, por ejemplo:

CL-USER 100: 8> (BINARY_LIST 4)

(1 0 0)

Código y resultado de ejemplo:

CL-USER 99 : 8 > (defun binary_list (i)
(COND 
    ((= i 0) 0)
    ((= i 1) 1)
    ((= (mod i 2) 0) (list (binary_list (truncate i 2)) 0))
    (t (list (binary_list (truncate i 2)) 1))
    )
)
BINARY_LIST

CL-USER 100 : 8 > (BINARY_LIST 4)
((1 0) 0)

CL-USER 101 : 8 > (BINARY_LIST 104)
((((# 1) 0) 0) 0)

Answer 1

Ya casi has llegado. Todo lo que necesita hacer es reemplazar la list con nconc :

(defun binary-list (n)
  (cond ((= n 0) (list 0))
        ((= n 1) (list 1))
        (t (nconc (binary-list (truncate n 2)) (list (mod n 2))))))

Puede evitar llamar tanto truncate como mod recogiendo ambos valores en la división de enteros:

(defun binary-list (n)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (list r)
        (nconc (binary-list q) (list r)))))

Tenga en cuenta que este algoritmo es cuadrático porque nconc tiene que atravesar el resultado en cada iteración. Esto se puede evitar pasando un acumulador:

(defun binary-list (n &optional acc)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (cons r acc)
        (binary-list q (cons r acc)))))

Ahora tenemos una función recursiva de cola que puede ser compilada a la iteración por un compilador moderno.

Un truco de optimización más que podría usar (que, de hecho, debería ser hecho por el compilador - ¡intente disassemble para verificar!) logand ash y logand lugar del floor mucho más general y caro:

(defun binary-list (n &optional acc)
  (cond ((zerop n) (or acc (list 0)))
        ((plusp n)
         (binary-list (ash n -1) (cons (logand 1 n) acc)))
        (t (error "~S: non-negative argument required, got ~s" ''binary-list n))))

Por cierto, los lispers usualmente utilizan dash en lugar de guiones bajos en símbolos, por lo que tu binary_list debería ser binary-list si no quieres ofender nuestra tierna estética.

Answer 2

me parece que es la manera más directa y menos indirecta de lograr los resultados deseados siempre:

(defun mvp-binary-from-decimal (n r)
    (if (zerop n)
    r
    (multiple-value-bind (a b)
        (floor n 2)
        (mvp-binary-from-decimal a (cons b r)))))

(defun binary-from-decimal (n)
    (if (and (numberp n) (plusp n))
    (mvp-binary-from-decimal n ''())
    (if (eql n 0) ''(0) nil)))

probado en limo, sbcl, clisp - usado de la siguiente manera:

CL-USER> (binary-from-decimal 100)
(1 1 0 0 1 0 0)
CL-USER> (binary-from-decimal 10)
(1 0 1 0)
CL-USER> (binary-from-decimal 0)
(0)

Hay algunas razones avanzadas en cuanto a por qué esta podría ser la manera más deseable para implementar dicha funcionalidad, pero por ahora, basta decir que es limpia, educada, legible y siempre funciona.