# Dynamic permutation cycle data

Let $$\pi \in S_n$$ be a permutation of $$\{1, \ldots, n\}$$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?

• sameCycle($$\pi,x,y$$): determines whether $$x$$ and $$y$$ belong to the same permutation cycle;
• transpose($$\pi,x,y$$): replaces $$\pi$$ by the composition $$(xy)\pi$$ of the transposition $$(xy)$$ with $$\pi$$.

This can be viewed as a special case of the fully-dynamic graph connectivity problem in which the connected components are always cycles. Therefore it admits such a data structure, but one may hope that the cycle structure makes the problem easier and/or faster.

• Sounds something that should be doable with link/cut trees with $O(\log n)$ complexity because cycles are just one edge away from trees. Nov 16 '20 at 20:58