Disorders and Permutations Article Swipe
Related Concepts
Computer science
Laurent Bulteau
,
Samuele Giraudo
,
Stéphane Vialette
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.cpm.2021.11
· OA: W3183594101
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.cpm.2021.11
· OA: W3183594101
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.
Related Topics
Finding more related topics…