Searching for subscriptions in lists with display / selection in math

Question

Wolfram Mathematica 8.0 has a nested list, e.g.

nList = {{a,b},{f,g},{n,o}}

and a regular list, for example

lList = {a,b,c,k,m,n,o,z}

and I want to check if all signatures are in nList in lList (in examples a, b and n, o is, but not f, g)

I did this with For[,,,] and using the index ... can someone enlighten me on using features like Map / Thread / Select to do this in one go.

Edit: if nList contains a,b , lList should contain a,b , not a,c,b or b,a or b,c,a

Answer 1

Assuming you don't need to arrange the elements, here is one way:

 In[20]:= Complement[Flatten[nList],lList] ==={} Out[20]= False 

EDIT

If order matters, then this is one way:

 In[29]:= And@ @(MatchQ[lList,{___,PatternSequence[##],___}]&@@@nList) Out[29]= False 

For a large number of subscriptions, this can be faster:

 In[34]:= Union[ReplaceList[lList, {___,x: Alternatives@ @( PatternSequence@ @@nList),___}:>{x}]]===Union[nList] Out[34]= False 

This works as follows: ReplaceList is a very good, but often ignored command that returns a list of all possible expressions that can be obtained using a template that tries to apply the rules in every possible way to the expression. This contrasts with the way the pickup template usually works, where it stops at the first successful match. PatternSequence is a relatively new addition to the Mathematica template language, which allows us to give an identity to a given sequence of expressions, considering it as a pattern. This allowed us to build an alternative template, so the resulting template says: the sequence of any sublist anywhere in the main list is collected and returned back to the brackets of the list, forming the sublist back. We get as many newly formed subscriptions as possible, as there are sequences of source sublists in a larger list. If all sublists are present, then Union in the resulting list should be the same as Union original list of sublists.

Here are the tests (I took a list of integers and overlapping signatures created by Partition ):

 In[39]:= tst = Range[1000]; In[41]:= sub = Partition[tst, 2, 1]; In[43]:= And @@ (MatchQ[tst, {___, PatternSequence[##], ___}] & @@@ sub) // Timing Out[43]= {3.094, True} In[45]:= Union[ReplaceList[tst, {___,x : Alternatives @@ (PatternSequence @@@ sub), ___} :> {x}]] === Union[sub] // Timing Out[45]= {0.11, True} 

It’s clear that the reason the second method works faster is because it does its work in a single run through the list (internally using the ReplaceList ), while the first solution explicitly iterates through the large list for each subscription.

EDIT 2 - Performance

If performance is really a problem, the following code is even faster:

 And @@ (With[{part = Partition[lList, Length[#[[1]]], 1]}, Complement[#, part] === {}] & /@SplitBy[SortBy[nList, Length], Length]) 

For example, in our tests:

 In[54]:= And@ @(With[{part = Partition[tst,Length[#[[1]]],1]}, Complement[#,part]==={}]&/@SplitBy[SortBy[sub,Length],Length])//Timing Out[54]= {0.,True} 

EDIT 3

At the suggestion of @ Mr.Wizard, the following performance improvement can be made:

 Scan[ If[With[{part = Partition[lList, Length[#[[1]]], 1]}, Complement[#, part] =!= {}], Return[False]] &, SplitBy[SortBy[nList, Length], Length] ] === Null 

Here, as soon as we get a negative answer from subscriptions for a given length, sublists of other lengths will not be checked, since we already know that the answer is negative ( False ). If Scan completes without Return , it will return Null , which means that lList contains all the signatures in nList .

Answer 2

You can use pattern matching to accomplish this task:

 In[69]:= nList = {{a, b}, {f, g}, {n, o}}; lList = {a, b, c, k, m, n, o, z}; 

@@@ is an alias for Apply at the {1} level. Level 1 nList contains your pairs, and the application replaces the List head in them with the function to the right of @@@ .

 In[71]:= MatchQ[lList, {___, ##, ___}] & @@@ nList Out[71]= {True, False, True}