×

Generating binary trees by transpositions. (English) Zbl 0651.68081

Algorithm theory, Proc. 1st Scand. Workshop, Halmstad/Sweden 1988, Lect. Notes Comput. Sci. 318, 199-207 (1988).
Summary: [For the entire collection see Zbl 0639.00043.]
Let T(n) denote the set of all bitstrings with n 1’s and n 0’s such that in every prefix the number of 0’s does not exceed the number of 1’s. This is a well known representation of binary trees. We consider algorithms that generate the elements of T(n) in such a way that successive bitstrings differ by the transposition of two bits. The presented algorithms have a constant average time per generated tree.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
94B25 Combinatorial codes

Citations:

Zbl 0639.00043