# Finding members of the list that share a common element

Let's say I have a list:

{{1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}}

and I want to find all the members of that list that share a common element. So, for instance, if I say that this element is 1, I would get a list {{1},{1,2},{1,2,3},{1,2,3,4}}. I played around with Cases and Intersection but couldn't figure it out. I'd appreciate some hints. Thanks.

• Use MemberQ to check if a element is part of a list. Combine this with Select, Cases etc – void life Jan 10 '19 at 16:16

l = {{1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}};
sel[list_, element_] := Select[list, MemberQ[#, element] &];
sel[l, 1]


produces the output

{{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}}

Let's assemble a SparseArray whose entry A[[i,j]] is 1 precisely if i is a member of the jth sublist (and 0 otherwise).

a = {{1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}};
A = SparseArray[
Join @@ MapIndexed[{y, x} \[Function] Thread[{y[], x}], a] -> 1,
{Max[a], Length[a]}
];


Then you obtain the indices of the sublists that contain the entry i by A[[i]]["AdjacencyLists"], e.g.

i = 1;


{1, 5, 8, 10}

The actual sublist have to be look up from the original list of lists:

a[[idx]]


{{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}}

The nice thing about the SparseArray A is that it can be reused for multiple lookups. Actually,

returns already the sublist indices for all entries. Moreover, the SparseArray data structure is highly optimized for such lookups. You will hardly be able to make it faster in Mathematica