文章基本信息

标题：Raising Permutations to Powers in Place
本地全文：下载
作者：Hicham El-Zein ; J. Ian Munro ; Matthew Robertson 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：29:1-29:12
DOI：10.4230/LIPIcs.ISAAC.2016.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Algorithms; Combinatorics; Inplace; Permutations; Powers