New Results on the Reconstruction of Permutations Distorted By Single Kendall τ-Errors
Jiyong Lu, Xiang Wang · IEEE Access · 2022
The reconstruction problem for permutations onnelements from their erroneous patterns which are distorted by single Kendall τ-errors was presented by Konstantinova et al. in 2007. To date, some authors solved some cases where the transmitted permutation can be arbitrary and the erroneous patterns are distorted by at most two or three Kendall τ-errors. In this paper, we study the setup where the transmitted permutation onnelements can be arbitrary and the erroneous patterns are distorted by at most four Kendall τ-errors. In this scenario, it is shown thatn3-n-3/3 erroneous patterns are needed to reconstruct an unknown permutation from an arbitrary unknown permutation for anyn≥ 9.