问题 检查元素是否在所有列表中一起出现?


假设我有一个列表,如下所示:

l = [[1,2,3],[6,5,4,3,7,2],[4,3,2,9],[6,7],[5,1,0],[6,3,2,7]]

我如何编写python代码来检查是否有总是一起出现的元素?例如,在上面的例子中,2,3和6,7总是出现在相同的列表中。 (可能还有其他人,不确定)。

实现这一目标的最简单方法是什么?

我唯一的想法是转换 inner-list1 设置和检查交集 inner-list2 但是当我检查交叉路口时 inner-list3,这些元素可能根本不会发生 inner-list3

我可以这样做:

for i in range(0,len(lists)):    
    a=set(lists[i]).intersection(lists[i+1])
    if (len(a))==0:
        continue
    else:
        a.intersection(lists[i+1])

这当然不起作用,但我怎么能正式编码这个或者有更好的方法吗?


12416
now


起源

对于2组合,这很容易,但是如果你看看是否有问题就更难了 3 总是与...一起出现 1 和 2。 - Willem Van Onsem
是的 elements 的 lists 总是 integers 从 1-9? - Joe Iddon
是的,总是从1到9和2或更多的整数可能会像@WillemVanOnsem一样出现。虽然理想情况下我想要一个适用于任何整数的解决方案,而不仅仅是1到9。 - doddy


答案:


运用 itertools.combinations

我最初想过用的东西 itertools.combination但正如这允许的那样 elements 从一个 list 它们不是彼此相邻的,它不适用于我想到的解决方案。

事实证明,当看非数字输入时 listsitertools.combinations   两种情况都是必要的。我很困惑,因为我认为了 groups 必须是 adjacent

我认为最适合这种方式的方法是产生可能的方法 elements 那 可以 工作,然后检查每一个 function 反对这 list 的 sub-lists  - 而不是做某种组合工作 list 沿着那条路走下去。

所以要检查一下 list 可能的 elements 是'有效',即如果全部 elements 只发生在一起,我用的很简单 if 用发电机 all() 和 any() 内建的 functions 做这部分工作。

现在这是有效的,需要有一种产生潜力的方法 elements 可能会发生。我刚刚用两个嵌套做了这个 for-loops  - 一个 iterating 过了 width 的 window和一个 iterating 在哪里 start 的 window 是。

然后从这里,我们只检查那组 elements 是 valid 并将其添加到另一个 list 如果是!


import itertools

def valid(p):
    for s in l:
        if any(e in s for e in p) and not all(e in s for e in p):
            return False
    return True

l = [[1,2,3],[6,5,4,3,7,2],[4,3,2,9],[6,7],[5,1,0],[6,3,2,7]]
els = list(set(b for a in l for b in a))
sol = []
for w in range(2,len(els)+1):
    for c in itertools.combinations(els, w):
        if valid(c):
            sol.append(c)

这使 sol 如:

[(2, 3), (6, 7)]]

这些 2  nested for-loops 实际上可以被扔到一起很好 one-liner (不确定其他人是否认为它是Pythonic):

sol = [c for w in range(2, len(els)+1) for c in itertools.combinations(els, w) if valid(c)]

它的工作原理相同但只是更短。


由于受欢迎的需求(@Arman),我已经更新了答案,现在它应该适用于其他人 elements 除了 0-9。这是通过引入一个独特的 elements  list (els)。


还有一些测试来自 @thanasisp 使用上面相同的代码:

l = [[1, 3, 5, 7],[1, 3, 5, 7]]

sol 如:

[(1, 3), (1, 5), (1, 7), (3, 5), (3, 7), (5, 7), (1, 3, 5), (1, 3, 7), (1, 5, 7), (3, 5, 7), (1, 3, 5, 7)]

并再次:

 l = [[1, 2, 3, 5, 7], [1, 3, 5, 7]]

得到:

 [(1, 3), (1, 5), (1, 7), (3, 5), (3, 7), (5, 7), (1, 3, 5), (1, 3, 7), (1, 5, 7), (3, 5, 7), (1, 3, 5, 7)]

我相信这是正确的 2  不能 像其他所有人一样在任何群体中 elements 是一个不同的 sub-list,所以它永远不能与另一个组成一个团体 element


5
2017-11-11 17:34



如果整数大于9,这怎么会不起作用。 - ᴀʀᴍᴀɴ
@Arman是的,但是我确定在写完答案之前先询问OP,如果那样的话很好...... - Joe Iddon
虽然理想情况下我想要一个适用于任何整数的解决方案,而不仅仅是1到9 OP说。 - ᴀʀᴍᴀɴ
@Arman True但是,它仍然回答了这个问题 - Joe Iddon
@Arman我会看看我是否可以改进我的解决方案,因此逻辑保持不变,但不限于此 1-9... - Joe Iddon


另一个具有默认dicts的线性解决方案(元组可用于制作可用密钥):

from collections import defaultdict
isin,contains = defaultdict(list),defaultdict(list)

for i,s in enumerate(l):
    for k in s : 
        isin[k].append(i)

# isin is  {1: [0, 4], 2: [0, 1, 2, 5], 3: [0, 1, 2, 5], 6: [1, 3, 5],
# 5: [1, 4], 4: [1, 2], 7: [1, 3, 5], 9: [2], 0: [4]}
# element 1 is in sets numbered 0 and 4, and so on.

for k,ss in isin.items(): 
    contains[tuple(ss)].append(k)

# contains is  {(0, 4): [1], (0, 1, 2, 5): [2, 3], (1, 3, 5): [6, 7],
# (1, 4): [5], (1, 2): [4], (2,): [9], (4,): [0]})
# sets 0 and 4  contains 1, and no other contain 1. 

现在,如果您查找按组显示的元素 n  (n=2 在这里),键入:

print ([p for p in contains.values() if len(p)==n])    
# [[2, 3], [6, 7]]

3
2017-11-11 18:26