Efficient way to turn a subset into a permutation

Question

For an input vector $\{a_1,a_2,\ldots,a_n,b_{1},b_2,\ldots,b_{m}\}$ and a list of ordered positions $\{k_1,k_2,\ldots, k_n\}$, such that $1\leqslant k_1 < k_2 < \ldots < k_n \leqslant n+m$, I would like to output a vector where each $a_i$ are located at $k_i$-th position, and for every $1 \leqslant s<t \leqslant m$, $b_s$ precedes $b_{t}$ in the resulting list.

My implementation of this is based on the observation that $\{k_1,\ldots,k_n\} \cup \{k_1,\ldots,k_n\}^c$ is the inverse of the needed permutation, where complement is understood in the set of natural numbers from 1 to $n+m$.

Reshuffle[ab_, kvec_] := ab[[Ordering[Join[kvec, Complement[Range@Length[ab], kvec]]]]]   
Reshuffle[{a1, a2, b1, b2, b3}, {2, 4}]    
(* Out= {b1, a1, b2, a2, b3} *)

I am somewhat dissatisfied with this solution, as it has sub-optimal complexity. I am hoping there is a direct way to construct the permutation to transform input ab into the result, that does not use Ordering or Complement. Thanks for reading.

Answer 1

Theoretically, this will have linear complexity:

reshuffle[ab_, kvec_] :=
  Module[{a, copy , bs = Drop[ab, Length[kvec]], n = 0},
    copy = Table[a, {Length[ab]}];
    copy[[kvec]] = Take[ab, Length[kvec]];
    copy /. a :> bs[[++n]]]

In practice, however, I am pretty sure your solution is one of the fastest. A version of my solution can be compiled if your list is e.g. a list of integers or reals, in which case it may be faster.

Here is a compiled version:

reshuffleC =
  Compile[{{ab, _Integer, 1}, {kvec, _Integer, 1}},
     Module[{result, min = Min[ab], i = 1, ctr = 0, bs = Drop[ab, Length[kvec]]},
       result = Table[min - 1, {Length[ab]}];
       result[[kvec]] = Take[ab, Length[kvec]];
       For[i = 1, i <= Length[ab], i++,
         If[result[[i]] == min - 1,
         result[[i]] = bs[[++ctr]]]];
       result], CompilationTarget -> "C"]

If you have a general list as ab, you can use ab[[reshuffleC[Range[Length[ab]],kvec]]].

Here are some benchmarks:

abtest = RandomInteger[{10000000},10000000];
kvec = RandomSample[Range[10000000],5000000];
(res1=reshuffleC[abtest ,kvec]);//Timing
(res2=Reshuffle[abtest ,kvec]);//Timing
res1==res2

(* 
 ==> {0.437,Null}
     {2.797,Null}
      True
*)

Answer 2

Since kvec is ordered we can just make a table.

reshuffle2[ab_, kvec_] := Module[{k = 1, j = Length[kvec] + 1},
  Table[If[k > Length[kvec] || i < kvec[[k]], ab[[j++]], 
    ab[[k++]]], {i, Length[ab]}]]

To improve speed we might compile something similar that just finds positions.

findOrderingC = Compile[{{kvec, _Integer, 1}, {len, _Integer, 0}},
   Module[{k = 1, j = Length[kvec] + 1},
    Table[If[k > Length[kvec] || i < kvec[[k]], j++, k++], {i, len}]
    ], CompilationTarget -> "C"];

reshuffle3[ab_, kvec_] := ab[[findOrderingC[kvec, Length[ab]]]]

Answer 3

This is a somewhat naive procedural implementation:

reshuffle[ab_, kvec_] := 
 Module[{result, jvec},
  jvec = Range@Length[ab];
  jvec[[kvec]] = Null;
  jvec = DeleteCases[jvec, Null];
  result = ConstantArray[Null, Length[ab]];
  result[[kvec]] = Take[ab, Length[kvec]];
  result[[jvec]] = Drop[ab, Length[kvec]];
  result
 ]

jvec just holds the indices of the $b$s. This should have linear complexity.