# Fastest way to check if an expression contains all symbols from a list

I need to execute this function thousands of times, and the faster, the better. I came up with two versions, but wanted to see if you can come up with an even faster way. Is there a better way?

I use the list:

symbolsList={r,A,b}


And the function checks if my expression contains all those symbols:

expression=r^2+A*b-3


First version:

ContainsAllSymbols[expression_]:=Block[{containsAllSymbols},
containsAllSymbols=True;
Do[containsAllSymbols=containsAllSymbols&&!FreeQ[expression,symbolsList[[dvi]]];If[!containsAllSymbols,Break[]],{dvi,Length[symbolsList]}];
containsAllSymbols
]


Second version (faster):

ContainsAllSymbols[expression_]:=Scan[If[FreeQ[expression,#],Return[False]]&,symbolsList]=!=False

-
Thanks for accepting my answer. On the other hand, I would recommend you to wait about one day before accepting an answer. There may be better answers coming out. –  Yi Wang Feb 13 '14 at 17:06
Yes, you were right. I'll unaccept and wait a little more. But yours seems very promissing. Thanks again. –  Giovanni Feb 13 '14 at 17:34

I am not sure if the return value of Variables meets your standard. If so, this works.

Complement[symbolsList, Variables@expression] == {}

AbsoluteTiming@
Do[Complement[symbolsList, Variables@expression] == {};, {200000}]


{0.575185, Null}

As @Szabolcs commented, Level[expression, {-1}] may be a nice alternative. And it's actually faster in this example:

AbsoluteTiming@
Do[Complement[symbolsList, Level[expression, {-1}]] == {};, {200000}]


{0.365893, Null}

They have similar speed to the OP's solution though.

AbsoluteTiming@Do[ContainsAllSymbols2[expression], {200000}]


{0.942182, Null}

-
+1, instead of Variables you can also use Level[expr, {-1}], which will give more control over what to include. (E.g. if you need heads, Level has an option for that.) –  Szabolcs Feb 13 '14 at 16:23
Could you please compare with the timings of my second solution? I think my solution works faster if the expression is big, since it breaks on the first non occurence of a symbol on symbolsList. Your computer seems to be a lot faster than mine :). –  Giovanni Feb 13 '14 at 16:40
In your particular example they have comparable speed. If there are symbols which doesn't exist, yours may be faster. –  Yi Wang Feb 13 '14 at 16:50
@Giovanni I also noticed your code should be FreeQ, not !FreeQ. Benchmark is updated. –  Yi Wang Feb 13 '14 at 17:01
Corrected there, thanks! Your code seems faster in all situations after I corrected the bug. –  Giovanni Feb 13 '14 at 17:06

Here;s one approach:

expression = {r^2 + A*b - 3};
vars1 = {r, A, b};
vars2 = {r, A, w, d};
Total[Boole[FreeQ[expression, #] & /@ vars1]] == 0


For example, this returns True for vars1 and False for vars2.

-
It's an alternative, timed between my first and second approaches. –  Giovanni Feb 13 '14 at 17:09

Of all the approaches not yet presented here this one seems to be the fastest:

containsAllSymbols[expr_, s_] := !FreeQ[expr, s]

containsAllSymbols[expr_, first_, rest__] :=
And[!FreeQ[expr, first], containsAllSymbols[expr, rest]]


EDIT: I claimed this to be faster than Complement[symbolsList, Variables@expression] but I was wrong, sorry.

Note that this approach does not use List wrapper. You might want to additionally define

ContainsAllSymbols[expr_, {s__Symbol}] := containsAllSymbols[expr, s]


I think it's worth noting that And[False, (rest)] does not evaluate (rest), a well as Or[True, (rest)].

UPD: As observed by Yi Wang in commments, you might want to use this method if you suspect that some symbols are not in the expression. Suspicious symbols should then be placed first in the symbols list.

-
Yours is faster than mine when I tested. However, if I use the OP's test data, symbolsList = {r, A, b}, expression = r^2 + A*b - 3, I got False for containsAllSymbols[expression, symbolsList]. I think it is supposed to be True. Or did I miss anything? –  Yi Wang Feb 13 '14 at 21:23
Sorry, I see. symbolsList should be written as Sequence@@symbolsList. Then the result is correct but it takes also a bit longer. –  Yi Wang Feb 13 '14 at 21:25
@YiWang My fault. I didn't check my data set as well, so I erroneously concluded it was faster. :-) Still, I think it's worth to be posted, mostly for the sake of And[False, …] trick. –  Akater Feb 13 '14 at 21:29
Thanks for explanation! This is a very interesting method. Nice to see! Also I guess for some data sets yours may be faster than mine (where And[False, ...] quits early). I didn't test though. –  Yi Wang Feb 13 '14 at 21:32