1.14. Обратные перестановки

.23

Ясно, что результирующие значения е{, е2,—, еп будут соответственно 1,2,...,п. В цикле каждый элемент пк встает на свое упорядоченное место ея (см. п.5.7). Подобным образом выполним заполнение элементов перестановкиоднако в

упорядоченное место элемента будем размещать его номер

в исходной перестановке я =

for к=\ to п do л:1 =кшш п~1[пк]=к.

Результирующий векторбудет обратной

перестановкой к я =

X. А. Роте впервые установил связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько же инверсий, сколько исходная.

--Глава 2-=

Представление абстрактных объектов

Рассматривая решение задачи с абстрактной точки зрения, как правило, избегают каких бы то ни было предположений относительно того, как мы намерены автоматизировать ее решение.

В идеале структура вычислительной машины должна соответствовать естественной структуре задачи, однако это требование

часто не выполняется, хотя приспособляемость современной вычислительной техники такова, что она позволяет обойти эти ограничения без труда. Языки высокого уровня при условии, что они должным образом сконструированы, предоставляют в распоряжение программиста, реализующего алгоритм, более удобную «машину», смягчая несоответствие основной машины требованиям алгоритма. Будем считать, что читатель знаком с элементарными понятиями математики и основными типами данных: целыми и вещественными числами, массивами, строками и т. д.

2.1. Представление последовательностей

Любой заданный класс абстрактных объектов может иметь несколько возможных представлений, и выбор наилучшего из них решающим образом зависит от того, каким образом объект будет использован, а также от типа производимых над ним операций.

2.1.1. Смежное представление

В алгоритмах на дискретных структурах часто приходится встречаться с представлением конечных последовательностей и операциями с ними. С вычислительной точки зрения простейшим представлением конечной последовательности ... , является точный список ее членов, расположенных по порядку в смежных ячейках памяти. В языках высокого уровня — это одномерные, двухмерные и т. д. массивы данных. Наряду с очевидными преимуществами последовательное представление имеет и некоторые значительные недостатки. Смежное представление становится

лым, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между SjH sj+1 нового элемента требует сдвигаSj+ j, Sj+2, ...,sn вправо на одну позицию; аналогично исключение 5, требует сдвига тех же элементов на одну позицию влево, как показано в алгоритме 2.1.

Алгоритм 2.1. Включение и исключение элементов при последовательном размещении

{Включипи. элемент z на i-e место }

п=п + 1;

for j-n- 1 to iby-l do sj+l = Sj, = z.

{Исключи/т элемент с i-го места } fori = i to n - I do Sj = sJ+l; n = n — 1.

В обоих случаях включение или удаление элементов при смежном представлении требует перемещения многих элементов. С точки зрения времени обработки такое перемещение элементов может оказаться дорогостоящим из-за сложности операций включения и удаления 0(п).

2.1.2. Характеристические векторы

Важной разновидностью смежного размещения является случай, когда такому представлению подвергается подпоследовательность sk ,sk ,...,sk некоторой основной последовательности В этом случае подпоследовательность можно представить более удобно, используя характеристический вектор — последовательность из нулей и единиц, где разряд равен единице, если принадлежит рассматриваемой подпоследовательности.

Например, для последовательности (1,2,3,4,5,6,7,8,9) характеристический вектор подпоследовательности чисел, кратных 3, имеет вид (0,0,1,0,0,1,0,0,1).

Характеристические векторы полезны в том случае, когда формирование нужной подпоследовательности вьтолняется путем последовательного удаления из основной последовательности элементов, которые не входят в подпоследовательность. Главное неудобство характеристических векторов состоит в том, что они не экономичны.