Предположим, у меня есть неизвестный вектор v и перестановка p.Как найти обратную перестановку?
Как я могу восстановить v от v(p) и p?
Эквивалентным вопросом было бы найти перестановку q такой, что p(q) = [1 2 ... n]?
Поскольку это будет работать в замкнутом цикле, мне нужно, чтобы ответ был векторизован (и эффективен).
Если вы хотите обратную перестановку q из p, она не станет более эффективным, чем:
q(p) = 1:numel(p);
Вы можете, таким образом, восстановить v от vp = v(p) и p через:
q(p) = 1:numel(p);
v = vp(q);
или даже быстрее без явного построения q:
v(p) = vp;
(Вы, возможно, заметили, что v = vp(q) соответствует v == P^(-1)*vp и v(p) = vp соответствует P*v == vp для соответствующих операторов перестановок (матриц) P = sparse(1:numel(p),p,1) и P^(-1)==P.'==sparse(p,1:numel(p),1). Таким образом, получая тот же результат.)
Если вы используете это в цикле, не забудьте правильно сбросить q или v соответственно до [] перед этой операцией. В случае изменения длины p в противном случае вы получили бы неправильные результаты, если новый p был короче старого p.
С ismember -
[~,q] = ismember(1:numel(p),p)
С intersect -
[~,~,q] = intersect(1:numel(p),p)
С bsxfun -
[q,~] = find(bsxfun(@eq,[1:numel(p)],p(:)))
Следует учесть сложность этих функций и насколько это будет стоить для запуска такого подхода? (большая нотация O была бы прекрасна). Я боюсь, что она будет работать в квадрическом времени, что для меня не вариант. – amit
@amit Что вы 'ndims (v)'? – Divakar
Как я уже сказал, 'v' является * вектором *, поэтому' ndims (v) = 2' – amit
Это может быть интересно, поскольку OP пытается запустить его в узком цикле, так что '1: numel (P)' может храниться в векторе и использоваться итеративно в этом узком цикле! Таким образом, это может быть более эффективным. – Divakar
Это умный и быстрый способ! Однако вы получите проблемы, если поместите его в цикл, а p будет в несколько раз меньше элементов, но если вы добавите что-то вроде 'q = q (1: numel (p)),' впоследствии будет исправлено (и все еще будет быстрее, чем мой метод). –
@JensBoldsen: Да, 'q' или' v' resp. должен быть пуст до этого, чтобы он работал правильно. Я добавил его в ответ, чтобы уточнить. – knedlsepp