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.