Hi,
> Thanks to Nicolas the Little, Sage has a SearchForest class. It is a very nice
> tools to iterate through sets defined by a recursive choice
> tree. Unfortunately, currently due to the name someone who doesn't know that
> it exists has no chance to find it. It seems that there is an agreement that
> the mane should be changed but we didn't yet find a good one. Let me describe
> a little what it does (please refer to the doc for more informations and
> examples):
>
> The enumerated set is mostly described by two data:
> - roots which are the starting nodes of the recursive generation
> - children with compute the immediate successors of a node in the generation
> tree.
There are many examples of languages that may be built along those
lines (words on {a,b,c} that does not contain any square, smooth
words, ...). I was able to build word on {a,b,c} without squares in 2
lines and 1 minute... so I love it. Thanks to Nicolas the little!
{{{
is_square = lambda w: len(w)%2 == 0 and w[:len(w)/2] == w[len(w)/2:]
children = lambda w: [v for v in [w+'a',w+'b',w+'c'] if not
any(is_square(v[i:]) for i in xrange(-2,-len(v)-1,-2))]
}}}
And then
{{{
sage: S = SearchForest(roots = [''], children = children)
sage: list(S.elements_of_depth(4))
['abac', 'abca', 'abcb', 'acab', 'acba', 'acbc', 'babc', 'baca',
'bacb', 'bcab', 'bcac', 'bcba', 'caba', 'cabc', 'cacb', 'cbab',
'cbac', 'cbca']
sage: S.elements_of_depth_iterator(100).next()
'abacabcacbabcabacabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcbacabacbabcabacabcac'
}}}
But for more complicated languages, to build words of length n+1 we
need in general more than the words of length n... ie we have to store
extra computation for each word of length n. As far as I understand,
removing extra computation may be an example of post_process ?
> Here are some proposal for search forest:
> - TreeGeneratedSet
> - ForestGeneratedSet
> - RecursivelyGeneratedSet
> - ChoiceTree
> - ChoiceForest
> ...
For naming convention, I would like to see Recursive and I don't
understand why there is a Search in the name ? It is more an
exhaustion than a search, isn't it ?
Cheers,
Vincent
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
