Hi There,
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.
One can also provide a post_process function that allows for customizing the
nodes that are actually produced. Furthermore, if it returns None, then the
node won't be output at all.
I'd like to gather proposal and find an agreement on the names for
SearchForest and post_process.
Here are some proposal for search forest:
- TreeGeneratedSet
- ForestGeneratedSet
- RecursivelyGeneratedSet
- ChoiceTree
- ChoiceForest
...
Nathann Cohen suggested to rename post_process with map_function, underlying
the fact that post_process is mapped on the sets of node of the tree. I'd like
to have a vote on this rename, possibly with alternative proposal.
\begin{pub}
I'm finishing to polish a class named currently
{{{SearchForestMapReduce}}} which allows to apply in a parallel and
distributed way a map-reduce scheme on the node generated by a such a
forest. For example, here's the Sage code for binary words of length less
or equal that 16:
sage: S = SearchForest(
... roots = [[]],
... children = lambda l: [l+[0], l+[1]] if len(l) < 16 else [])
sage: S.map_reduce(
... map_function = lambda z: x**len(z),
... reduce_function = lambda x,y: x+y,
... reduce_init = 0 )
65536*x^16 + 32768*x^15 + 16384*x^14 + 8192*x^13 + 4096*x^12 + 2048*x^11
+ 1024*x^10 + 512*x^9 + 256*x^8 + 128*x^7 + 64*x^6 + 32*x^5 + 16*x^4 + 8*x^3 +
4*x^2 + 2*x + 1
\end{pub}
Thanks for your suggestions,
Florent
--
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.
