# Searching for an unordered triple in a list of triples

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?

• You could Sort subsets first.... – David G. Stork Dec 17 '17 at 17:19
• Do you have to apply the MemberQ check often? – Henrik Schumacher Dec 17 '17 at 22:35
• Yes, but Sort seems to do the trick. – leastaction Dec 17 '17 at 23:10

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}

• Thanks for your answer @kglr. – leastaction Dec 17 '17 at 23:11
• @leastaction, my pleasure. – kglr Dec 17 '17 at 23:58

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

• Note that this way, the arrays get unpacked which slows things down. Mapping Sort over the list is faster... – Henrik Schumacher Dec 17 '17 at 21:56

Another workaround

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

(*    True    *)

• Thanks for your answer @Akku14 – leastaction Dec 17 '17 at 23:11

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.

• Thanks for your answer @Henrik Schumacher! – leastaction Dec 17 '17 at 23:11
• @leastaction You're welcome! – Henrik Schumacher Dec 17 '17 at 23:54