list - 在 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 中的所有子列表.