Permutation Arrays

June 30, 2014

I have been studying data structures this week, as part of my continuing work on March. In particular I have been thinking about the more effective data structure for an ordered collection. Most language use either an array or a linked-list. Arrays have fact access speed (typically O(1)) but poor CRUD speeds (typically O(n)). Whereas linked-lists have the opposite characteristics. So I have been considering the possibility of using a structure that falls in between these two extremes.

The most promising (and perhaps most obvious) candidate is the binary search tree. It has reasonably good performance characteristics across the board (worst case O(log n)). As an implementation optimization concrete structure would a T*-tree (threaded T-tree).

Another possibility that I just recently discovered is the Hashed Array Tree. It’s name is a little odd considering it is has nothing to do with hashing functions, but it has a cool acronym, HAT. Regardless, it has some very nice properties such a O(1) access time and O(&sqrt;n) for CRUD operations. It also has a much smaller memory foot print than the T*-tree. Even better, it can be generalized to N dimensions (three being a good all around focal dimension) for improved performance for large data sets.

But one other idea came to mind, that I have not heard of anyone espousing before. I had been thinking about the the order of elements on a stack and how a programmer might want to reorganize them to improve the flow of concatenative code. Naturally I thought about permutations. Later when thinking about the poor performance characteristics of inserting and deleting elements in and array, I has one of those light-bulb moments.

For an array, if an element needs to be inserted between two others, all the elements after that position will have to shifted downward in memory; and vice-versa for deletion. There are very inefficient procedures. (Makes you wonder why they haven’t invented memory that can shift directly in hardware). My insight to a potential remedy for this abysmal performance was to instead track a reference permutation, a sort-of point of origin, if you will, and adjust it as necessary rather than moving anything around at all. Permutation numbers are enumerate any possible order of a collection. For example, three elements can be in any of six possible orders.

The permutations above are simply listed in numerical sort order, but there are a variety of formula for ordering permutations. Now, if a permutation numbers can be calculated quickly enough to serve the purposes of insertion, deletion and access, than it is a simple matter to create an array structure with superior characteristics for insertion and deletion, potentially on the order of O(1). There is one caveat to this, an over allocation strategy must used to insure enough insertion space for new elements. It will slow things down somewhat but it’s amortization across all operations is relatively small.

A more serious obstruction to this idea is the size of permutation numbers. They grow at a factorial rate in proportion to the size of the collection. So, for instance, an array with just 50 items would require a 256-bit number, or so, to enumerate all it’s possible permutations. This is rather huge, albeit doable. It would be nice if there were a way to limit the number of possible permutations to a workable subset, but that might not be possible without degrading performance unacceptably. But at this point, this is conjecture. The more pressing issue is to determine if it is even possible to quickly calculate these permutation numbers. In particular we need these functions:

: perm ( int+ ) ;
: index ( int+ ) ;
: offset ( int+ ) ;

(* given a permutation number and an insertion index return the new permutation number *)
: insert_perm ( perm index offset -> perm )

(* given a permutation number and a deletion index return the new permutation number *)
: delete_perm ( perm index offset -> perm )

(* given a permutation return the corresponding sequence of ordered offsets,
   preferably this will return a stream, but an array would be acceptable    *)
: sequence ( perm -> stream )

(* given a permutation number and a positional index get the memory offset *)
: offset ( perm index -> offset )

I imagine that to do this we need to have an ordering of permutations best suited to our requirements of insertion and deletion. To ease our problem we can think in terms of a stack where every new entry will always be pushed to the top of the allocated memory, regardless of it’s actual index in the collection.

We know that the insertion of element in an array will physically require the positions of all subsequent elements to shifted down a slot, and the opposite for deletion. So with regards to a permutation every entry with a value great than the index’s must be incremented by one, or subtracted for deletion.

In the above _ is our unallocated space. Interestingly, adding an element to the top of the array does not change the permutation number, only the size.

Numerical sort order is not however an optimal formula for the permutations because we require numbers that have a relative relationship that can be quickly calculated from one another. As it turns out, a nearly perfect sequencing was figured out quite a long time ago. It was already known to 17th-century English change ringers. In modern times it is known as the Steinhaus–Johnson–Trotter algorithm12. The algorithm is a close fit for our needs because it generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations differ by swapping two adjacent values.

So why does this ordering work so well for us? Because we are always working from one end of the physical memory, and insertion or deletion can be thought of as sequence of swaps working from the end of the sequence to the target index. A simple illustration will clarify. Say we have a four element array with one unallocated slot and we wish to insert a new element into the middle of the array. We can transition the unallocated slot into the middle of the array one step at a time, swapping adjacent elements.

[ _ 1 2 3 4 ]  ->  [ 1 _ 2 3 4 ]  ->  [ 1 2 _ 3 4 ]

But in our case we don’t want to do that with physical memory, but rather our permutation number. If the permutations number are in order of adjacent transpositions, as the are in the Steinhaus–Johnson–Trotter algorithm, then it should be simple matter of adding the number of places for an insert, or subtracting them for a deletion to get the new permutation number.

Unfortunately the Steinhaus–Johnson–Trotter algorithm isn’t quite as ideal as might prefer because every other set of transitions moves in the opposite direction. This means we will have to determine which direction any permutation number is facing via its modulo with respect to its size. Nonetheless, the functions to determine insert and delete permutation numbers should be relatively trivial.

The remaining difficulty is in calculating the sequence and offset functions. These may prove more a bit more difficult, but if the sequence function can computed then the offset function can at least be created from it. The real salient question is, how fast? The naive way to calculate the sequence function is to generate all the possible permutation up to the given number. We know how to do that. But this is preposterously inefficient. An array with a mere twenty elements could require weeks of computation. Obviously that isn’t going to work. We need a function that can deduce the sequence from the number itself. As it turns out, it is possible, at least for a certain ordering of the permutations. Whether it can be done for our ordering of permutations I have yet to determine, but it seems likely. However, it may be a O(n) computation. It were the only means to determine the ith offset in the sequence then it would not be sufficient for fast random access. But if it were possible to construct the sequence, or get the ith offset, in O(log n) time, then it would be very feasible. In fact, because the algorithm is independent of the actual memory it could be built into hardware and calculated extremely quickly. Of course so much the better if there is an O(1) algorithm for calculating the offset, but I suspect that is unlikely.

The end result of such a structure would allow for O(1) insert, O(1) delete and O(log n) lookup in software, or the equivalent of O(1) lookup if accelerated in hardware –in effect, the perfect data structure. It’s only caveat is still memory allocation. But there are effective strategies for dealing with this that would have only a small effect on overall performance, e.g Hashed Array Trees, and would also be beneficial in providing a means of persistence for functional languages.

I think the algorithm to compute the sequence of the permutation is basically as follows:

given the permutation number P and the size S
calculate the quotient and modulus S of P, i.e. Q=floor(P/S), M=P%S
M is the position in the S index if Q is odd
M* is the position in the S index if Q is even
  where M* is the converse modulus, |M-S+1|
set P=Q and S=S-1 and repeat from step one,
  skipping previously placed indexes

The skipping part is probably the trickiest part to the algorithm. There are two things to notice about the procedure. The first and good news is that it will generate the results in order, in this case from last index to first. But opposite can easily be achieved by reversing the orientation of the SJT pattern, no big deal. The bad news is that it is definitely O(n) and to a particular position we must calculate the prior positions first. Actually, that might not quite be true. I think we can get the position of the kth index if we take the modulus of the k!, but we won’t know where to put it exactly because we won’t know positions we have to skip. Damn, I knew that skipping was going to be tricky part.

← All posts