Сортировка перестановок со знаками при помощи обращений (расстояние обращения): различия между версиями

Реализация алгоритма с линейным временем выполнения в виде программы на C доступна на странице http://www.cc.gatech.edu/~bader. Также доступны две другие реализации, разработанные для вычисления кратчайшей последовательности инверсий наряду с длиной. Одна из них принадлежит Ханненхалли и реализует его первый алгоритм [9], выполняющийся за квадратичное время при вычислении расстояний; другая представляет собой Java-апплет, написанный Мантином (http://www.math.tau.ac.il/~rshamir/GR/) и реализующий алгоритм KST [10], но использующий явное представление графа перекрытий и в силу этого также имеющий квадратичное время выполнения. Реализация Ханненхалли работает очень медленно; в ней применен исходный метод Ханненхалли и Певзнера, а не более быстрый – Бермана и Ханненхалли. Апплет KST также оказывается очень медленным из-за явного построения графа перекрытий.