arrays - 在数组内移动数组元素

Question

像这样将元素移动到数组内的新索引的有效方法是什么？

A = collect(1:9)  # [1,2,3,4,5,6,7,8,9]

# now lets move elements 1:3 to index 2 
move!(A,1:3,2)    # [4,1,2,3,5,6,7,8,9]

# lets move the 9 to index 3 now
move!(A,9:9,3)    # [4,1,9,2,3,5,6,7,8]

# or this
move!(A,3:6,5)    # [4,1,6,7,9,2,3,5,8]

我总是最终调整数组的大小或像疯了一样交换。有没有一种有效(=快速)的方法来解决这个问题？

Answer 1

将数组中的一系列元素移动到新位置可以视为旋转更大的范围，其中包括一条边上的移动元素和目标位置。旋转刚好足以使移动的元素定位并将其他元素推开。

由于向量的长度保持不变，最好在没有分配的情况下就地执行此操作。就地进行这种旋转有点棘手，但可行，如下面的代码所示:

function rotate!(v,n::Int)
  l = length(v)
  l>1 || return v
  n = n % l
  n = n < 0 ? n+l : n
  n==0 && return v
  for i=1:gcd(n,l)
    tmp = v[i]
    dst = i
    src = dst+n
    while src != i
      v[dst] = v[src]
      dst = src
      src += n
      if src > l
        src -= l
      end
    end
    v[dst] = tmp
  end
  return v
end

move!(A,rng,loc) = begin 
  rotate!(view(A,min(first(rng),loc):max(last(rng),length(rng)+loc-1)),first(rng)-loc)
  return A
end

A = collect(1:9)
@show move!(A,1:3,2) == [4,1,2,3,5,6,7,8,9]
@show move!(A,9:9,3) == [4,1,9,2,3,5,6,7,8]
@show move!(A,3:6,5) == [4,1,6,7,9,2,3,5,8]

最后几行代码复制了问题中的示例。本质上，只有 view分配内存和 rotate!功能完全到位。