Factorization of permutations

DOI10.13001/1081-3810.2849MaRDI QIDQ3448189zbMATH OpenOpenAlexFDO

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)

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

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

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)

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.

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

Cited in

(7)

• Enumeration of Payphone Permutations
• 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

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)