Listing All Sorting Reversals in Quadratic Time

摘要

We describe an average-case O(n~2) algorithm to list all reversals on a signed permutation n that, when applied to 71, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Q(n~2) in the worst case.