How to find all elements in B that contain any element of A, where A and B are lists of combinations-CodePudding

Suppose A = [[0, 1], [1, 2]], which stores two 2-combinations from {0, 1, 2, 3}, and B = [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], which stores all possible 3-combinations from {0, 1, 2, 3}.

How to find all elements in B that contain at least one of the 2-combinations from A?

My desired output is C = [[0, 1, 2], [0, 1, 3], [1, 2, 3]], where [0, 1, 2] includes both [0, 1] and [1, 2], [0, 1, 3] includes [0, 1], and [1, 2, 3] includes [1, 2].

Thanks! (It would be great if the answer code is efficient and fast, as I need to do this for A and B that are of large scale)

I tried the following codes:

import numpy as np
import itertools

A = [[0, 1], [1, 2]]
B = []
Cdup = []
rows = range(4)
for combo in itertools.combinations(rows, 3):
    B.append(list(combo))

print(B)

for b in B:
    for a in A:
        if a.issubset(b):
            Cdup.append(b)

C = np.unique(Cdup)

But there is an error that says list object has no attribute issubset.

CodePudding user response：

You could scan each element b of listB and check if any element a of listA is a subset of b, in that case keep b.

Coding:

[b for b in listB if any(set(a).issubset(set(b)) for a in listA)]

CodePudding user response：

Here is a solution using itertools.combinations, comprehensions, and set:

from itertools import combinations

A = [(0, 1), (1, 2)]
B = list(combinations(range(4), 3))
C = set(b for a in A for b in B if a in set(combinations(b, len(a))))

print(C)

Which results in:

{(0, 1, 2), (0, 1, 3), (1, 2, 3)}

The solution above assumes that len(a) <= len(b) where a and b are elements of A and B, respectively. What it does is simply check if each element of A is an element of the combinations of each element of B, combined by the len() of elements of A.

CodePudding user response：

Hope this code can be a solution for your scenario, let me know if you think it needs any explanations:

listA=[[0,1],[1,2]]
listB=[[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
res = []

for comA in listA:

    strA = " ".join(str(e) for e in comA)

    for comB in listB:
    
        strB = " ".join(str(el) for el in comB)
    
        if strA in strB:
        
            res.append(list(comB))
            # use tuple if you want to remove duplicates easily:
            # res.append(tuple(comB))


print(res)

# if the res list contain tuples the to remove duplicates we can use:
# mylist = list(dict.fromkeys(res))
# print(mylist)