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

Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений <math>\rho_1, ..., \rho_k</math> называется ''максимальной'', если не существует ориентированного обращения в <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k</math>. В частности, последовательность сортировки является максимальной, в то же время обратное неверно.

'''Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части <math>S = S_1, S_2</math>, и <math>S_1, S', S_2</math> является последовательностью ориентированных обращений.'''

Это позволяет строить последовательности ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая последовательность сортировки.