Reconstruction of permutations distorted by single transposition errors

Elena Konstantinova, Vladimir Levenshtein, Johannes Siemons

The reconstruction problem for permutations on $n$ elements from their erroneous patterns which are distorted by transpositions is presented in this paper. It is shown that for any…