Revision history [back]

You may use RecursivelyEnumeratedSet in Sage to do these kind of thing:

sage: def non_rep_words(alphabet):
....:     def children(w):
....:         return [w+(a,) for a in alphabet if not w or w[-1] != a]
....:     seeds = [tuple()]
....:     R = RecursivelyEnumeratedSet(seeds, children, structure='forest')
....:     return R
....: 
sage: Rab = non_rep_words(['a','b'])
sage: Rab
An enumerated set with a forest structure
sage: it = Rab.breadth_first_search_iterator()
sage: [next(it) for _ in range(6)]
[(), ('a',), ('b',), ('a', 'b'), ('b', 'a'), ('a', 'b', 'a')]
sage: list(Rab.elements_of_depth_iterator(3))
[('a', 'b', 'a'), ('b', 'a', 'b')]
sage: list(Rab.elements_of_depth_iterator(4))
[('a', 'b', 'a', 'b'), ('b', 'a', 'b', 'a')]
sage: list(Rab.elements_of_depth_iterator(5))
[('a', 'b', 'a', 'b', 'a'), ('b', 'a', 'b', 'a', 'b')]