LIPIcs.CPM.2021.11.pdf
- Filesize: 1.22 MB
- 15 pages
Document
Disorders and Permutations
Authors
Samuele Giraudo 
,
Stéphane Vialette
-
Part of:
Volume:
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-30
File
Document Identifiers
Author Details
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
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Permutations and combinations
Keywords
- Permutation
- Algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Bóna. Combinatorics of Permutations, Second Edition. Discrete mathematics and its applications. CRC Press, 2012.
-
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.
-
M. De Biasi. Permutation Reconstruction from Differences. Electron. J. Combin., 1(4):4.3, 2014.
-
D. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison Wesley Longman, 1998.
-
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.
-
R. P. Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, 2nd edition edition, 2011.
-
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.