logo标签列表

在Python中，从列表中删除子集的最快方法是什么？

pythonpython-2.7subsetpython-itertools
3
假设我有一个像下面这样的列表（实际列表要长得多）：
fruits = [['apple', 'pear'],
          ['apple', 'pear', 'banana'],
          ['banana', 'pear'],
          ['pear', 'pineapple'],
          ['apple', 'pear', 'banana', 'watermelon']]

在这种情况下，列表['banana'，'pear']，['apple'，'pear']和['apple'，'pear'，'banana']中的所有项目都包含在列表['apple'，'pear'，'banana'，'watermelon']中（项目的顺序无关紧要），因此我想删除['banana'，'pear']，['apple'，'pear']和['apple'，'pear'，'banana']，因为它们是['apple'，'pear'，'banana'，'watermelon']的子集。
我的当前解决方案如下所示。我首先使用ifilter和imap创建一个生成器，以便为每个列表创建可能具有的超集。然后对于那些确实有超集的情况，我使用compress和imap将它们删除。
from itertools import imap, ifilter, compress

supersets = imap(lambda a: list(ifilter(lambda x: len(a) < len(x) and set(a).issubset(x), fruits)), fruits)


new_list = list(compress(fruits, imap(lambda x: 0 if x else 1, supersets)))
new_list
#[['pear', 'pineapple'], ['apple', 'pear', 'banana', 'watermelon']]

我在想有没有更高效的方法来做这件事情？

1
可能是重复的问题：Python - 验证一个列表是否为另一个列表的子集。 - Brent Washburne
1
你可以通过使用生成器表达式/列表推导式来替换imap和ifilter。它们的工作方式相同，但能产生更易读的代码... - JBernardo
@JBernardo：你能给个例子吗？谢谢！ :) - Alex
所有的子列表都保证是集合本身，还是可能存在 [['pear', 'pineapple', 'pear'], ['pineapple', 'pear']] 这样的情况？ - Kyle Pittman
@dawg 对我来说没问题。有一个额外的 from itertools 悬在那里，但那是我改变的唯一的东西。编辑：好吧，在编辑之前确实有这个问题。;) - Kyle Pittman
显示剩余2条评论
3个回答
7
filter(lambda f: not any(set(f) < set(g) for g in fruits), fruits)
当我尝试运行你的代码时，输出结果为[['apple', 'pear'], [['apple', 'pear', 'banana'], ['banana', 'pear'], ['pear', 'pineapple'], ['apple', 'pear', 'banana', 'watermelon']]]。 - Alex
我的代码有一个错误。我认为当前版本应该可以工作。 - lukaszzenko
无论你怎么做，它对我都起作用 - 而且无论如何，这都是一个非常Pythonic的答案。这让我很开心。 - Kyle Pittman
奇怪。在 Canopy 编辑器界面中，我一直得到一个空列表。但是当我在命令行界面中尝试时，我得到了正确的结果！谢谢 - Alex
4

我不知道是否更快，但对我来说这种方式更易于阅读：

sets={frozenset(e) for e in fruits}  
us=set()
while sets:
    e=sets.pop()
    if any(e.issubset(s) for s in sets) or any(e.issubset(s) for s in us):
        continue
    else:
        us.add(e)

更新

这很快。更快的方法是使用一个 for 循环。查看时间：

fruits = [['apple', 'pear'],
        ['apple', 'pear', 'banana'],
        ['banana', 'pear'],
        ['pear', 'pineapple'],
        ['apple', 'pear', 'banana', 'watermelon']]

from itertools import imap, ifilter, compress    

def f1():              
    sets={frozenset(e) for e in fruits}  
    us=[]
    while sets:
        e=sets.pop()
        if any(e.issubset(s) for s in sets) or any(e.issubset(s) for s in us):
            continue
        else:
            us.append(list(e))   
    return us           

def f2():
    supersets = imap(lambda a: list(ifilter(lambda x: len(a) < len(x) and set(a).issubset(x), fruits)), fruits)
    new_list = list(compress(fruits, imap(lambda x: 0 if x else 1, supersets)))
    return new_list

def f3():
    return filter(lambda f: not any(set(f) < set(g) for g in fruits), fruits)

def f4():              
    sets={frozenset(e) for e in fruits}  
    us=[]
    for e in sets:
        if any(e < s for s in sets):
            continue
        else:
            us.append(list(e))   
    return us              

if __name__=='__main__':
    import timeit     
    for f in (f1, f2, f3, f4):
        print f.__name__, timeit.timeit("f()", setup="from __main__ import f, fruits"), f()

在我的机器上使用Python 2.7：

f1 8.09958791733 [['watermelon', 'pear', 'apple', 'banana'], ['pear', 'pineapple']]
f2 15.5085151196 [['pear', 'pineapple'], ['apple', 'pear', 'banana', 'watermelon']]
f3 11.9473619461 [['pear', 'pineapple'], ['apple', 'pear', 'banana', 'watermelon']]
f4 5.87942910194 [['watermelon', 'pear', 'apple', 'banana'], ['pear', 'pineapple']]
我尝试了 f1()，结果得到了 set()。 - Alex
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接