Arrays and permutation
1 Permutation, functional form
What exactly is an array. In functional form, an array just have to support the following two operations in constant time.
- : returns .
- : update the array such that returns .
So in some sense, array is just encoding a function . A permutation would be a bijective function . If we are interested in applying a permutation , then to program it is easy, we need to output a new function such that .
This allows us to apply permutations pretty easily by composing functions and cache outputs. In the purely functional view, the layout of the array in memory and the indexing can be different.
2 Permutation, physically
Sometimes one might ask to physically apply the permutation to an array. That is, the th position in the array contains the element in . This is helpful because it helps with cache locality: accessing consecutive elements would be in the same location. Although if the ordering of loops does not matter, there is no harm considering the functional view.
Often, one is tasked to apply permutation to an array physically. It usually ask for running time and space. Unfortunately, there is no way to obtain this running time for all permutations. There are some permutations where this is impossible. A discussion can be found in cstheory.
3 Mix and match
Let's consider the simple case where every element is distinct. One simple solution is the following. Partition the numbers into the median, elements smaller than median, and elements larger than the median. We map the smallest elements into even positions, and remaining elements into the odd position. The algorithm has time. The problem is how to get constant extra place. Because it is unclear how to apply the following permutation in place. The permutation .
What is happening in the physical location. If we applied index transform , then apply physical permutation on the index, what happens for the physical array? It is the same as applying to the physical array. Note this means we can only use this trick to obtain conjugates of .