Document Open Access Logo

Ranking Bracelets in Polynomial Time

Authors Duncan Adamson, Vladimir V. Gusev, Igor Potapov, Argyrios Deligkas

PDF
Thumbnail PDF

File

LIPIcs.CPM.2021.4.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Duncan Adamson
  • Leverhulme Research Centre for Functional Materials Design, Department of Computer Science, University of Liverpool, UK
Vladimir V. Gusev
  • Leverhulme Research Centre for Functional Materials Design, Department of Computer Science, University of Liverpool, UK
Igor Potapov
  • Department of Computer Science, University of Liverpool, UK
Argyrios Deligkas
  • Department of Computer Science, Royal Holloway University of London, UK

Funding

  • Potapov, Igor: Partially funded by EP/R018472/1 and Royal Society Leverhulme Trust Senior Research Fellowship.

Acknowledgements

The authors thank the Leverhulme Trust for funding this research via the Leverhulme Research Centre for Functional Materials Design and the reviewers for their helpful comments that improved the quality of the paper.

Cite As Get BibTex

Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CPM.2021.4

Abstract

The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k²⋅ n⁴), where k is the size of the alphabet and n is the length of the considered bracelets. The key part of the algorithm is to compute the rank of any word with respect to the set of bracelets by finding three other ranks: the rank over all necklaces, the rank over palindromic necklaces, and the rank over enclosing apalindromic necklaces. The last two concepts are introduced in this paper. These ranks are key components to our algorithm in order to decompose the problem into parts. Additionally, this ranking procedure is used to build a polynomial-time unranking algorithm.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
Keywords
  • Bracelets
  • Ranking
  • Necklaces

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. On the Hardness of Energy Minimisation for Crystal Structure Prediction. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 12011 LNCS, pages 587-596. Springer, January 2020. URL: https://doi.org/10.1007/978-3-030-38919-2_48.
  2. Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The K-Centre Problem for Necklaces. CoRR, May 2020. URL: http://arxiv.org/abs/2005.10095.
  3. C. Collins, M. S. Dyer, M. J. Pitcher, G. F. S. Whitehead, M. Zanella, P. Mandal, J. B. Claridge, G. R. Darling, and M. J. Rosseinsky. Accelerated discovery of two crystal structure types in a complex inorganic phase field. Nature, 546(7657):280-284, 2017. Google Scholar
  4. Clelia De Felice, Rocco Zaccagnino, and Rosalba Zizza. Unavoidable sets and circular splicing languages. Theoretical Computer Science, 658:148-158, 2017. Formal Languages and Automata: Models, Methods and Application In honour of the 70th birthday of Antonio Restivo. URL: https://doi.org/10.1016/j.tcs.2016.09.008.
  5. Aris Filos-Ratsikas and Paul W. Goldberg. The complexity of splitting necklaces and bisecting ham sandwiches. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 638-649. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316334.
  6. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics : a foundation for computer science. Addison-Wesley, 1994. Google Scholar
  7. U. I. Gupta, D. T. Lee, and C. K. Wong. Ranking and unranking of B-trees. Journal of Algorithms, 4(1):51-60, March 1983. URL: https://doi.org/10.1016/0196-6774(83)90034-2.
  8. Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams. Combinatorial generation via permutation languages. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1214-1225. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.74.
  9. S. Karim, J. Sawada, Z. Alamgir, and S. M. Husnine. Generating bracelets with fixed content. Theoretical Computer Science, 475:103-112, March 2013. URL: https://doi.org/10.1016/j.tcs.2012.11.024.
  10. Donald E. Knuth. The Art of Computer Programming: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 1st edition, 2011. Google Scholar
  11. T. Kociumaka, J. Radoszewski, and W. Rytter. Computing k-th Lyndon word and decoding lexicographically minimal de Bruijn sequence. In Symposium on Combinatorial Pattern Matching, pages 202-211. Springer, 2014. Google Scholar
  12. S. Kopparty, M. Kumar, and M. Saks. Efficient indexing of necklaces and irreducible polynomials over finite fields. Theory of Computing, 12(1):1-27, 2016. Google Scholar
  13. Martin Mareš and Milan Straka. Linear-time ranking of permutations. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, pages 187-193, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  14. Wendy Myrvold and Frank Ruskey. Ranking and unranking permutations in linear time. Information Processing Letters, 79(6):281-284, 2001. URL: https://doi.org/10.1016/S0020-0190(01)00141-7.
  15. J. M. Pallo. Enumerating, Ranking and Unranking Binary Trees. The Computer Journal, 29(2):171-175, February 1986. URL: https://doi.org/10.1093/comjnl/29.2.171.
  16. J. Sawada and A. Williams. Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences. Journal of Discrete Algorithms, 43:95-110, 2017. Google Scholar
  17. Joe Sawada. Generating bracelets in constant amortized time. SIAM Journal on Computing, 31(1):259-268, January 2001. URL: https://doi.org/10.1137/S0097539700377037.
  18. Toshihiro Shimizu, Takuro Fukunaga, and Hiroshi Nagamochi. Unranking of small combinations from large sets. Journal of Discrete Algorithms, 29:8-20, 2014. URL: https://doi.org/10.1016/j.jda.2014.07.004.
  19. S. G. Williamson. Ranking algorithms for lists of partitions. SIAM Journal on Computing, 5(4):602-617, 1976. URL: https://doi.org/10.1137/0205039.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact