Finding out complexity of a list

[cormullion]

Here's a quickie for you. Given a list of stupendous and garguantuan proportions*, how would you measure or describe its complexity?



flat is useful, I suppose, but I want to know how deep the levels go and that doesn't help. I don't really want to convert it to a string, unless that's the only way...



* - eg some S-XML I found recently... :)

[Sammo]

Maybe ref-all to find reference vectors for all elements, then take the longest vector as the complexity metric? Something like this:

Code Select Expand

(apply max (map length (ref-all nil aList (fn (x) true))))

Edit: Clarified list parameter in ref-all.

[cormullion]

That's cool! Hadn't thought of looking for nil!

[Kazimir Majorinc]

I have these three functions in my library:

(Lists are understood as trees, and complexity is measured in terms of nodes, branches and leafs. The branch is path from root to leaf.)

Code Select Expand

;
; Syntax:            (depth <L>) - length of the longest branch
;                    (size <L>)  - number of nodes
;                    (width <L>) - number of leafs
;
; Examples:      

(set 'depth (lambda(x)
               ;(println x)
               (cond ((quote? x)(+ 1 (depth (eval x))))
                     ((and (list? x) (empty? x)) 1)
                     ((list? x)(+ 1 (apply max (map depth x))))
                     (true 1))))
                     
(set 'size (lambda(x)
              (+ 1 (cond ((quote? x)(size (eval x)))
                         ((list? x)(apply + (map size x)))
                         (true 0)))))
                         
(set 'width (lambda(x)
              (cond ((quote? x)(width (eval x)))
                    ((list? x)(apply + (map width x)))
                    (true 1))))

For example, when my library is loaded, I get messages like this one:

Code Select Expand

Defined random-sublist with size=70, depth=8 and width=43.

That gives few measures of the complexity of the definition of the random-sublist:

Code Select Expand

(lambda(L pick-from-list)
      (let ((result '())
            (left-in-list (length L)))
           (when (> pick-from-list left-in-list)
            (throw-error (append "There is no n="
                                 (string pick-from-list)
                                 " elements in L.")))
           (dolist (element L (= pick-from-list 0))
                   (let ((probability (div pick-from-list
                                           left-in-list)))
                         (when (<= (random 0 1) probability)
                               (push element result -1)
                               (dec pick-from-list))
                         (dec left-in-list)))
            result))

[cormullion]

Thanks, Kazimir. I've just spotted your reply! These work well.

Code Select Expand

(map (fn (f) (println f { } (apply f sxml))) '(depth  size  width))
depth 10
size 77477
width 51393

where sxml is the newLISP user manual in SXML... :)