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.


3 Answers 3


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

 ==> {0.437,Null}
  • $\begingroup$ 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. $\endgroup$ Commented Feb 23, 2012 at 17:14
  • $\begingroup$ I tried a version of this too, but for some reason it was hopelessly slow. Thanks for the solution! $\endgroup$
    – Sasha
    Commented Feb 23, 2012 at 17:21
  • $\begingroup$ @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. $\endgroup$ Commented Feb 23, 2012 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]]]]
  • 1
    $\begingroup$ Very nice. This is what I was thinking about when writing the second comment to my post. +1. $\endgroup$ Commented Mar 7, 2012 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]];

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

  • $\begingroup$ Thanks. More streamlined building of jvec is Delete[ Range@Length@ab, Transpose[{kvec}]] $\endgroup$
    – Sasha
    Commented Feb 23, 2012 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.