  Two permutations $s$ and $t$ are $k$-similar if they can be decomposed into
subpermutations $s^1, \ldots, s^k$ and $t^1, \ldots, t^k$ such that $s^i$ is
order-isomorphic to $t^i$ for all $i$. Recently, Dudek, Grytczuk and Ruci\'nski
posed the problem of determining the minimum $k$ for which two permutations
chosen independently and uniformly at random are $k$-similar. We show that two
such permutations are $O(n^{1/3}\log^{11/6}(n))$-similar with high probability,
which is tight up to a polylogarithmic factor. Our result also generalises to
simultaneous decompositions of multiple permutations.
