0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Use MemberQ to check if a element is part of a list. Combine this with Select, Cases etc $\endgroup$ – void life Jan 10 '19 at 16:16
0
$\begingroup$
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}}

| improve this answer | |
$\endgroup$
2
$\begingroup$

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[[1]], 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;
idx = A[[i]]["AdjacencyLists"]

{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,

A["AdjacencyLists"]

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

The drawback is that you are limited to positive integer labels. But that is easily compensated if necessary.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – amator2357 Jan 10 '19 at 16:24
  • $\begingroup$ You're welcome. Don't forget to upvote helpful answers; this is what drives to community. $\endgroup$ – Henrik Schumacher Jan 10 '19 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.