![\"tree\"](\"http:\/\/yuguangzhang.com\/blog\/wp-content\/uploads\/2010\/04\/tree-300x240.PNG\" "\\"tree\\"")
<\/a>
\nwould translate to
\n[cc lang=”python”][[1],[2,6],[3,5,7],[4]][\/cc]
\nand
\n[cc lang=”python”][(1,2),(2,3),(2,5),(3,4),(1,6),(6,7)][\/cc]<\/p>\nSeparating the Levels<\/h4>\n
\nWe start off with a recursive list representing the tree structure:
\n[cc lang=”python”][1,[2,6,[3,5,[4,[]],[]],[7,[]]]][\/cc]
\nTo tackle the problem, I first solved a similar one: flattening a list.
\nThis can easily be done in Scheme, as syntax and type declarations do not get in the way.
\n[cc lang=”scheme”]
\n(define (flatten sequence)
\n (cond ((null? sequence) ‘()) ; simplest case: ()
\n ((list? (car sequence)) ; a list in front: ((1) …)
\n (append (flatten (car sequence))
\n (flatten (cdr sequence))))
\n (else (cons (car sequence) ; an atom in front: (1 …)
\n (flatten (cdr sequence))))))<\/p>\n
> (flatten ‘(1 (2 3)))
\n(list 1 2 3)
\n[\/cc]
\nHere’s the same code translated into Python:
\n[cc lang=”python”]
\ncar = lambda lst: lst[0]
\ncdr = lambda lst: lst[1:]
\ndef flatten(seq):
\n\tif not seq:
\n\t\treturn list()
\n\telif isinstance(car(seq), list):
\n\t\treturn flatten(car(seq)).extend(flatten(cdr(seq)))
\n\telse:
\n\t\treturn [car(seq), flatten(cdr(seq))]
\n[\/cc]
\nUnfortunately, flatten in Python produces a hypernested structure for flat lists, as (1 2 3) in Scheme is equibalent to (cons 1 (cons 2 (cons 3 empty))) or (1 . (2 . 3)).
\n[cc lang=”python”]
\n>>> flatten([1,2,3])
\n[1, [2, [3, []]]]
\n[\/cc]
\nThe more serious problem is that it exposes a quirk in Python:
\n[cc lang=”python”]
\n>>> [1].extend([])
\n>>>
\n[\/cc]
\nYes, that means the list disappears after being extended with an empty list . . . one of those unpleasant surprises.
\nSo let’s redefine a flat list in Python:
\n[cc lang=”python”]
\ndef flatten(tree):
\n result = []
\n for node in tree:
\n if isinstance(node, list):
\n result.extend(flatten(node))
\n else:
\n result.append(node)
\n return result<\/p>\n
>>> flatten([1,2,3])
\n[1,2,3]
\n>>> flatten([1,[2,3]])
\n[1,2,3]
\n[\/cc]
\nThere is a similarity between this approach and the recursive one: different actions are taken for a list node and other nodes. I used a combined functional and imperative approach to solve the problem:
\n[cc lang=”python”]
\ncar = lambda lst: lst[0]
\ncdr = lambda lst: lst[1:]<\/p>\n
”’
\ndepth: returns the maximum nesting level of a list<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n an integer
\n”’
\ndef depth(ls):
\n if not ls:
\n return 0
\n elif isinstance(car(ls),list):
\n return max(depth(car(ls))+1,depth(cdr(ls)))
\n else:
\n return max(1,depth(cdr(ls)))<\/p>\n
”’
\nstrip: returns the list elements of a list<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n ls, the modified list
\n”’
\ndef strip(ls, top):
\n if top:
\n for item in top:
\n if item in ls:
\n ls.remove(item)
\n elif cdr(ls):
\n ls = car(ls) + strip(cdr(ls), top) # case like [[1], …]
\n else:
\n ls = car(ls) # case like [[1]]
\n return ls<\/p>\n
”’
\nlevel: returns the top level elements of a list<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n a new list
\n”’
\ndef level(ls):
\n if not ls:
\n return []
\n elif not isinstance(car(ls),list):
\n return [car(ls)] + level(cdr(ls))
\n else:
\n return level(cdr(ls))<\/p>\n
”’
\nlevelize: returns a list of lists, each list is contains the items of a level<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n a new list
\n”’
\ndef levelize(ls):
\n result = []
\n a = list(ls)
\n for i in range(2*depth(ls)):
\n if not i%2:
\n result.append(level(a))
\n a = strip(a, level(a))
\n return result<\/p>\n
>>> levelize([1,[2,6,[3,5,[4,[]],[]],[7,[]]]])
\n[[1], [2, 6], [3, 5, 7], [4]]
\n[\/cc]<\/p>\n
Connecting the Nodes<\/h4>\n
\nWe start off with a recursive list representing the tree structure, slightly different from the list for separating the levels:
\n[cc lang=”python”][1,[2,[3,[4],5],6,[7]]][\/cc]
\nAgain, a mix of recursion and iteration easily solves the problem:
\n[cc lang=”python”]
\n”’
\npair: returns a list of lists, each list has an odd and even pair<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n a list
\n”’
\ndef pair(ls):
\n result = []
\n while ls:
\n result.append(ls[0:2])
\n ls = ls[2:]
\n return result<\/p>\n
”’
\nconnect: returns a list of tuples, each tuple represents an edge of the graph<\/p>\n
Given:
\n ls, a list<\/p>\n
Result:
\n a list of tuples
\n”’
\ndef connect(ls):
\n result = []
\n if cdr(ls):
\n if cdr(cdr(ls)):
\n for item in pair(ls):
\n result.extend(connect(item))
\n else:
\n second = car(cdr(ls))
\n for item in level(second):
\n result.append((car(ls),item))
\n result.extend(connect(second))
\n return result<\/p>\n
>>> connect([1,[2,[3,[4],5],6,[7]]])
\n[(1, 2), (1, 6), (2, 3), (2, 5), (3, 4), (6, 7)]
\n[\/cc]
\nHopefully, you’ve had fun reading this article and meanwhile came up with a better way to represent the tree as a flat structure.<\/p>\n","protected":false},"excerpt":{"rendered":"
While working on the tree part of the coursetree project, I ran into the question of how to display the course dependencies. I have written a recursive function that returns a recursive list of course prerequisites: [cc lang=”python”][u’SE 112′, [u’MATH 135′, []]][\/cc] I wanted to turn it into a diagram of course prerequisites and decided […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[29,23],"tags":[25,28,27,26,22,24],"class_list":["post-274","post","type-post","status-publish","format-standard","hentry","category-coursetree","category-programming","tag-deep-recursion","tag-depth","tag-flatten","tag-iteration","tag-python","tag-scheme"],"aioseo_notices":[],"_links":{"self":[{"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/posts\/274","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/comments?post=274"}],"version-history":[{"count":0,"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/posts\/274\/revisions"}],"wp:attachment":[{"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/media?parent=274"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/categories?post=274"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yuguangzhang.com\/blog\/wp-json\/wp\/v2\/tags?post=274"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"tree\"](\"http:\/\/yuguangzhang.com\/blog\/wp-content\/uploads\/2010\/04\/tree.PNG\" "\\"tree\\"")
<\/a>