Unshuffling Permutations: Trivial Bijections and Compositions

Abstract

Given permutations $\pi$, $\sigma _1$ and $\sigma _2$, the permutation $\pi$ (viewed as a string) is said to be a shuffle of $\sigma _1$ and $\sigma _2$, in symbols , if $\pi$ can be formed by interleaving the letters of two strings $p_1$ and $p_2$ that are order-isomorphic to $\sigma _1$ and $\sigma _2$, respectively. Given a permutation $\pi \in S_{2n}$ and a bijective mapping $f : S_n \rightarrow S_n$, the f-Unshuffle-Permutation problem is to decide whether there exists a permutation $\sigma \in S_n$ such that . We consider here this problem for the following bijective mappings: inversion, reverse, complementation, and all their possible compositions. In particular, we present combinatorial results about the permutations accepted by this problem. As main results, we obtain that this problem is $\mathsf {NP}$-complete when f is the reverse, the complementation, or the composition of the reverse with the complementation.

Partially supported by Laboratoire International Franco-Québécois de Recherche en Combinatoire (LIRCO) (G. Fertin and S. Vialette), supported by the Individual Discovery Grant RGPIN-2016-04576 from Natural Sciences and Engineering Research Council of Canada (NSERC) (S. Hamel).