Here's a quickie for you. Given a list of stupendous and garguantuan proportions*, how would you measure or describe its complexity?
* - eg some S-XML I found recently... :)
Maybe ref-all to find reference vectors for all elements, then take the longest vector as the complexity metric? Something like this:
Edit: Clarified list parameter in ref-all.
That's cool! Hadn't thought of looking for nil!
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.)
; 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:
That gives few measures of the complexity of the definition of the
(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))
Thanks, Kazimir. I've just spotted your reply! These work well.
depth 10
size 77477
width 51393
where sxml is the newLISP user manual in SXML... :)