Подстановки Опции

[Reflex]

Помогите смотри есть две подстаноки

Код

(1  2  3  4 ... n ) и   ( 1   2  3   4 ...  n )
(x1 x2 x3 x4 ...xn)  И  (y1 y2 y3 y4 ...yn)

требуеть написать прогамму которая выведет последовательность транспозиций вида

Код

(j,j+1)
(ij,ij+1)

такую, что если первую подстановку умножить на эту последовательность получиться вторая подстановка

Сообщение отредактировано: Reflex - 15.01.2007 16:11

[klem4]

Пример есть ?

[Reflex]

например
(3 2 1) ( 1 3 2)
вывод
(1 3 2) (2 1 3)

грубо говоря какие две соседние цифры в упорядоченном множестве нужно поменять

и последовательность пар номеров соседних цифр, последовательная замена которы друг на друга приводит ко второму упорядоченному множеству

[klem4]

Так стоп. Нам нужно найти последотельность _перестановок_ для первой последовательности такую, чтобы из нее получилась вторая последовательность или что ? Я не пойму, причем тут умножение ?

[Reflex]

объясняю подругому забей на все что было раньше
есть два массива элементов
теперь
надо вывести такую последовательность пар соседних индексов массива, чтесли к первому массиву провести последовательно операцию"ы" для каждой пары чисел.
arr - наш массив
операция ы (a,b : integer)
var tmp : integer;
begin
tmp:=arr[a];
arr[a]:=arr[b];
arr[b]:=tmp;
end;

пример входных данных
(2 3 1 4) (1 3 2 4
Выходные данные : (1 2) (2 3) (1 2)
этот пример показан на картинке

[Malice]

Тебе нужно сделать обычный пузырек с выводом промежуточных результатов (откуда/куда), только сортировку делать не по значению в массиве, а по его индексу в результирующем. Объясним я похлеще тебя

На пальцах:
было (1,2,3,4,5) -надо (3,4,2,1,5)
Индексируем первый массив (добавлением еще одного или с использованием record- не важно):
значения 1,2,3,4,5
Индексы 4,3,1,2,5
Теперь обычный пузырек
если индекс[i]<индекс[i+1] то выводим результат и меняем местами индексы и значения.

[Reflex]

помогите кодом, я не понимаю что делать если вход 1 2 5 и 1 2 3 , тоесть как быстро определить можно ли это сделать и как сделать то что сказал малис

[Malice]

Вот набросок для примера:

const n=4;
type tt=record x,ind:byte; end;
const
    x:array [1..n] of byte=(2,3,1,4); {было}
    y:array [1..n] of byte=(1,3,2,4); {стало}
var z:array [1..n] of tt;
i,j,k:integer;
l:tt;
begin
for i:=1 to n do
for j:=1 to n do
if x[i]=y[j] then begin z[i].x:=x[i]; z[i].ind:=j; end; {Индексируем}
for k:=1 to n do
 for i:=1 to n-1 do
  if z[i].ind> z[i+1].ind then begin
  write ('(',i,',',i+1,') ');
  l:=z[i]; z[i]:=z[i+1]; z[i+1]:=l;
  end;
end.

Проверку на возможность перестановки не делал, считается, что ты его не обманул. Но проверка нужна, ее проще всего добавить в цикл индексирования массива.

[Reflex]

слушай а в такой индексации будет глюк при таком вводе 1 2 2 3 4 и 1 2 3 2 4

[Malice]

слушай а в такой индексации будет глюк при таком вводе 1 2 2 3 4 и 1 2 3 2 4

Согласен, будет. Поправь, для этого достаточно вычеркивания числа из массива Y числа в момент совпадения при индексировании.