6
$\begingroup$

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?

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

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}

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

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 *)
$\endgroup$
  • 2
    $\begingroup$ Note that this way, the arrays get unpacked which slows things down. Mapping Sort over the list is faster... $\endgroup$ – Henrik Schumacher Dec 17 '17 at 21:56
3
$\begingroup$

Another workaround

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

(*    True    *)
$\endgroup$
  • $\begingroup$ Thanks for your answer @Akku14 $\endgroup$ – leastaction Dec 17 '17 at 23:11
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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