Nested string substitutions

[Antonio Cuni]

Lulu of the Lotus-Eaters wrote:

> I think I am being daft here.  But I cannot think of an elegant way to
> perform a nested expansion of a set of substitution patterns.
> 
> For example, let's say I have a dictionary of patterns:
> 
>     subs = {'foo':'bar baz',
>             'bar':'bat bam ber',
>             'baz':'zat zam zer',
>             'bam':'yat yam yer',
>             'yam':'spam and eggs'}

this can be seen as an acyclic directed graph: each word is a node and 
each dictionary pairs defines the arcs. Our goal is to compute the 
transitive closures of the graph:

First, we should use a better data structure for our job:

subs = { 'foo': ['bar', 'baz'],
         'bar': ['kat', 'www'],
         'baz': [],
         'kat': [],
         'www': [] }

It is trivial to pass from the form to the latter. Notice that each node 
must be in the dictionary, even if it has no children.
Now we can use this algorithm (it's by Floyd, if I recall correctly) to 
compute the transitive closures:

for k in subs:
    for i in subs:
        for j in subs:
            if k in subs[i] and j in subs[k]:
                subs[i].append(j)

Obviously "k in subs[i]" tests for an arc from i to k, and so on.

for word in subs:
    print word, subs[word]

baz []
www []
foo ['bar', 'baz', 'www', 'kat']
bar ['kat', 'www']
kat []

I'm sorry but it's longer than two lines... ;-)

ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra