Optimizing Comparisons in the Construction of Insertion Tableau for Permutations
Shweta Godse, Varunkumar Jayapaul · 2024
Young Tableaux are combinatorial object which have found utility in areas such as combinatorics, cryptography, representation theory etc. Every application has an inherent need for constructing a Young Tableaux efficiently. Young Tableaux consists of two parts namely the Insertion Tableau(P) and the Recording Tableau(Q). The procedure of transforming the input permutation$(\sigma)$into tableau is known as the RSK algorithm. Each element from permutation is inserted into$P$, consequently displacing/bumping other elements from the tableau, whereas$Q$records the order in which these elements were inserted into$P$. As part of our work, we have devised a modified method for the construction of insertion tableau from the permutation$(\sigma)$, The number of comparisons mainly take place in searching for a position where the next element can be inserted in$P$. In order to solve this problem, we consider$P$along with the pointer matrix which stores the pointers to the elements in$P$and tracks previous points of insertion to improve subsequent insertions. We use a combination of linear search and binary search on$P$to find the correct location for inserting an element$(\alpha)$from the permutation$(\sigma)$. Our randomized trials show that the devised algorithm beats the standard RSK algorithm which uses binary search and the Fast RSK algorithm (current theoretical best) devised by Tiskin [15] by approximately 30% on average.