License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.29
URN: urn:nbn:de:0030-drops-67992
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6799/
Go to the corresponding LIPIcs Volume Portal


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

Raising Permutations to Powers in Place

pdf-format:
LIPIcs-ISAAC-2016-29.pdf (0.5 MB)


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.

BibTeX - Entry

@InProceedings{elzein_et_al:LIPIcs:2016:6799,
  author =	{Hicham El-Zein and J. Ian Munro and Matthew Robertson},
  title =	{{Raising Permutations to Powers in Place}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6799},
  URN =		{urn:nbn:de:0030-drops-67992},
  doi =		{10.4230/LIPIcs.ISAAC.2016.29},
  annote =	{Keywords: Algorithms, Combinatorics, Inplace, Permutations, Powers}
}

Keywords: Algorithms, Combinatorics, Inplace, Permutations, Powers
Seminar: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 02.12.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI