27
$\begingroup$

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++
];
$\endgroup$
4
  • 3
    $\begingroup$ Please don't post simultaneously in several forums. Perhaps that will save you a few hours, but you should consider other people's time too $\endgroup$ Aug 18, 2013 at 4:27
  • 4
    $\begingroup$ @belisarius I see not reason to not post on many sites :) but only if there is information about this on both sites. $\endgroup$
    – Kuba
    Aug 18, 2013 at 8:50
  • 1
    $\begingroup$ I also see no reason why users shouldn't post on multiple forums. There is no guarantee the best answer will be found on one forum vs another. Nor is there a guarantee that the same users spend time on both forums. Nor is it required that someone spend time answering the same question multiple times on multiple sites. $\endgroup$
    – Todd Allen
    Aug 18, 2013 at 23:32
  • 8
    $\begingroup$ Adding information on cross-posting is considered polite and beneficial: meta.mathematica.stackexchange.com/a/368/131 (cc @belisarius) $\endgroup$
    – Yves Klett
    Aug 19, 2013 at 7:38

6 Answers 6

25
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ Thank you for your swift response. I don't understand the end code "[Transpose]". What does "\" stand for that I might look it up in the documentation? $\endgroup$
    – Todd Allen
    Aug 18, 2013 at 3:14
  • $\begingroup$ @Todd \[Transpose] is the long form of the transpose symbol entered with [Esc] tr [Esc]. $\endgroup$
    – Mr.Wizard
    Aug 18, 2013 at 3:20
  • $\begingroup$ multiInsert fails if Last@pos == Length@list+1, which both multiInsert2 and foldInsert handle as Insert would by effectively Appending Last@val to list. $\endgroup$ Aug 22, 2013 at 0:56
  • $\begingroup$ @Ray Thanks for the bug report; let me see if I can fix it cleanly. I must admit I never knew one could use that input with Insert. $\endgroup$
    – Mr.Wizard
    Aug 22, 2013 at 1:04
17
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ Oops, looks like I forgot to plan for an insert of a list into a vector. I'll fix that and then compare these methods. $\endgroup$
    – Mr.Wizard
    Aug 18, 2013 at 3:43
  • $\begingroup$ @Mr.Wizard I don't think this way is particularly fast or robust, but feel free to nuke it $\endgroup$ Aug 18, 2013 at 3:45
  • $\begingroup$ Nuke it? Not sure I understand. Anyway, your method appears to be faster than mine on long lists with few insertions (50,000 / 50) while mine is faster with many insertions. (+1) $\endgroup$
    – Mr.Wizard
    Aug 18, 2013 at 3:49
  • 1
    $\begingroup$ Another code equivalent to the above solution: pInsert=Function[{lst,rep},ReplacePart[lst,Apply[Function[{r1,r2},r1->Sequence[r2,lst[[r1]]]],rep,{1}]]]; $\endgroup$
    – M6299
    Aug 18, 2013 at 8:46
9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Your code works also with for example origlist = {1, {2, 3}, 4}; insertpositions = {{1}, {2, 3}}; insertvalues = {x, y}. It gives : {x, 1, {2, 3, y}, 4}).This is interesting. $\endgroup$
    – andre314
    Aug 18, 2013 at 7:54
  • $\begingroup$ @andre this case you've provided is exactly the same as OP's. two values -> two positions, and even though levels are not 1, Inser works with them. $\endgroup$
    – Kuba
    Aug 18, 2013 at 7:57
  • $\begingroup$ What is interesting is precisely that levels are 1 for x and 2 for y. This is not compatible with other answers. $\endgroup$
    – andre314
    Aug 18, 2013 at 8:01
  • $\begingroup$ @andre I'm not sure if I understand :) that's good, right? Fortunatelly OP has provided insertpositions in form accepted by Inser, thats because he was trying to use it. $\endgroup$
    – Kuba
    Aug 18, 2013 at 8:07
  • 1
    $\begingroup$ @Mr.Wizard I was thinking and thinking, what List/@ does... :) well it is redundant with OP's data. Very nice simplification. Thanks for the comment. $\endgroup$
    – Kuba
    Aug 19, 2013 at 21:44
7
$\begingroup$

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!

$\endgroup$
12
  • $\begingroup$ This is great! Very fast and much cleaner than my code. Don't I feel silly now! Initial tests show that my multiInsert2 is some 20X to 30X faster than yours in the case of a limited number of insertions into a long packed list, e.g. time[5*^6, 1*^3], so it does have a place, but yours appears to be faster in more cases. I shall study this further. Nice work! $\endgroup$
    – Mr.Wizard
    Apr 10, 2014 at 17:54
  • $\begingroup$ @Mr.Wizard: Thanks for kind words! Yep, as I noted, somewhere around the 1% density it takes over. The two methods combined make a wicked good utility function. $\endgroup$
    – ciao
    Apr 10, 2014 at 20:09
  • $\begingroup$ Please see my updated answer. Your code in a way solves the problem twice! $\endgroup$
    – Mr.Wizard
    Apr 10, 2014 at 20:31
  • $\begingroup$ @mr: lol, I did exactly that (well, almost exactly, as in the two-row sparse idea). It performed worse in my tests. Another interesting benchmark anomaly. Thanks for looking at it, tweaking it, etc. Glad you found it interesting! Edit- just tested yours - it is faster - the method you contruct array is better. Nice work, wish I could +1 you again... $\endgroup$
    – ciao
    Apr 10, 2014 at 20:38
  • 1
    $\begingroup$ @Mr.Wizard: re: saIinsert, see prior comment. oInsert actually seems slightly superior. And it's super-clean code to boot. I'll go poke at code and reply later with what I did with SA, but other reason I dropped it - can't (trivially) use it to insert non-scalar values. $\endgroup$
    – ciao
    Apr 10, 2014 at 20:53
2
$\begingroup$

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]

Mathematica graphics

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}
$\endgroup$
7
  • $\begingroup$ I don't understand the use of NaN here. Anyway, I await your timings. $\endgroup$
    – Mr.Wizard
    Aug 20, 2013 at 2:07
  • $\begingroup$ @Mr.Wizard, I needed a special symbol that will not occur in the original input. i.e. needed a special marker. In Matlab nan is used since for valid input, it should not contain a nan in it. If you suggest a different one I could use it, but this is how it is done in Matlab ;) the marker is any value that is not present in the insertvalues list. That is all. $\endgroup$
    – Nasser
    Aug 20, 2013 at 2:11
  • $\begingroup$ In that case I recommend using an additional symbol in the Module, e.g. mark. Also, you can simplify (and speed) your Position call with e.g. Position[bb, mark]. Oh, one more thing: ConstantArray will be much faster than Table. $\endgroup$
    – Mr.Wizard
    Aug 20, 2013 at 2:32
  • $\begingroup$ @Mr.Wizard good point. I was working in global context first and I did not think of it that when I move things to Module context, then any symbol there will go the job. WIll update now. Working on timings now also... $\endgroup$
    – Nasser
    Aug 20, 2013 at 2:34
  • $\begingroup$ I'm looking forward to this one. I think in certain circumstances it should be very good (once optimized). $\endgroup$
    – Mr.Wizard
    Aug 20, 2013 at 2:38

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.