# How can I keep track of the state of a sequence after rotating parts of it multiple times?

Given a sorted array

1 2 3 4 5 6 7 8


and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the right by one), leaving the following for N = 3

4 1 2 3 5 6 7 8


I need to be able to figure out the state of the array, after performing an arbitrary number of these operations.

I've implemented a simple algorithm using std::rotate that simulates this behavior, but the problem is that my input data set is too large, and rotating the physical array gets really slow.

I've also tried doing this in a std::list (linked list), while keeping a separate array of pointers to every K-th element, so that I could access anywhere in the list in near constant time, while benefiting from the fast removal. This approach requires moving the pointers (or iterators in my implementation) every time I rotate, but since I have less pointers than the actual elements in the array (say 1 pointer per 1000 list elements), this isn't so expensive. All in all, this solution turns out to be about 2 times faster than the vector in some cases, in others it's less fast, but it's still too slow.

I don't need to store the actual array, I only need to be able to compute the value of any element in it. I can see how to do this easily if I only had to do one rotation, where the 0th index would be the rotated element, everything before the rotated element would be shifted one to the right by one and everything on the right side of the element would be kept in place, but I don't see how to keep this up when I do multiple rotations.

One of the possible solutions I found was using interval trees, though this seems rather complex and I'm not sure if it would be more efficient given the high number of rotations needed.

TL;DR: Given a sequence of the first N natural numbers, perform K rotations and figure out the final state of the sequence. For the sake of example, set N = 10^6 and K = 10^5.

• Have you tried a doubly-connected list? It will require only three pointer reassignments, however the search for the element to be made the first one will be sequential. What is "TL;DR" by the way? Also, you said almost nothing about size of rotation - is it constant? – HEKTO Dec 10 '14 at 20:36
• Also you can improve the sequential search, if you remember the position of previous search and move forward or backward only by difference (assuming the size of rotation varies) – HEKTO Dec 10 '14 at 20:44
• @HEKTO Can you clarify in a proper answer? For his example, his $K$ can get close to $N$, doing 'remember' read like what you seem to suggest will lead to $O(k^2)$ which is close enough to $O(n^2)$ unless I misunderstand your idea. – InformedA Dec 10 '14 at 21:01
• @InstructedA - the OP said "K rotations", it's not the rotation size AFAIU. The idea is simple - it's no need to start counting from the beginning every time, if we already have a previous position, which might be closer to what we want now – HEKTO Dec 10 '14 at 21:06
• Why don't you just use some kind of balanced binary search tree that supports insertion/removal in $O(\log n)$? – Tom van der Zanden Dec 10 '14 at 21:29

But the problem here is that the values of the elements do not matter, since the rotations can change the order arbitrarily (actually, I do not understand why they are first sorted).

You want to find an element according to its index in the list, not its value. A way to do that is to keep with each node of the tree the number of list elements (leaves) dominated by its left daughter. Then very simple arithmetics will tell you at each node whether the $n^th$ element of the list is to be found under the left or the right daughter, and you acess it in $O(\log n)$ steps if the tree is properly balanced.

Then the element in inserted at the beginning, which can also be done in $O(\log n)$ steps.

Then you need to rebalance the tree when it gets unbalanced. But there are techniques to maintain balancing.

The same should be possible with skiplist, again relying on some size information to access by index rather than by value.

• Values of elements don't matter (and sorted initially) because the OP is actually interested in permutations – HEKTO Dec 11 '14 at 16:04

If I am not mistaken, the complexity is $O(N+K)$, so $O(N)$. Work backwards. If the last rotation is $r_1$ then this means $r_1$ is the first element in your list. Keep working backwards and ignore all earlier occurrences of $r_1$, they do not matter. Now if you find $r_2$ that is the second element in your list. Continue, ignoring the earlier $r_i$ values.

When done, copy all remaining values in the order of the original array.

Keeping track of all values seen can be done using a boolean array of size $N$. Seems a little large, but I guess we need to check all $N$ array elements anyhow.

The easiest option is to use Skip List which will give you much better average case complexity. It will be $O(k\log n)$ from what the wiki page says:

Skip list will give you $O(\log n)$ when you query for an item in the average case. Similarly, it gives you $O(\log n)$ in insertion and removal in the average case. Together, this means that the average cost for your operation is $O(\log n)$

• When you use array, the average cost for your operation is $O(n)$ because you have the same probability of $1/n$ for the cost of $0, 1, 2, .. n-1$. The cost all sum to $O(n^2)$ dividing by $n$ giving you $O(n)$.

• When you use linked list with the addition of pointer array to all values, the argument is similar.