# Efficient way to turn a subset into a permutation

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.

-

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
*)

-
Actually, you can get about 30% speed increase by setting RuntimeOptions->"Speed", in which case, for the size of the lists as in benchmarks above, the compiled solution is order of magnitude faster than your version. –  Leonid Shifrin Feb 23 '12 at 17:14
I tried a version of this too, but for some reason it was hopelessly slow. Thanks for the solution! –  Sasha Feb 23 '12 at 17:21
@Sasha Glad I could help, thanks for the accept. Actually, I think a more reusable component for this would be a function which takes a length and a list of positions, and constructs the complementary list of positions. Can be done along the same lines but simpler. –  Leonid Shifrin Feb 23 '12 at 18:09

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]]]]

-
Very nice. This is what I was thinking about when writing the second comment to my post. +1. –  Leonid Shifrin Mar 7 '12 at 18:10

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.

-
Thanks. More streamlined building of jvec is Delete[ Range@Length@ab, Transpose[{kvec}]] –  Sasha Feb 23 '12 at 17:18
Here is a functional approach which should do the same. Basically it creates the list of all the a with its destination positions and inserts it one after another into the b list using Fold
Reshuffle[ab_List, kvec_List] :=

But the repeated Insert will make this have an $O(m n)$ complexity (due to all the reallocations Insert might do). –  Szabolcs Feb 23 '12 at 17:48