| Author | Nguyen Ngoc Trung |
| Call Number | AIT Thesis no.CS-03-16 |
| Subject(s) | Permutations
|
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. CS-03-16 |
| Abstract | In this thesis we consider the problem of recognizing and generating permutations of the integers f0; : : : ; 2r ¡ 1g that have a special property. The idea is as follows. Any integer from f0; : : : ; 2r ¡ 1g can be represented in its binary form as a bit string of length r. Consequently, a permutation p = (p0; p1; : : : ; p2r¡1) of f0; : : : ; 2r ¡ 1g can be represented as a bit string, call it R(p), of length r:2r by concatenating the binary representations of integers in the permutation. Imagine now the bit string R(p) to be arranged circularly. Our question then is, to obtain a permutation of f0; : : : ; 2r ¡ 1g, can we start reading of binary representations of length r, from any bit on this circle? Clearly, by our definition of R(p) there is at least one such valid start bit. The permutation p is said to be stable if any bit of R(p) (arranged circularly) could serve as the start bit for finding a permutation of f0; : : : ; 2r ¡ 1g. In this thesis we prove several interesting properties of stable permutation. Algorithm for recognizing stable permutations, rules to generate stable permutations are also proposed. |
| Year | 2003 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. CS-03-16 |
| Type | Thesis |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Guha, Sumanta; |
| Examination Committee(s) | Phan Minh Dung;Haddawy, Peter; |
| Scholarship Donor(s) | Vietnamese Ministry of Education and Training; |
| Degree | Thesis (M.Sc.) - Asian Institute of Technology, 2003 |