2021/03/07 by Dimitrov, Stoyan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.04332
We study sorting by queues that can rearrange their content by applying permutations from a predefined set. These new sorting devices are called shuffle queues and we investigate those of them corresponding to sets of permutations defining some well-known shuffling methods. If ℚΣ is the shuffle queue corresponding to the shuffling method Σ, then we find a number of surprising results related to two natural variations of shuffle queues denoted by ℚΣ′ and ℚΣ^\textsfpop. These require the entire content of the device to be unloaded after a permutation is applied or unloaded by each pop operation, respectively. First, we show that sorting by a deque is equivalent to sorting by a shuffle queue that can reverse its content. Next, we focus on sorting by cuts. We prove that the set of permutations that one can sort by using ℚcuts′ is the set of the 321-avoiding separable permutations. We give lower and upper bounds to the maximum number of times the device must be used to sort a permutation. Furthermore, we give a formula for the number of n-permutations, pn(ℚΣ′), that one can sort by using ℚΣ′, for any shuffling method Σ, corresponding to a set of irreducible permutations. We also show that pn(ℚΣ^\textsfpop) is given by the odd indexed Fibonacci numbers F2n-1, for any shuffling method Σ having a specific "back-front" property. The rest of the work is dedicated to a surprising conjecture inspired by Diaconis and Graham, which states that one can sort the same number of permutations of any given size by using the devices ℚIn-sh^\textsfpop and ℚMonge^\textsfpop, corresponding to the popular In-shuffle and Monge shuffling methods.