Searching for an unordered triple in a list of triples

Question

I have a list of triples which looks like this

T = {{7, 1, 2}, {7, 2, 3}, {7, 3, 8}, {7, 1, 6}};

(I have suppressed a few triples for clarity. My real list is larger.)

The problem is that

MemberQ[T, {7, 1, 2}]

returns True, but

MemberQ[T, {7, 2, 1}]`

returns False.

It is a known fact that a list is treated as an ordered list, not as a set, by Mathematica. But in my specific application, all I want to distinguish between are triples like {7, 1, 2} and {7, 3, 8}. But {7, 1, 2} and {7, 2, 1} are to be treated as identical.

How do I achieve this in Mathematica?

Answer 1

This seems to be a case for OrderlessPatternSequence

tT = {{7, 1, 2}, {7, 2, 3}, {7, 3, 8}, {7, 1, 6}};

MemberQ[tT, {OrderlessPatternSequence[1, 2, 7]}]

True

Or define a function to wrap the second argument of MemberQ:

foo = {OrderlessPatternSequence @@ ##}&;

MemberQ[tT, foo @ {1,2,7}]

True

MemberQ[tT, foo @ #] & /@ {{1, 2, 7}, {3, 8, 7},{1, 2, 3}}

{True,True,False}

Answer 2

If the order will never matter for your lists, you can use an Orderless head rather than list.

I use slist (sorted list) :

ClearAll[slist]    
SetAttributes[slist, Orderless]

Then Mathematica will automatically sort any input given to slist :

slistT = slist @@@ T

{slist[1, 2, 7], slist[2, 3, 7], slist[3, 7, 8], slist[1, 6, 7]}

This is the way Mathematica handles functions like Plus or Times which don't care about the order of their elements.

In your case, you can do

 MemberQ[slistT, slist[7, 1, 2] ]  (* True *)
 MemberQ[slistT, slist[7, 2, 1] ]  (* True *)

Answer 3

Another workaround

Xor @@ Sequence[MemberQ[T, #] & /@ Permutations[{7, 2, 1}]]

(*    True    *)

Answer 4

If you have to perform many checks of this kind, it might justify the overhead to create a lookup table in form of an Association.

The first thing here is a listable variant of Sort that also employs parallelization.

sort = Compile[{{list, _Integer, 1}},
   Sort[list],
   RuntimeAttributes -> {Listable},
   Parallelization -> True
   ];

This will be the replacement for MemberQ. Note that we

memberQ[S_Association, R_?MatrixQ] := Unitize[Lookup[S, sort@R, 0]];
memberQ[S_Association, R_?VectorQ] := Unitize[Lookup[S, sort[{R}], 0]][[1]];

Some not so big test data...

n = 2000;
m = 30;
d = 3;
T = DeleteDuplicates[sort@RandomInteger[{1, m}, {n, d}]];
R = RandomInteger[{1, m}, {n, d}];

Now, we create the lookup table S for T:

S = AssociationThread[sort@T, Range[Length[T]]]; // AbsoluteTiming // First

0.002173

And this is how our new memberQ compares to MemberQ in conjunction with Sort:

a = Boole[MemberQ[T, Sort[#]] & /@ R]; // AbsoluteTiming // First
b = memberQ[S, R]; // AbsoluteTiming // First
a == b

0.496145

0.001229

True

This will also work well for longer lists. For lists of length d=2, it is more efficient to use a SparseArray as lookup table. For short lists of given length d, this can be further improved by writing specialized and compiled sorting routines.