From: Ben Olasov
Subject: tree generator
Date: 
Message-ID: <432f5c$oe1@shadow.cs.columbia.edu>
I need a function to generate a decision tree based on X variables,
each of which can have Y possible values.  Is there a straightforward
way to take a nested list of the variables and their associated sets
of possible values, like the following:
 
'((var1 '("A" "B" "C"))
  (var2 '(123 234 345 456))
  (var3 '(SYM1 SYM2 SYM3))
  (var4 '('(* SYM1 5.0) '(/ SYM2 4.0) '(+ SYM2 SYM3))))
 
and produce a [hierarchical] 'decision tree'-like expression in which
all the possible branches are iterated?  So, to continue with the
above example, if passed a nested list like the one above, the
function I'm looking for would return an expression not unlike the
following:
 
(cond ((= var1 "A")
       (cond ((= var2 123)
              (cond ((= var3 SYM1)
                     (cond ((= var4 (* SYM1 5.0))
                            (princ "case 1.1.1.1"))
                           ((= var4 (/ SYM2 4.0))
                            (princ "case 1.1.1.2"))
                           ((= var4 (+ SYM2 SYM3))
                            (princ "case 1.1.1.3"))
                    ((= var3 SYM2)
                     (cond ((= var4 (* SYM1 5.0))
                            (princ "case 1.1.2.1"))
                           ((= var4 (/ SYM2 4.0))
                            (princ "case 1.1.2.2"))
                           ((= var4 (+ SYM2 SYM3))
                            (princ "case 1.1.2.3"))
 
. . .
 
As above, it's assumed that the first key/value-list pair in the
argument becomes the top level in the hierarchy.

I couldn't find anything that looked similar in the FAQ, although this
problem _looks_ general enough [and somehow familiar enough] that it's
easy to think it must have been repeatedly solved in the past.
 
Any ideas or pointers to previous [hopefully optimal] solutions are
welcome!
 
 
Ben
 

-- 
;Ben Olasov			······@shadow.cs.columbia.edu
;				···@syska.com
From: Jens Kilian
Subject: Re: tree generator
Date: 
Message-ID: <433fs3$t1n@hpscit.sc.hp.com>
Ben Olasov (······@shadow.cs.columbia.edu) wrote:

> I need a function to generate a decision tree based on X variables,
> each of which can have Y possible values.  Is there a straightforward
> way to take a nested list of the variables and their associated sets
> of possible values, like the following:
>  
> '((var1 '("A" "B" "C"))
>   (var2 '(123 234 345 456))
>   (var3 '(SYM1 SYM2 SYM3))
>   (var4 '('(* SYM1 5.0) '(/ SYM2 4.0) '(+ SYM2 SYM3))))

Why do you use so many quotes?  The first one would be sufficient.

> (cond ((= var1 "A")
>        (cond ((= var2 123)
>               (cond ((= var3 SYM1)
>                      (cond ((= var4 (* SYM1 5.0))
>                             (princ "case 1.1.1.1"))
>                            ((= var4 (/ SYM2 4.0))
>                             (princ "case 1.1.1.2"))
>                            ((= var4 (+ SYM2 SYM3))
>                             (princ "case 1.1.1.3"))
>                     ((= var3 SYM2)
>                      (cond ((= var4 (* SYM1 5.0))
>                             (princ "case 1.1.2.1"))
>                            ((= var4 (/ SYM2 4.0))
>                             (princ "case 1.1.2.2"))
>                            ((= var4 (+ SYM2 SYM3))
>                             (princ "case 1.1.2.3"))

Here's a straightforward solution (no error checking):

(defun decision-tree (patterns &optional cases)
  (if (null patterns)     
      `(princ ,(format nil "case ~{~S~^.~}" (reverse cases)))
    
    `(cond ,(let ((pattern (first patterns))
		  (others  (rest patterns)))
	      (let ((variable (first pattern))
		    (values   (second pattern))
		    (case     0))
		(mapcar #'(lambda (value)
			    `((= ,variable ,value)
			      ,(decision-tree others
					      (cons (incf case) cases))))
			values))))))

(decision-tree '((var1 ("A" "B" "C"))
		 (var2 (123 234 345 456))
		 (var3 (SYM1 SYM2 SYM3))
		 (var4 ((* SYM1 5.0) (/ SYM2 4.0) (+ SYM2 SYM3)))))
==>
(COND
  (((= VAR1 "A")
    (COND
      (((= VAR2 123)
        (COND
          (((= VAR3 SYM1)
            (COND
              (((= VAR4 (* SYM1 5.0))
                (PRINC "case 1.1.1.1"))
               ((= VAR4 (/ SYM2 4.0))
                (PRINC "case 1.1.1.2"))
               ((= VAR4 (+ SYM2 SYM3))
                (PRINC "case 1.1.1.3")))))
           ((= VAR3 SYM2)
            (COND
              (((= VAR4 (* SYM1 5.0))
                (PRINC "case 1.1.2.1"))
               ((= VAR4 (/ SYM2 4.0))
                (PRINC "case 1.1.2.2"))
               ((= VAR4 (+ SYM2 SYM3))
                (PRINC "case 1.1.2.3")))))
           ((= VAR3 SYM3)
            (COND
              (((= VAR4 (* SYM1 5.0))
                (PRINC "case 1.1.3.1"))
               ((= VAR4 (/ SYM2 4.0))
                (PRINC "case 1.1.3.2"))
               ((= VAR4 (+ SYM2 SYM3))
                (PRINC "case 1.1.3.3"))))))))
       ((= VAR2 234)
        (COND
          (((= VAR3 SYM1)
            (COND
              (((= VAR4 (* SYM1 5.0))
                (PRINC "case 1.2.1.1"))
               ((= VAR4 (/ SYM2 4.0))
                (PRINC "case 1.2.1.2"))
               ((= VAR4 (+ SYM2 SYM3))
                (PRINC "case 1.2.1.3")))))

The full output is >300 lines (I'm sure you know about exponential blowup).
Also, the test using "=" may not be what you really want; I suspect you should
be using EQUAL.

Greetings,

	Jens.
From: Ben Olasov
Subject: Re: tree generator
Date: 
Message-ID: <434plt$hpu@shadow.cs.columbia.edu>
In article <··········@hpscit.sc.hp.com>, Jens Kilian <·····@bbn.hp.com> wrote:

>> '((var1 '("A" "B" "C"))
>>   (var2 '(123 234 345 456))
>>   (var3 '(SYM1 SYM2 SYM3))
>>   (var4 '('(* SYM1 5.0) '(/ SYM2 4.0) '(+ SYM2 SYM3))))
>
>Why do you use so many quotes?  The first one would be sufficient.

	<deletia>

>>                            ((= var4 (/ SYM2 4.0))
>>                             (princ "case 1.1.1.2"))
>>                            ((= var4 (+ SYM2 SYM3))
>>                             (princ "case 1.1.1.3"))
>>                     ((= var3 SYM2)

>Also, the test using "=" may not be what you really want; I suspect you should
>be using EQUAL.

I know - after I sent this off, I remembered I should have expected
this to get misunderstood - it's an invitation to misinterpretation
after all - the 'code' above was simply intended as
shorthand/pseudocode to convey a concept, not to compile.

Anyway, thanks for the idea - I'll try it out...

>Greetings,
>
>	Jens.

Ben

-- 
;Ben Olasov			······@shadow.cs.columbia.edu
;				···@syska.com
comp.lang.lisp / 1995 / sep