Re: newbie list question

*To*: mathgroup at smc.vnet.net*Subject*: [mg115045] Re: newbie list question*From*: Ray Koopman <koopman at sfu.ca>*Date*: Wed, 29 Dec 2010 05:58:20 -0500 (EST)

At 7:51 am on Dec 28, 2010, Daniel Lichtblau <danl at wolfram.com> wrote > ----- Original Message ----- >> From: "Gareth Edwards" <gareth.edwards at cubicmotion.com> >> To: mathgroup at smc.vnet.net >> Sent: Sunday, December 26, 2010 3:02:23 AM >> Subject: newbie list question >> Hi, >> >> Liking Mathematica a lot, but struggling with the early part of the >> learning curve, i.e. don't know what I don't know... >> >> What would be the neatest syntax for finding the first location of >> elements from one list in another? For example: >> >> listA = { 4,5,8,2,6,4 } >> listB = { 8,4,2 } >> >> I would like a function to return {3,1,4} in this case (the first >> location in A of each element in B) >> >> Many thanks! > > Neatest is subject to debate. A straightforward and simple method > is to Map Position (of element in first list) over the second list. > > firstPositions1[l1_, l2_] := Flatten[Map[Position[l1, #, 1, 1] &, > l2]] > > This will be fine provided the second list is not too large; it > scales as m1*m2 where mj is the length of list j. A method that is > slower per element of list2, but scales as O(m1+m2), is shown below. > > firstPositions2[l1_, l2_] := Module[ > {stor, elem, tab}, > tab = ConstantArray[0, Length[l2]]; > MapIndexed[If[! IntegerQ[stor[#1]], stor[#1] = #2[[1]]] &, l2]; > Do[ > elem = stor[l1[[j]]]; > If[IntegerQ[elem], > stor[l1[[j]]] = False; > tab[[elem]] = j; > ], {j, Length[l1]}]; > tab] > > Quick test that these work. > > listA = {4, 5, 8, 2, 6, 4}; > listB = {8, 4, 2}; > > In[85]:= firstPositions1[listA, listB] == > firstPositions2[listA, listB] == > IntegerDigits[IntegerPart[100*Pi]] > > Out[85]= True > > If the second list has 10 or so elements, the second method is > noticeably slower than the first. But it does in fact scale much > better. Here we compare speed when second list is 1000 elements > (not necessarily unique). > > l1 = RandomInteger[10^6, 5*10^5]; > l2 = RandomInteger[10^6, 10^3]; > > In[73]:= Timing[pos1 = firstPositions1[l1, l2];] > Out[73]= {68.11000000000001, Null} > > In[74]:= Timing[pos2 = firstPositions2[l1, l2];] > Out[74]= {1.933999999999969, Null} > > Notice there is a difference in behavior beyond speed. If the second > list contains values not found in the first, the second result will > have zeros in those corresponding slots. I'm guessing this is > probably desirable behavior, as compared to omitting them altogether > (since you won't otherwise know what element in result corresponds > to what element in second list). > > In[75]:= pos1 == DeleteCases[pos2, 0] > Out[75]= True > > In[76]:= Length[pos1] > Out[76]= 379 > > Daniel Lichtblau > Wolfram Research firstPositions2 ignores repeats in the second list: firstPositions1[listA, Join[listB,listB] ] firstPositions2[listA, Join[listB,listB] ] {3,1,4,3,1,4} {3,1,4,0,0,0} Swapping the roles of the lists seems to fix the problem: firstPositions3[L1_, L2_] := Module[{p}, MapIndexed[If[ !IntegerQ@p@#1, p@#1 = #2[[1]] ]&, L1]; Map[If[ IntegerQ@p@#, p@#, 0 ]&, L2]] firstPositions3[listA, listB] firstPositions3[listA, Join[listB,listB] ] {3,1,4} {3,1,4,3,1,4}