A review and classification of the algorithms for SBPR problem (Sorting Permutations By Prefix Reversals)

Abstract

The ordering of permutations by prefix reversal (SPBR) is a classical combinatorial optimization problem whose main objective is to order a permutation of n elements by reversing the leftmost blocks (prefixes) of that permutation. Technically, a given permutation  pi must be transformed into an identity permutation called i. Similarly, it could be compared in magnitude to a stack of pancakes that must be rearranged with a spatula by inserting at any point and reversing their order so that after several iterations the stack is ordered. However, since 2012 it has been shown that this problem belongs to the NP Hard class, which makes it infeasible in practical terms to construct an optimal solution in polynomial time or lower. In fact, in recent years, the academic community has been trying to use heuristic and metaheuristic approximation algorithms that provide better results approaching the global optimum. In this research, heuristic and metaheuristic algorithms were designed and implemented based on the criteria proposed by the reviewed literature. In addition, a family of life-inspired metaheuristics was proposed, which have proven to be very efficient in finding solutions in large search spaces. The algorithms used during the implementation of this research work were written with Python, using the Google Colab tool. In addition, the basic concepts related to modern permutation theory and its elementary sorting methods were reviewed. The evaluation of the algorithms was performed using the set of results provided by the scientific literature in the last 10 years. The advantages and disadvantages of the use of the different proposed methods were shown and, ultimately, it is shown which of them will prove to be the most appropriate depending on the context in which the problem is placed.