A065603 Transposition diameter: maximal number of moves in an optimal sorting of n objects by moving blocks.
0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9
Offset: 1
Links
- V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
- V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
- H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, Sorting a bridge hand, Discrete Math. 241 (2001), 289-300.
- H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, Sorting a bridge hand, Discrete Math. 241 (2001), 289-300.
- R. de A. Hausen, L. Faria, C. M. H. de Figueiredo, and L. A. B. Kowada, On the toric graph as a tool to handle the problem of sorting by transpositions, LNCS 5167 (2008), 79-91.
- J. Gonçalves, L. R. Bueno, and R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.
- Index entries for sequences related to sorting
Formula
It is conjectured that a(n) = ceiling((n+1)/2) for n >= 3 except for n = 13 and 15.
From Petros Hadjicostas, Dec 16 2019: (Start)
ceiling((n-1)/2) <= a(n) <= floor(3*n/4) for n >= 1 (Eriksson et al. (2001) state that these inequalities were proved in Bafna and Pevnzer (1998)).
ceiling((n+1)/2) <= a(n) <= floor((2*n-2)/3) for n >= 3 (see p. 293 in Eriksson et al. (2001)). (End)
Extensions
Definition corrected by Peter Lipp, Dec 16 2008
Edited by Max Alekseyev, Nov 07 2011
Comments