Position of Subsets in a List

Question

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!

Answer 1

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:

Answer 2

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}}

Answer 3

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 :)

Answer 4

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}}