Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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
*)
share|improve this answer
    
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]]]]
share|improve this answer
1  
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.

share|improve this answer
    
Thanks. More streamlined building of jvec is Delete[ Range@Length@ab, Transpose[{kvec}]] –  Sasha Feb 23 '12 at 17:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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