Document Open Access Logo

Raising Permutations to Powers in Place

Authors Hicham El-Zein, J. Ian Munro, Matthew Robertson

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2016.29.pdf
  • Filesize: 499 kB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Algorithms
  • Combinatorics
  • Inplace
  • Permutations
  • Powers

Metrics

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

Abstract

Given a permutation of n elements, stored as an array, we address the problem of replacing the permutation by its kth power. We aim to perform this operation quickly using o(n) bits of extra storage. To this end, we first present an algorithm for inverting permutations that uses O(lg^2 n) additional bits and runs in O(n lg n) worst case time. This result is then generalized to the situation in which the permutation is to be replaced by its kth power. An algorithm whose worst case running time is O(n lg n) and uses O(lg^2 n + min{k lg n, n^{3/4 + epsilon}}) additional bits is presented.

Cite As Get BibTex

Hicham El-Zein, J. Ian Munro, and Matthew Robertson. Raising Permutations to Powers in Place. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.29

Author Details

Hicham El-Zein
J. Ian Munro
Matthew Robertson

References

  1. Diego Arroyuelo, Gonzalo Navarro, and Kunihiko Sadakane. Reducing the space requirement of LZ-index. In Moshe Lewenstein and Gabriel Valiente, editors, Proceedings of CPM, volume 4009 of Lecture Notes in Computer Science, pages 318-329. Springer, 2006. Google Scholar
  2. Jérémy Barbay, Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theor. Comput. Sci., 387(3):284-297, 2007. Google Scholar
  3. Jérémy Barbay, Meng He, J. Ian Munro, and Srinivasa Rao Satti. Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms, 7(4):52, 2011. Google Scholar
  4. Mariano Paulo Consens and Timothy Snider. Maintaining very large indexes supporting efficient relational querying, August 14 2001. US Patent 6,275,822. Google Scholar
  5. Hicham El-Zein, J. Ian Munro, and Venkatesh Raman. Tradeoff between label space and auxiliary space for representation of equivalence classes. In Proceedings of ISAAC, PartII, volume 8889 of Lecture Notes in Computer Science, pages 543-552. Springer, 2014. Google Scholar
  6. Hicham El-Zein, J. Ian Munro, and Siwei Yang. On the succinct representation of unlabeled permutations. In Proceedings of ISAAC, volume 9472 of Lecture Notes in Computer Science, pages 49-59. Springer, 2015. Google Scholar
  7. Faith E. Fich, J. Ian Munro, and Patricio V. Poblete. Permuting in place. SIAM Journal on Computing, 24(2):266-278, 1995. Google Scholar
  8. Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. Rank/select operations on large alphabets: a tool for text indexing. In Proceedings of Seventeenth SODA, pages 368-373. ACM Press, 2006. Google Scholar
  9. Daniel S. Hirschberg and James Bartlett Sinclair. Decentralized extrema-finding in circular configurations of processors. Communications of the ACM, 23(11):627-628, 1980. Google Scholar
  10. Moshe Lewenstein, J. Ian Munro, and Venkatesh Raman. Succinct data structures for representing equivalence classes. In Proceedings of ISAAC, PartII, volume 8283 of Lecture Notes in Computer Science, pages 502-512. Springer, 2013. Google Scholar
  11. J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct representations of permutations and functions. Theoretical Computer Science, 438:74-88, 2012. Google Scholar
  12. Gonzalo Navarro and Veli Mäkinen. Compressed full-text indexes. ACM Comput. Surv., 39(1), 2007. Google Scholar
  13. Michael Rubinstein. The distribution of solutions to xy = nod a with an application to factoring integers, 2009. Google Scholar
  14. Kunihiko Sadakane. New text indexing functionalities of the compressed suffix arrays. J. Algorithms, 48(2):294-313, 2003. Google Scholar
  15. I. Vinogradov. Selected works. With a biography by K. K. Mardzhanishvili. Translated from the Russian by Naidu Psv. Translation edited by Yu. A. Springer-Verlag, Berlin, 1985. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact