Search This Blog

01 November 2014

recursivity elegance

while searching for an elegant solution, I stumbled upon this by Andrew Clark
incoming = {'E': {'D': {'A': {},
                        'O': {'Co': {},
                              'Cu': {}
                             }
                        }
                 }
            }

expected = [
   ('E', 'D', 'A'),
   ('E', 'D', 'O', 'Co'),
   ('E', 'D', 'O', 'Cu'),
]


def paths(tree, cur=()):
    if not tree:  # previous was a leaf, path to us is a solution
        yield cur
    else:  # we're a node
        for node, subtree in tree.iteritems():
            for path in paths(subtree, cur+(node,)):
                yield path

assert list(paths(incoming)) == expected

No comments:

Post a Comment