ITERATIVE DECOMPOSITION OF PERMUTATIONS

Authors

  • Z. Kokosinski

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.

Citation data from Crossref and Scopus

How to Cite

Kokosinski, Z. (1991) “ITERATIVE DECOMPOSITION OF PERMUTATIONS”, Periodica Polytechnica Transportation Engineering, 19(1-2), pp. 49–55.

Issue

Section

Articles