在mathematica中使用map/select查找列表中的子列表

Question

在Wolfram Mathematica 8.0中,我有一个嵌套列表

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

和像这样的普通列表

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

我想检查nList中的所有子列表是否都在lList中(在示例中a,b和n,o是否存在但不是f,g)

我已经使用For[,,,]和使用索引完成了...有人可以启发我使用Map/Thread/Select等函数来一次完成它.

编辑:如果nList包含a,b,lList必须包含a,b和不包含a,c,b或b,a或b,c,a

Answer 1

假设您不关心元素排序,这里有一种方法:

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

Out[20]= False

编辑

如果订单很重要,那么这是一种方式:

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

Out[29]= False

对于大量子列表,这可能更快:

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

Out[34]= False

其工作方式如下:ReplaceList是一个非常好但经常被忽略的命令,它返回所有可能表达式的列表,这些表达式可以通过模式匹配器尝试以一切可能的方式将规则应用于表达式来获得.这与模式匹配器通常的工作方式形成对比,它在第一次成功匹配时停止.所述PatternSequence 是一个相对较新除了Mathematica的模式语言,这使我们能够得到一个身份表达的给定序列,将它视为一个图案.这允许我们构造替代模式,因此得到的模式是:主要列表中任何位置的任何子列表的序列被收集并放回到列表括号中,形成子列表.我们得到尽可能多的新形成的子列表,因为在较大的列表中存在原始子列表的序列.如果存在所有子列表,则Union结果列表应Union与原始子列表列表相同.

以下是基准测试(我获取了一个整数列表,以及由此生成的重叠子列表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}

从概念上讲,第二种方法更快的原因是它在单个运行列表中执行其工作(由内部执行ReplaceList),而第一个解决方案显式遍历每个子列表的大列表.

编辑2 - 表现

如果性能确实是一个问题,那么下面的代码要快得多:

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

例如,在我们的基准测试中:

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

Out[54]= {0.,True}

编辑3

根据@ Mr.Wizard的建议,可以进行以下性能改进:

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

在这里,只要我们从给定长度的子列表中得到否定答案,就不会检查其他长度的子列表,因为我们已经知道答案是否定的(False).如果Scan没有完成Return,它将返回Null,这意味着lList包含所有子列表nList.

Answer 2

你可以使用模式匹配来完成这项工作:

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

这@@@是Apply级别的别名{1}.级别1 nList包含您的对,并且应用用List右侧的函数替换它们中的头部@@@.

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

Out[71]= {True, False, True}