The Unclear Impact

is anyone aware of an efficient algorithm for "reordering" a vector/array according to a vector of indices?

reorder : vector [vectorof index] -> vector
reorder([1, 2, 3], [2, 1, 0]) # => [3, 2, 1]
reorder([1, 2, 3], [1, 2, 0]) # => [2, 3, 1]

mutability is okay in the first argument (the data to reorder), but the index vector has to be preserved

@hazel if memory efficiency isn't a concern i would generate a new array by walking the index vector and placing the values in the new array

@dankwraith memory efficiency is a concern

racket code

@dankwraith I've tried these two implementations:

; reorders a vector based on the given indices
; example:
; (vector-reorder (vector 1 2 3) (vector 2 1 0))
; => (vector 3 2 1)
(define (vector-reorder vec indices)
(when (not (= (vector-length indices) (vector-length vec)))
(error 'vector-reorder "index list not same length as vector"))
(for/vector ([idx (in-vector indices)])
(vector-ref vec idx)))

; takes the input vector and swaps the value at index A with that at index B,
; mutably
(define (vector-swap! vec a-idx b-idx)
(define temp (vector-ref vec a-idx))
(vector-set! vec a-idx (vector-ref vec b-idx))
(vector-set! vec b-idx temp))

; like the above, but mutably with regards to the input
(define (vector-reorder! vec indices)
(define src-idx 0)

(for ([tar-idx (in-range (vector-length vec))])
(set! src-idx (vector-ref indices tar-idx))
(let loop ()
(when (< src-idx tar-idx)
(set! src-idx (vector-ref indices src-idx))
(vector-swap! vec src-idx tar-idx)))

and the second is notably faster for what I'm doing because copying is not performant

@hazel Looks like there’s an algorithm to apply a permutation to a vector in-place with constant memory:

Just follow each orbit of the permutation and shift the elements in the vector circularly. The tricky thing is to remember which orbits you have already followed (and when you have completed an orbit), but the solution in the stackoverflow answer is very pretty: just mess up the index array by negating the visited elements, then negate everything again in the end to restore it.


@hazel i mean,,, i would just sort it but im dummy and don't see a problem with O(n\log(n)) instead of O(n)

@hazel this sounds like a permutation operation? The thesis linked here may have more knowledge than you want?