Generating Binary Trees by Transpositions. Ruskey, F. & Proskurowski, A. Journal of Algorithms, 11(1):68--84, March, 1990.
Paper doi abstract bibtex Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property 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 for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.
@article{ Ruskey1990,
abstract = {Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property 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 for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.},
author = {Ruskey, Frank and Proskurowski, Andrzej},
doi = {10.1016/0196-6774(90)90030-I},
file = {:Users/KunihiroWASA/Dropbox/paper/1990/Ruskey, Proskurowski, Generating Binary Trees by Transpositions, 1990.pdf:pdf},
issn = {01966774},
journal = {Journal of Algorithms},
month = {March},
number = {1},
pages = {68--84},
title = {{Generating Binary Trees by Transpositions}},
url = {http://www.sciencedirect.com/science/article/pii/019667749090030I http://linkinghub.elsevier.com/retrieve/pii/019667749090030I},
volume = {11},
year = {1990}
}
Downloads: 0
{"_id":"nJqKQpHBnzAuxKuXm","authorIDs":[],"author_short":["Ruskey, F.","Proskurowski, A."],"bibbaseid":"ruskey-proskurowski-generatingbinarytreesbytranspositions-1990","bibdata":{"abstract":"Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property 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 for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.","author":["Ruskey, Frank","Proskurowski, Andrzej"],"author_short":["Ruskey, F.","Proskurowski, A."],"bibtex":"@article{ Ruskey1990,\n abstract = {Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property 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 for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.},\n author = {Ruskey, Frank and Proskurowski, Andrzej},\n doi = {10.1016/0196-6774(90)90030-I},\n file = {:Users/KunihiroWASA/Dropbox/paper/1990/Ruskey, Proskurowski, Generating Binary Trees by Transpositions, 1990.pdf:pdf},\n issn = {01966774},\n journal = {Journal of Algorithms},\n month = {March},\n number = {1},\n pages = {68--84},\n title = {{Generating Binary Trees by Transpositions}},\n url = {http://www.sciencedirect.com/science/article/pii/019667749090030I http://linkinghub.elsevier.com/retrieve/pii/019667749090030I},\n volume = {11},\n year = {1990}\n}","bibtype":"article","doi":"10.1016/0196-6774(90)90030-I","file":":Users/KunihiroWASA/Dropbox/paper/1990/Ruskey, Proskurowski, Generating Binary Trees by Transpositions, 1990.pdf:pdf","id":"Ruskey1990","issn":"01966774","journal":"Journal of Algorithms","key":"Ruskey1990","month":"March","number":"1","pages":"68--84","title":"Generating Binary Trees by Transpositions","type":"article","url":"http://www.sciencedirect.com/science/article/pii/019667749090030I http://linkinghub.elsevier.com/retrieve/pii/019667749090030I","volume":"11","year":"1990","bibbaseid":"ruskey-proskurowski-generatingbinarytreesbytranspositions-1990","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/019667749090030I http://linkinghub.elsevier.com/retrieve/pii/019667749090030I"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:45.541Z","downloads":0,"keywords":[],"search_terms":["generating","binary","trees","transpositions","ruskey","proskurowski"],"title":"Generating Binary Trees by Transpositions","year":1990,"dataSources":["YRMeqhMHoNu9HzJoC"]}