TY - JOUR
T1 - Quantifying CDS sortability of permutations by strategic pile size
AU - Gaetz, Marisa
AU - Flanagan, Bethany
AU - Scheepers, Marion
AU - Shanks, Meghan
N1 - Publisher Copyright:
© 2020 World Scientific Publishing Company.
PY - 2020/2/1
Y1 - 2020/2/1
N2 - The special purpose sorting operation, context directed swap (CDS), is an example of the block interchange sorting operation studied in prior work on permutation sorting. CDShas been postulated to model certain molecular sorting events that occur in the genome maintenance program of some species of ciliates. We investigate the mathematical structure of permutations not sortable by the CDSsorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDSnon-sortability. Our main results include formulas for the number of permutations in Sn with maximum size strategic pile. More generally, we derive a formula for the number of permutations in Sn with strategic pile size k, in addition to an algorithm for computing certain coefficients of this formula, which we call merge numbers.
AB - The special purpose sorting operation, context directed swap (CDS), is an example of the block interchange sorting operation studied in prior work on permutation sorting. CDShas been postulated to model certain molecular sorting events that occur in the genome maintenance program of some species of ciliates. We investigate the mathematical structure of permutations not sortable by the CDSsorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDSnon-sortability. Our main results include formulas for the number of permutations in Sn with maximum size strategic pile. More generally, we derive a formula for the number of permutations in Sn with strategic pile size k, in addition to an algorithm for computing certain coefficients of this formula, which we call merge numbers.
KW - Permutation sorting
KW - context directed swap
KW - factorization into cycles
KW - strategic pile
UR - http://www.scopus.com/inward/record.url?scp=85078014757&partnerID=8YFLogxK
U2 - 10.1142/S1793830920500147
DO - 10.1142/S1793830920500147
M3 - Article
AN - SCOPUS:85078014757
SN - 1793-8309
VL - 12
JO - Discrete Mathematics, Algorithms and Applications
JF - Discrete Mathematics, Algorithms and Applications
IS - 1
M1 - 2050014
ER -