# Position of Subsets in a List

I have a particular list of integers and a matrix whose entries are lists. Say I know that my particular list is a subset of at least some of the elements in the matrix. I want to find an efficient way to find the positions of all of the elements of the matrix of which my list is a subset.

Right now, I just loop through all of the entries in the matrix and keep track of which ones entirely contain my list (M is the matrix I want to search through and mylist is my list of integers):

Matches[mylist_] := (
match = {};
Do[Do[If[Intersection[M[[i, j]], mylist] == mylist, match = Append[match, {i, j}]]
,{j,Length[M[[i]]]}];
,{i,Length[M]}];
match);


As an example of my desired output:

M = {{{1, 2, 3}, {1, 2, 4}}, {{5, 4, 3}, {1, 2, 1}}};
Matches[{1, 2}]
(*={{1, 1}, {1, 2}, {2, 2}}*)


This function works how I want it to, but in the code I'm working on I wind up using it thousands of times with matrices and lists containing many more elements. Calling it so many times becomes the limiting factor in how quickly my code runs. Are there any ways to accomplish this that would be more efficient?

I've tried using Position:

Matches2[mylist_]:=(Position[M, _?(Intersection[#,mylist]==mylist&)]);


Using Intersection in a pattern like this generates errors that I don't know how to correct, though, and I'm not sure whether this approach would be faster to begin with. If anyone knows of any more efficient ways to do this, it would be greatly appreciated. Thanks!

• +1 for what turns out to be an interesting problem. With some additional clarification (e.g., are bottom-level lists all the same length, etc.) my gut feeling is there's a clever and efficient way to do this. – ciao Jun 28 '14 at 8:18

## 4 Answers

I'm interpreting your OP as wanting positions of lists that contain the element(s) in your target list, not the precise sequence only, etc. which is what other answers so far seem to do. If that's not what you're after, please clarify the OP.

E.g., given a list {{{1,2,3},{2,1,3}},{{1,4,5},{1,5,2}}}, targets of either {1,2} or {2,1} should return {{1, 1}, {1, 2}, {2, 2}}. Again, if that's not the case, please clarify.

That said, the following is pretty fast (since you said efficiency is important and the actual lists are larger than your examples - an area where doing this using rules/patterns can sometimes get disastrously slow. A quick test shows this ~300X faster on a 10K X 10 X 10 array test than your code - depends on data distribution.):

setPos=Catch[Block[{l = #, s = #2, i},
Fold[If[(i =
Intersection[#,
SparseArray[Unitize@BitXor[l, #2], Automatic, 1][
"NonzeroPositions"][[All, ;; 2]]]) == {}, Throw[{}], i] &,
SparseArray[Unitize@BitXor[l, First@s], Automatic, 1][
"NonzeroPositions"][[All, ;; 2]], Rest@s]]] &;


Using your M

setPos[M, {1, 2}]
(* {{1, 1}, {1, 2}, {2, 2}} *)


As an aside, generally a bad idea to use uppercase letters/initials for your own symbols - might clash with built-ins...

Here's a lengthier realization, performance depending on data characteristics is from a bit faster to much (~5X +) than the above:

newSet = Block[{foldp =
DeleteDuplicates@
SparseArray[BitXor[1, Unitize@BitXor[First@#2, #1]]]["NonzeroPositions"][[All, ;; 2]],
startv, foldn, i, target = Rest@#2},

startv = Extract[#1, foldp];

foldp[[Catch[
Fold[If[(i =
Intersection[#, #[[Join @@
SparseArray[
BitXor[1, Unitize@BitXor[#2, startv[[#]]]]][
"NonzeroPositions"][[All, ;; 1]]]]]) == {},
Throw[{}], i] &, Range@Length@foldp, target]]]]] &


As above, arguments are the matrix and the target elements list, and as above the output matches that of your code, just... faster.

Here's a quick test of the existing answers, using RandomInteger[10, {size, 10, 10}] to generate lists and target = Range@2 as the target subset. Note the time scale is logarithmic. I used my first answer, since the test lists/targets were simple, and the second comes into its own with more convoluted cases. The usual loungebook benchmark caveats apply... the roughness of the plot for my times is from it being in the noise or below timing resolution combined with log scale. Here's the three fastest extended out to list size of 20,000 to get a better picture of the trend (same data generation as above). Kudos to those respondents for terse solutions with usable performance (I'd expect all three of these to be 5-10X faster on a "real" machine): Lastly, prompted by eldo's comment, the fastest three with a more complex case: longer sublists, longer target sets, and greater sparsity for matches where the penalty for repeated use of Position gets costly. Only run to length 10,000: • Now I see what you were saying; I misunderstood your point yesterday as being about the position returned rather than ordering. I agree with you. – mfvonh Jun 28 '14 at 15:16
• If you get the chance I'd be curious to see how my edit stacks up in the timing chart. – mfvonh Jun 28 '14 at 15:33
• @mfvonh: Happy to, except I can't get proper results from the edit, e.g. looking for {1,2} in {{{1, 2, 3}, {2, 1, 3}}, {{1, 4, 5}, {1, 5, 2}}, {{1, 4, 5}, {1, 5, 2}}} gives incorrect results. Typo in the edit? Interestingly, it gets the right number of results... – ciao Jun 28 '14 at 22:14
• Also, unrelatedly, you've had several killer answers recently using bitwise ops. I know what they do but not how to take advantage of them practically. Do you by chance have any reading you could recommend? – mfvonh Jun 28 '14 at 23:08
• @mfvonh: I know of no text on just the subject, but Knuth's epic series covers them, Hacker's Delight has good examples. Mine comes from assembly programming, and one of my startups used bit-mapped indexed techniques for databases. Basically, whenever I see a problem where "indicators" can be used, I'll try a bit-wise method because they're compact, usually quite efficient - particularly when machine-sized. Hope that helps... also - added your new routine to results. – ciao Jun 28 '14 at 23:43

EDIT

Not fast but short

SetAttributes[ul, Orderless];
matches[matrix_, {list__}] :=
Position[matrix /. List[i__Integer] -> ul[i], ul[list, ___], {2}];
m = {{{1, 2, 3}, {2, 1, 3}}, {{1, 4, 5}, {1, 5, 2}}};
matches[m, {1, 2}]


{{1, 1}, {1, 2}, {2, 1}}

matches[m, {2, 1}]


{{1, 1}, {1, 2}, {2, 1}}

m = {{{1, 2, 3}, {2, 1, 3}}, {{1, 4, 5}, {1, 5, 2}}, {{1, 4, 5}, {1, 5, 2}}}
matches[m, {2, 1}]


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

• @ mfvonh I'm afraid that your answer gives a wrong result for m = {{{3, 1, 2}, {1, 2, 4}}, {{5, 4, 3}, {1, 2, 1}}}. – eldo Jun 27 '14 at 21:17
• @eldo It does? What should the result be in your view? – mfvonh Jun 27 '14 at 21:19
• {{1, 2}, {2, 2}} - I admit that the question is ambigious: Would 1 and 2 always be in position 1 and 2 ? – eldo Jun 27 '14 at 21:23
• @eldo I didn't understand the OP to mean 1,2 would be fixed within the element. "I want to find an efficient way to find the positions of all of the elements of the matrix of which my list is a subset." – mfvonh Jun 27 '14 at 21:24
• I agree, sorry for the objection :) – eldo Jun 27 '14 at 21:26
subsetQ = And @@ Table[MemberQ[#1, i], {i, #2}] &;
posF = Function[{a1, a2}, Position[a1, _?(subsetQ[#, a2] &)]]
posF2 = Function[{a1, a2}, Join @@ MapIndexed[If[subsetQ[#, a2], #2, ## &[]] &, a1, {2}]]
posF[m, {1, 2}]
(* {{1,1}, {1,2}, {2,2}} *)
posF[m, {1, 2}] == posF2[m, {1, 2}]
(* True *)


(Note: not to be compared with rasher's method -- since neither stands a chance :)

• That's a nice second one - redoing my tests with it. +1 – ciao Jun 28 '14 at 8:02
M = {{{1, 2, 3}, {1, 2, 4}}, {{5, 4, 3}, {1, 2, 1}}};

Drop[#, -1] & /@
Position[M /. {a_ /; a == 1, b_ /; b == 2, c_} :> {{a, b}, c}, {1, 2}]


{{1, 1}, {1, 2}, {2, 2}}

REVISION

To make my answer compatible with the others:

FindPosition[m_, a_, b_] :=
Intersection @@ Map[Most, {Position[m, a], Position[m, b]}, {2}]

FindPosition[M, 2, 1]


{{1, 1}, {1, 2}, {2, 2}}

FindPosition[M, 3, 4]


{{2, 1}}

EDIT

To allow for more than two target elements:

M = {{{1, 2, 3, 4}, {1, 2, 4, 3}}, {{5, 2, 4, 3}, {1, 2, 1, 4}}};

FindPosition[m_, v_] :=
Intersection @@ Map[Most, Position[m, #] & /@ v, {2}]

FindPosition[M, {2, 1, 4}]


{{1, 1}, {1, 2}, {2, 2}}

• I've added timings for this, note however the revision is still not generalized: the OP states actual use will have lists of varying sizes, your revision takes two and only two target elements... – ciao Jun 28 '14 at 11:03