Optimizing Comparisons in the Construction of Insertion Tableau for Permutations

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\sigma)$</tex> into tableau is known as the RSK algorithm. Each element from permutation is inserted into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex>, consequently displacing/bumping other elements from the tableau, whereas <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Q$</tex> records the order in which these elements were inserted into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex>. As part of our work, we have devised a modified method for the construction of insertion tableau from the permutation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\sigma)$</tex>, The number of comparisons mainly take place in searching for a position where the next element can be inserted in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex>. In order to solve this problem, we consider <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex> along with the pointer matrix which stores the pointers to the elements in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex> and tracks previous points of insertion to improve subsequent insertions. We use a combination of linear search and binary search on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex> to find the correct location for inserting an element <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\alpha)$</tex> from the permutation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\sigma)$</tex>. 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.