Looking for a way to insert multiple elements into multiple positions simultaneously in a list

Question

I would like to take the following data:

insertValues = {r, x};
insertPositions = {{1}, {5}};
originalList = {a, b, c, d, e, f, g};

and generate output that looks like this:

{r,a,b,c,d,x,e,f,g}

Mathematica's Insert command seems limited in that it does not allow you to insert multiple elements simultaneously into different positions in a list.

I wrote an ugly While[] loop to accomplish this, and it works, but seems inappropriate for Mathematica's functional approach to coding. Is there a "simpler" way to accomplish this goal with a functional approach? Thank you.

insertValues = {r, x};
insertPositions = {{1}, {5}};
originalList = {a, b, c, d, e, f, g};

loopCounter = 0; 
posCounter = 0; 
final = originalList;
While[loopCounter < Length[insertValues],
  final = 
   Insert[final, insertValues[[loopCounter + 1]], 
          (insertpositions[[loopCounter + 1]] + posCounter)]; 
  loopCounter++; 
  posCounter++
];

Answer 1

New developments

rasher posted a new answer with clean and well performing code that caused me to look again at this problem. (It well deserves your vote.) I see now that there are good ways to approach this problem that haven't yet been fully developed. Fundamentally rasher's code operates by Sort, but I don't think even he realized this as Riffle et al are superfluous. We merely need Ordering and Part applied to joined lists of the correct order:

oInsert[list_, val_, pos_] :=
  Join[val, list][[ Ordering @ Join[pos, Range @ Length @ list] ]]

In a way rasher solved the problem twice: Riffle and sa[[ps]] = reps already place the elements in the proper order; one merely needs to get rid of the zeros. We could use DeleteCases but pattern based methods are slow. Instead I reimplemented the Riffle operation in terms of SparseArray, but to make it efficient I had to be clever and unfortunately here that (so far) implies less clean code.

saInsert[list_, val_, pos_] :=
  With[{no = Length[list], ni = Length[val]},
    SparseArray[
      Automatic, {2, no + 1}, 0,
      {1, {{0, ni, no + ni}, pos ~Join~ Range[no] ~Partition~ 1}, val ~Join~ list}
    ]\[Transpose]["NonzeroValues"]
  ]

This ugly bit of code manually constructs a two row SparseArray, the upper row being the insertion elements and the lower being the original list. It then transposes them, and extracts the "NonzeroValues". (Despite the name these are actually the non-background values; this code still works correctly with zeros.)

Rudimentary test of both new methods:

oInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]

saInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]

{W, a, X, b, c, Y, d, e, Z}

{W, a, X, b, c, Y, d, e, Z}

I shall add timings for these functions later, but to summarize my early findings:

• multiInsert2 is still the fastest for a limited number of insertions into a long list
• saInsert is superior to all other methods posted so far for a greater number of insertions into a packed list
• oInsert is competitive with saInsert and rashernator on unpacked lists. It is faster than rashernator on packed lists.

---

Original Method

If your list is a vector (has no sub-lists) this is perhaps the simplest way, and likely competitively fast:

m = origlist;

m[[{1, 5}]] = {{r, x}, m[[{1, 5}]]}\[Transpose]

Flatten[m]

{r, a, b, c, d, x, e, f, g}

Edit: Ray Koopman points out that this method, by itself, does not handle an edge case in Insert where the position is one greater than the length of the list, i.e. Insert[{1,2,3}, x, 4]. This is accounted for in the function below by padding the list as required.

If your list is not a vector (as defined above) we could use a different head for the inserted elements and then replace it with Sequence to effect a flatten. Here is a function that handles both cases, selecting between the methods for best performance:

multiInsert[list_List, val_, pos_] /; Length@val == Length@pos :=
  Module[{m = list, f, pad},
    pad[x_] /; Max@pos == Length@list + 1 := AppendTo[m, x];
    If[VectorQ[val] && VectorQ[list],
      pad[{ }]; m[[pos]] = Transpose @ {val, m[[pos]]}; Flatten[m],
      pad[f[]]; m[[pos]] = MapThread[f, {val, m[[pos]]}]; m /. f -> Sequence
    ]
  ]

Input is a little different from yours:

multiInsert[Range@15, {a, b, c}, {3, 7, 13}]

{1, 2, a, 3, 4, 5, 6, b, 7, 8, 9, 10, 11, 12, c, 13, 14, 15}

Preallocate Method

Nasser proposed a method of preallocating the array. This idea was promising if it could be optimized because a packed array could be preserved throughout the process theoretically reducing memory and computation time. His implementation was limited in performance because it used a tag that necessitated unpacking and because searching for that tag using Position is slow. Here is an implementation that directly calculates the runs of original values rather than tagging and finding them afterward.

multiInsert2[list_, val_, pos_] /; Length@val == Length@pos :=
  Module[{new, start, end, offset, n1, n2},
    {n1, n2} = Length /@ {list, val};
    new    = ConstantArray[0, n1 + n2];
    start  = Prepend[pos, 1];
    end    = Append[pos - 1, n1];
    offset = Range[0, n2];
    MapThread[
      new[[# ;; #2]] = list[[#3 ;; #4]]; &,
      {offset + start, offset + end, start, end}
    ];
    new[[pos + Range[0, n2 - 1]]] = val;
    new
  ]

This function appear to be best for a moderate number of insertions into a long list. (See below)

Notes and timings

Ray Koopman posted a very elegant method, which on reflection I've seen before though I cannot remember where. I voted for that method but there is reason to use the longer forms that belisarius and I proposed: speed on long lists. Every Insert operation reallocates the array which takes time proportional to the length of the list. As such, a method using Fold will slow down considerably when doing many insertions into a very long list. I will call Ray Koopman's code foldInsert:

foldInsert[list_, val_, pos_] /; Length@val == Length@pos :=
 Fold[
  Insert[#1, #2[[2]], #2[[1]]] &,
  list,
  Reverse @ Sort @ Transpose @ {pos, val}
 ]

And using this timing code for the three functions multiInsert, multiInsert2, foldInsert:

timeAvg = 
  Function[func,
    Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}],
    HoldFirst];

time[n_Integer, k_Integer, rand_: RandomInteger] :=
 Module[{start, vals, pos},
  start = Range@n;
  vals = rand[9, k];
  pos = Sort @ RandomSample[start, k];
  timeAvg @ #[start, vals, pos] & /@ {multiInsert, multiInsert2, foldInsert}
]

With 3500 insertions into a length 5000 list:

time[5000, 3500]

{0.0017968, 0.007368, 0.01372}

With five insertions into a length 500,000 list:

time[500000, 5]

{0.02432, 0.0006736, 0.001448}

With 7500 insertions into the length 500,000 list:

time[500000, 7500]

{0.03244, 0.01812, 5.038}

All timings above were performing with integer into integer insertions. If inserting reals unpacking is necessary. Here are a few timings for that situation:

time[150000, 50, RandomReal]
time[150000, 500, RandomReal]
time[150000, 5000, RandomReal]

{0.01372, 0.005488, 0.0624}

{0.01308, 0.007368, 0.592}

{0.01684, 0.01748, 8.658}

Answer 2

Building on Kuba's answer: If you insert in reverse order then the positions don't need to be incremented.

Fold[Insert[#1,#2[[2]],#2[[1]]]&, origlist,  
     Reverse@Sort@Transpose@{insertpositions,insertvalues}]  

If a value is to be inserted in several positions then it must be appear in insertvalues once for each position. Elements of insertvalues may themselves be lists.

Answer 3

Probably also:

pInsert[origList_, repList_] := 
      Function[{l}, ReplacePart[
                      l, 
                      Thread[Rule[#[[1]], Sequence[#[[2]], l[[#[[1]]]]]] &/@ repList]]]@origList

pInsert[{a, b, c, d, e}, {{2, {x, y}}, {5, z}}]

{a, {x, y}, b, c, d, z, e}

Answer 4

If there are no multiple positions for each insertelement we can do something like:

i = 0;
Insert[origlist, "mark", insertpositions] /. "mark" :> (++i; insertvalues[[i]])

(*insertposition should be sorted*)

if, there are it can be exteded easily, by making duplicates in insertelements or to make different "marks" for them.

Answer 5

What a neat question and set of answers. Wish I'd been here when it was new, but here's my belated entry:

rashernator[list_, reps_, pos_] :=
     Module[{sa = Riffle[list, 0, {1, -1, 2}], ps = pos*2 - 1},
     sa[[ps]] = reps;
     sa[[Sort[Join[ps, Range[2, 2*Length@list, 2]]]]]]

About 20X faster than rest on large lists/larger replacement lists (e.g. on 50K list with 35K replacements, it's ~20X and ~50X as fast as the neat answers by Mr. Wizard, much more than that on the other answers I tested).

Seems to take over when the size of replacement list goes above 0.5 to 1%.

+1 to OP and answerers!

Answer 6

I have not looked at all the answers to see if one is similar to this. But this is the typical way to do these things in Matlab. This assumes the input is vector or one level list. It works by allocating vector of the size needed to contains everything.

Update

This is slight update. This version is a little faster than what I had before but still not as fast as Mr.Wizard's. Instead of using Position and marker, used Complement

ClearAll["Global`*"];
insertvalues = {r, x};
insertpositions = {1, 5};
origlist = {a, b, c, d, e, f, g};

  insertMultiNasser[to_List, from_List, pos_List] /; Length@from == Length@pos := 
   Module[{b, npos, o},
   b = Table[0, {Length[from] + Length[to]}];
   npos = pos + Range[0, Length[from] - 1];
   b[[npos]] = from;
   o = Complement[Range[Length[b]], npos];
   ReplacePart[b, Thread[o -> to]]
   ];

to call

insertMulti[origlist, insertvalues, insertpositions]

timings

MrWizard is at worst 10 times faster. So no cigar for me. Here are the timings (first number is above function, second number is MrWizard's multiInsert above.

time[50000, 35000]
{0.081121, 0.01148167}

time[5000, 350]
{0.00761285, 0.000349442}

time[500000, 3500]
{0.811205, 0.0355682}

time[50000, 45000]
{0.084241, 0.0137281}