首页 | 本学科首页   官方微博 | 高级检索  
     


Practical algorithms to rank necklaces,Lyndon words,and de Bruijn sequences
Affiliation:1. School of Computer Science, University of Guelph, Canada;2. Science, Mathematics & Computing, Bard College at Simon''s Rock, USA
Abstract:
We present practical algorithms for ranking k-ary necklaces and Lyndon words of length n. The algorithms are based on simple counting techniques. By repeatedly applying the ranking algorithms, both necklaces and Lyndon words can be efficiently unranked. Then, explicit details are given to rank and unrank the length n substrings of the lexicographically smallest de Bruijn sequence of order n.
Keywords:Necklace  Lyndon word  De Bruijn sequence  Ranking and unranking
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号