*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 31 марта 2010 г.

Веселые перестановки

Вдогонку к вопросу о векторе предлагаю еще блиц вопрос (ни разу не претендую на оригинальность, но вопрос родился лично у меня в процессе обдумывания алгоритма формирования таблиц market depth): есть некоторая произвольная конечная последовательность (массив, строка и т.д.). Повторения значений возможны. Также задана вторая последовательность такой же длины, состоящая в точности из тех же элементов, что и первая, но расположенных в другом порядке.

Вопрос: как на месте преобразовать первую последовательность во вторую, если в плане перемещения/копирования элементов есть только одна функция - обмен двух соседних элементов. Произвольный доступ к одиночным элементам есть только на чтение. Для перезаписи/изменения элементов надо пользоваться данной функцией обмена.

Конечно, интересно иметь и оценку сложности.

Мой ответ, если кому интересно, будет завтра.

Комментариев нет:

Отправить комментарий