DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.46

Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations

Authors: Vincent Pilaud and Aaron Williams

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

Wiggly permutations were introduced by Bapat and Pilaud (Wigglyhedron Mathematische Zeitschrift 2025). We positively answer one of their conjectures by finding a Hamilton path in the wiggly flip graph that is isomorphic to the wigglyhedron. Our path provides a Gray code in which successive wiggly permutations are obtained by a single jump or hop, meaning that one or two consecutive symbols move past some number of smaller symbols. The Gray code has a simple greedy description that produces a recursive zig-zag pattern reminiscent of plain changes for permutations. More broadly, our results extend Algorithm J and the series of papers on zig-zag languages initiated by Hartung, Hoang, Mütze and Williams (Combinatorial Generation via Permutation Languages SODA 2020). Finally, we use wiggly changes as the basis for an 𝒪(n)-time delay generation algorithm.

Cite as

Vincent Pilaud and Aaron Williams. Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pilaud_et_al:LIPIcs.WADS.2025.46,
  author =	{Pilaud, Vincent and Williams, Aaron},
  title =	{{Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.46},
  URN =		{urn:nbn:de:0030-drops-242778},
  doi =		{10.4230/LIPIcs.WADS.2025.46},
  annote =	{Keywords: permutations, wiggly permutations, pattern avoidance, permutahedron, wigglyhedron, Hamilton path, flip graph, Gray code, combinatorial generation, generation algorithm}
}

Search Results

Documents authored by Pilaud, Vincent

Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations

Abstract

Cite as

Thanks for your feedback!

Could not send message