recursion - Generating a list of all possible combinations of true or false for n given variables in LISP -

i want define function takes input "n" (the number of variables) , return possible truth values. here, represent truth values variable (1 <= <= n) +i representing true, , -i representing false.

for example:

(generate-values 2) 

should return:

((2 1)(2 -1)(-2 1)(-2 -1))  (generate-values 3) 

should return:

((3 2 1)(3 2 -1)(3 -2 1)(3 -2 -1)(-3 2 1)(-3 2 -1)(-3 -2 1)(-3 -2 -1)) 

here incorrect attempt:

(defun generate-values (n)   (cond    ((equal n 0) nil)    (t (list (cons n (generate-values (- n 1)))             (cons (- 0 n) (generate-values (- n 1))))))) 

i know why incorrect, not able find way generate (3 2 1) , move on (3 2 -1). program outputs:

 ((3 (2 (1) (-1)) (-2 (1) (-1))) (-3 (2 (1) (-1)) (-2 (1) (-1)))) 

any question qould thoroughly appreciated! thanks!

it might easiest approach in easiest way possible, , figure out how make bit simpler or more efficient afterward.

if you're doing recursively, it's important consider bases cases are. reasonable base case here when n = 0. function supposed return list of lists. in n = 0 case, there no "variables", result has list of empty list: (()).

for case n else, consider function returns n-1. it's list of combinations on n-1 "variables". need prepend n each of those, , prepend -n each of those, , make sure end list of of those.

encoding directly, end this:

(defun table (n)   (if (zerop n)       '(())       (let* ((table (table (1- n)))              (plus-pos-n (mapcar (lambda (subtable)                                    (list* n subtable))                                  table))              (plus-neg-n (mapcar (lambda (subtable)                                    (list* (- n) subtable))                                  table)))         (nconc plus-pos-n plus-neg-n)))) 

cl-user> (table 3) ((3 2 1) (3 2 -1) (3 -2 1) (3 -2 -1) (-3 2 1) (-3 2 -1) (-3 -2 1) (-3 -2 -1)) 

now, let's @ current implementation doing differently, noting doesn't have same algorithm, of course.

(defun generate-values (n)   (cond     ((equal n 0)      nil)     (t      (list (cons n                    (generate-values (- n 1)))              (cons (- 0 n)                    (generate-values (- n 1))))))) 

stylistically, since there 2 branches, i'd prefer if cond here, that's not problem. before attacking base case, lets @ recursive case, when n ≠ 0. first, you're calling generate-values twice; more efficient call once , save result. end being important later if you're calling function big values of n, doesn't make function incorrect. remember generate-values returns; returns list of different combinations. means call (cons n (generate-values …)) returning list first element n, , remaining elements combinations n-1. e.g., you're doing like:

cl-user> (table 1) ((1) (-1)) cl-user> (cons 2 (table 1)) (2 (1) (-1)) 

but that's not want. want add n each of lists:

cl-user> (mapcar (lambda (x)                    (cons 2 x))                  (table 1)) ((2 1) (2 -1)) 

that's issue in recursive case. there's issue in base case, too. in recursive case, want add n , -n each of sublists n-1 case. happens when have n = 1? want getting (cons 1 '()) , (cons -1 '()). since second argument cons going each list inside of result of (generate-values 0), really need have in list returned (generate-values 0). needs there? empty list needs there. base case needs return (()), not (). so, after making changes, code be:

(defun generate-values (n)   (cond     ((equal n 0)      '(()))     (t      (list (mapcar (lambda (x)                      (cons n x))                    (generate-values (- n 1)))            (mapcar (lambda (x)                      (cons (- 0 n) x))                    (generate-values (- n 1))))))) 

cl-user> (generate-values 3) (((3 (2 (1)) (2 (-1))) (3 (-2 (1)) (-2 (-1))))  ((-3 (2 (1)) (2 (-1))) (-3 (-2 (1)) (-2 (-1))))) 

that's closer, it's still not quite right. there's in recursive case. end generating values have n in beginning (a list of them), , values have -n in beginning (a list of them), you're using list combine them. returns single list 2 values. instead, want single list has values each of them. want combine them append (or, since structure newly generated, use nconc):

(defun generate-values (n)   (cond     ((equal n 0)      '(()))     (t      (append (mapcar (lambda (x)                        (cons n x))                      (generate-values (- n 1)))              (mapcar (lambda (x)                        (cons (- 0 n) x))                      (generate-values (- n 1))))))) 

cl-user> (generate-values 3) ((3 2 1) (3 2 -1) (3 -2 1) (3 -2 -1) (-3 2 1) (-3 2 -1) (-3 -2 1) (-3 -2 -1)) 

this final implementation isn't started with, it's same in terms of algorithm. differences stylistic, there efficiency concerns, too. using nconc instead of append save memory, , cache results recursive call, rather recomputing it. stylistic issues don't affect correctness might using if instead of cond, using list* instead of cons (to indicate we're working lists, not trees of cons cells), , it's nice note don't have (- 0 n), - single argument returns argument's negation. is, (- n) = -n.