Document Open Access Logo

Disorders and Permutations

Authors Laurent Bulteau, Samuele Giraudo , Stéphane Vialette

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2021.11.pdf
  • Filesize: 1.22 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
Keywords
  • Permutation
  • Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The additive x-disorder of a permutation is the sum of the absolute differences of all pairs of consecutive elements. We show that the additive x-disorder of a permutation of S(n), n ≥ 2, ranges from n-1 to ⌊n²/2⌋ - 1, and we give a complete characterization of permutations having extreme such values. Moreover, for any positive integers n and d such that n ≥ 2 and n-1 ≤ d ≤ ⌊n²/2⌋ - 1, we propose a linear-time algorithm to compute a permutation π ∈ S(n) with additive x-disorder d.

Cite As Get BibTex

Laurent Bulteau, Samuele Giraudo, and Stéphane Vialette. Disorders and Permutations. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CPM.2021.11

Author Details

Laurent Bulteau
  • LIGM, Univ Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France
Samuele Giraudo
  • LIGM, Univ Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France
Stéphane Vialette
  • LIGM, Univ Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France

References

  1. M. Bóna. Combinatorics of Permutations, Second Edition. Discrete mathematics and its applications. CRC Press, 2012. Google Scholar
  2. P. Brändén and A. Claesson. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electron. J. Combin., 18(2):Paper 5, 14, 2011. Google Scholar
  3. M. De Biasi. Permutation Reconstruction from Differences. Electron. J. Combin., 1(4):4.3, 2014. Google Scholar
  4. D. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison Wesley Longman, 1998. Google Scholar
  5. P. A. MacMahon. The Indices of Permutations and the Derivation Therefrom of Functions of a Single Variable Associated with the Permutations of any Assemblage of Objects. Amer. J. Math., 35(3):281-322, 1913. Google Scholar
  6. R. P. Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, 2nd edition edition, 2011. Google Scholar
  7. W. Yu, H. Hoogeveen, and J. K. Lenstra. Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard. J. Sched., 7(5):333-348, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact