DSpace Repository

# Circular bit strings and stable permutations

 dc.contributor.author Nguyen Ngoc Trung en_US dc.date.accessioned 2015-01-12T10:39:55Z dc.date.available 2015-01-12T10:39:55Z dc.identifier.other AIT Thesis no.CS-03-16 en_US dc.identifier.uri http://www.cs.ait.ac.th/xmlui/handle/123456789/264 dc.description Pathum Thani, Thailand : Asian Institute of Technology, 2003 en_US dc.description 29 p. en_US dc.description.abstract In this thesis we consider the problem of recognizing and generating permutations of the integers f 0 ;:::; 2 r ° 1 g that have a special property. The idea is as follows. Any integer from f 0 ;:::; 2 r ° 1 g can be represented in its binary form as a bit string of length r . Consequently, a permutation p = ( p 0 ;p 1 ;:::;p 2 r ° 1 ) of f 0 ;:::; 2 r ° 1 g can be represented as a bit string, call it R ( p ) , of length r: 2 r 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 f 0 ;:::; 2 r ° 1 g , 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 f 0 ;:::; 2 r ° 1 g . In this thesis we prove several interesting properties of stable permutation. Algo- rithm for recognizing stable permutations, rules to generate stable permutations are also proposed. dc.relation.ispartof Thesis no. CS-03-16 en_US dc.relation.ispartof Asian Institute of Technology. Thesis no. CS-03-16 en_US dc.subject Permutations en_US dc.title Circular bit strings and stable permutations en_US dc.type Thesis en_US
﻿