Re: A SubListQ function?

*To*: mathgroup at smc.vnet.net*Subject*: [mg28549] Re: [mg28546] A SubListQ function?*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Fri, 27 Apr 2001 03:56:04 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Of the three examples you give, the first is correct and in my opinion very efficient (perhaps unbeatable), the second is wrong, and the third very inefficient. You can easily see that the second one is wrong, e.g.: In[1]:= ContainedQ[a_, b_] := Intersection[a, b] === a In[2]:= ContainedQ[{2, 1}, {1, 2, 3}] Out[2]= False Of course you need to Sort a on the right hand side, which will slow down your code. Still, even with Sort on the right hand side this beats your last example by a big margin. As I said, the complement approach seems to me very efficient and I will be very surprised if any one can beat it. Even the second method will be hard to beat. Here are some test results in which I include also one attempt I have tried (the only one). (My attempt assumes that your lists do not contain Boolean values False and True as elements! If this was really a problem one could easily deal with it but it seems to me so unlikely I shan't bother). In[1]:= ContainedQ[1][a_List, b_List] := Complement[a, b] === {} In[2]:= ContainedQ[2][a_, b_] := Intersection[a, b] === Sort[a] In[3]:= ContainedQ[3][a_List, b_List] := Or @@ (a /. Dispatch[Thread[Rule[b, False]]]) === False In[4]:= ContainedQ[4][a_, b_] := And @@ (MemberQ[b, #] & /@ a) My ContainedQ[3] fails well short of the first two in the case when a is a sublist of b: In[5]:= b = Table[Random[], {5000}]; In[6]:= a = Take[b, {2000, 4000}]; In[7]:= (ContainedQ[#][a, b] // Timing) & /@ Range[4] Out[7]= {{0.0166667 Second, True}, {0.0333333 Second, True}, {0.183333 Second, True}, {28.5 Second, True}} However when a is not a sublist of b ContainedQ[3] seems to catch with the ContainedQ[2] and is just slightly behind ContainedQ[1], for this range of values anyway (and on my old 266 mghz Mac!): a = Append[a, dog]; In[9]:= (ContainedQ[#][a, b] // Timing) & /@ Range[4] Out[9]= {{0.133333 Second, False}, {0.166667 Second, False}, {0.166667 Second, False}, {28.9333 Second, False}} -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/ on 01.4.26 8:21 AM, AGUIRRE ESTIBALEZ Julian at mtpagesj at lg.ehu.es wrote: > Given two lists a and b, how can I find if a is contained in b? I have > tried > > Complement[a, b] == {} > > Intersection[a, b] == a > > And@@(MemberQ[#,b]&/@a) > > They work, but are not very efficient. Is there a better way? > > Thanks in advance, > > Julian Aguirre > Universidad del Pais Vasco > > >