Disjoint direct product decomposition of permutation groups

Abstract

Let $H\le S_n$ be an intransitive group with orbits ${\Omega }_1,{\Omega }_2,\dots ,{\Omega }_k$. Then certainly $H$ is a subdirect product of the direct product of its projections on each orbit, $H{|}_{{\Omega }_1}\times H{|}_{{\Omega }_2}\times \dots \times H{|}_{{\Omega }_k}$. Here we provide a polynomial time algorithm for computing the finest partition $P$ of the $H$-orbits such that $H={\prod }_{c\in P}H{|}_c$ and demonstrate its usefulness in some applications.