Inverting Permutations In Place

Permutation;In Place;Invert;Computer Science

Robertson, Matthew

University of Waterloo

关键词: Permutation;    In Place;    Invert;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9535/3/Robertson_Matthew.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We address the problem of quickly inverting the standard representation of a permutation on $n$ elements in place. First, we present a naive algorithm to do it using $O(log n)$ extra bits in $O(n^2)$ time in the worst case. We then improve that algorithm, using a small bit vector, to use $O(sqrt n)$ extra bits in $O(n sqrt n)$ time. Using a different approach, we present an algorithm to do it using $O(sqrt n log n)$ extra bits in $O(n log n)$ time. Finally, for our main result, we present a technique that leads to an algorithm to invert the standard representation of a permutation using only $O(log^2 n)$ extra bits of space in $O(n log n)$ time in the worst case.