Factorization of permutations

DOI10.13001/1081-3810.2849zbMATH Open1323.05008arXiv1303.3776OpenAlexW2964220383MaRDI QIDQ3448189FDOQ3448189

Authors: Chi-Kwong Li, Sharon H. Li, Nung-Sing Sze, Zejun Huang 

Publication date: 23 October 2015

Published in: The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Abstract: We consider the problem of factoring permutations as a product of special types of transpositions, namely, those transpositions involving two positions with bounded distances. In particular, we investigate the minimum number, $delta$, such that every permutation can be factored into no more than $delta$ special transpositions. This study is related to sorting algorithms, Cayley graphs, and genomics.

Full work available at URL: https://arxiv.org/abs/1303.3776

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 798638
• Prefix transpositions on binary and ternary strings
• Minimal factorizations of permutations into star transpositions
• Sorting by bounded block-moves
• Permutations as Products of Transpositions

zbMATH Keywords

permutationCayley graphgenomicssymmetric groupbubble sort

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30)

Cited In (7)

• Inequivalent factorizations of permutations
• Divide-and-permute
• Permutation polynomials and factorization
• Transposition as a permutation: a tale of group actions and modular arithmetic
• Finding composition factors of permutation groups of degree \(n\leq 10^ 6\)
• Sorting on graphs by adjacent swaps using permutation groups
• Enumeration of Payphone Permutations

This page was built for publication: Factorization of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448189)