Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question
    
+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. –  rasher Jun 28 at 8:18

4 Answers 4

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.

enter image description here

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

enter image description here

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:

enter image description here

share|improve this answer
    
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 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 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... –  rasher Jun 28 at 22:14
    
Thanks, I've been dropping the ball left and right on this one. The problem was the Orderless attribute was causing the matrix rows themselves to be sorted canonically. Should be fixed now :) –  mfvonh Jun 28 at 22:44
    
@mfvonh: LOL, I know the feeling. Will update results shortly... –  rasher Jun 28 at 22:50

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

share|improve this answer
    
@ 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 at 21:17
    
@eldo It does? What should the result be in your view? –  mfvonh Jun 27 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 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 at 21:24
    
I agree, sorry for the objection :) –  eldo Jun 27 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 :)

share|improve this answer
    
That's a nice second one - redoing my tests with it. +1 –  rasher Jun 28 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}}

share|improve this answer
    
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... –  rasher Jun 28 at 11:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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