Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSweep maps: A continuous family of sorting algorithms
245
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We define a family of maps on lattice paths, called sweep maps, that assign levels to each step in the path and sort steps according to their level. Surprisingly, although sweep maps act by sorting, they appear to be bijective in general. The sweep maps give concise combinatorial formulas for the q,t-Catalan numbers, the higher q,t-Catalan numbers, the q,t-square numbers, and many more general polynomials connected to the nabla operator and rational Catalan combinatorics. We prove that many algorithms that have appeared in the literature (including maps studied by Andrews, Egge, Gorsky, Haglund, Hanusa, Jones, Killpatrick, Krattenthaler, Kremer, Orsina, Mazin, Papi, Vaille, and the present authors) are all special cases of the sweep maps or their inverses. The sweep maps provide a very simple unifying framework for understanding all of these algorithms. We explain how inversion of the sweep map (which is an open problem in general) can be solved in known special cases by finding a bounce path for the lattice paths under consideration. We also define a generalized sweep map acting on words over arbitrary alphabets with arbitrary weights, which is also conjectured to be bijective.
rate research
Read More
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.
We compute the degree complexity of a family of birational mappings of the plane with high order singularities.
Sorting input objects is an important step in many machine learning pipelines. However, the sorting operator is non-differentiable with respect to its inputs, which prohibits end-to-end gradient-based optimization. In this work, we propose NeuralSort, a general-purpose continuous relaxation of the output of the sorting operator from permutation matrices to the set of unimodal row-stochastic matrices, where every row sums to one and has a distinct arg max. This relaxation permits straight-through optimization of any computational graph involve a sorting operation. Further, we use this relaxation to enable gradient-based stochastic optimization over the combinatorially large space of permutations by deriving a reparameterized gradient estimator for the Plackett-Luce family of distributions over permutations. We demonstrate the usefulness of our framework on three tasks that require learning semantic orderings of high-dimensional objects, including a fully differentiable, parameterized extension of the k-nearest neighbors algorithm.
Garsia and Xin gave a linear algorithm for inverting the sweep map for Fuss rational Dyck paths in $D_{m,n}$ where $m=knpm 1$. They introduced an intermediate family $mathcal{T}_n^k$ of certain standard Young tableau. Then inverting the sweep map is done by a simple walking algorithm on a $Tin mathcal{T}_n^k$. We find their idea naturally extends for $mathbf{k}^pm$-Dyck paths, and also for $mathbf{k}$-Dyck paths (reducing to $k$-Dyck paths for the equal parameter case). The intermediate object becomes a similar type of tableau in $mathcal{T}_mathbf{k}$ of different column lengths. This approach is independent of the Thomas-Williams algorithm for inverting the general modular sweep map.
Computing the reversal distances of signed permutations is an important topic in Bioinformatics. Recently, a new lower bound for the reversal distance was obtained via the plane permutation framework. This lower bound appears different from the existing lower bound obtained by Bafna and Pevzner through breakpoint graphs. In this paper, we prove that the two lower bounds are equal. Moreover, we confirm a related conjecture on skew-symmetric plane permutations, which can be restated as follows: let $p=(0,-1,-2,ldots -n,n,n-1,ldots 1)$ and let $$ tilde{s}=(0,a_1,a_2,ldots a_n,-a_n,-a_{n-1},ldots -a_1) $$ be any long cycle on the set ${-n,-n+1,ldots 0,1,ldots n}$. Then, $n$ and $a_n$ are always in the same cycle of the product $ptilde{s}$. Furthermore, we show the new lower bound via plane permutations can be interpreted as the topological genera of orientable surfaces associated to signed permutations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
