Abstract:
A special sorting operation called Context Directed Swap, and denoted \(\textbf{cds}\), performs certain types of block interchanges on permutations. When a permutation is sortable by \(\textbf{cds}\), then \(\textbf{cds}\) sorts it using the fewest possible block interchanges of any kind. This work introduces a classification of permutations based on their number of \(\textbf{cds}\)-eligible contexts. In prior work an object called the strategic pile of a permutation was discovered and shown to provide an efficient measure of the non-\(\textbf{cds}\)-sortability of a permutation. Focusing on the classification of permutations with maximal strategic pile, a complete characterization is given when the number of \(\textbf{cds}\)-eligible contexts is close to maximal as well as when the number of eligible contexts is minimal. A group action that preserves the number of \(\textbf{cds}\)-eligible contexts of a permutation provides, via the orbit-stabilizer theorem, enumerative results regarding the number of permutations with maximal strategic pile and a given number of \(\textbf{cds}\)-eligible contexts. Prior work introduced a natural two-person game on permutations that are not \(\textbf{cds}\)-sortable. The decision problem of which player has a winning strategy in a particular instance of the game appears to be of high computational complexity. Extending prior results, this work presents new conditions for player ONE to have a winning strategy in this combinatorial game.