ITERATIVE DECOMPOSITION OF PERMUTATIONS

Abstract

Given symmetric group Sn and its subgroup (SqX Sp), P + q = n, we establish necessary and sufficient conditions for the decomposition of Sn into left cosets of (SqX Sp) in Sn. If n = 2m, (m = 1,2, ... ) and p = q = n/2 then by iteration we obtain a decomposition of an arbitrary nE Sn in the form n = (f3~)(f3~, fig) ... (f3'/.r12-1, •.. , f3~\I), where N = logz nand f3i is the j-th left coset leader obtained on the i-th stage. We develop an O(n log n) serial algorithm for the programming the tree cellular permutations networks which result from the above decomposition scheme.