# Finding similar expressions in list

I have a function that returns to me lists of expressions, like:

I (a^2 + b^2) (* 1 *)
a (I b + e)   (* 2 *)
b (I a + d)   (* 3 *)
b (I a + f)   (* 4 *)
a b           (* 5 *)
a (I b + f)   (* 6 *)
I (b^2 + c^2) (* 7 *)


The expressions can become arbitrary complex.

Now I want a function that returns to me that expression 2,3,4,6 as well as 1,7 are similar, because one can just rename the variables.

I have absolutly no idea how to solve this problem, and would be very happy for any hint in the right direction.

Update on similarity-criterion

Similar means:

 a -> b, c, d, e, f, ... zzzz, SomeVar1, ...


(If it is simpler, for the moment one can assume that the list of variables can be only a,b,c,d,...,z = 26 lowercase letters).

It must not transform the structure of the equation, for instance:

 a (I b + e)


Here, a cannot become b or e, b cannot become a or e, e cannot become a or b, i.e. all of them must be different.

All terms a, b, c, d are simple variables, and cannot become Sin[a], Tan[b], 1/c, ...

Examples:

• a (I b + e), b (I a + d), b (I a + f), a (I b + f) are all similar
• a^2 + b and a + b^2 are similar
• a (c + d) + b (c + e) and a (c + d) + b (e + f) are not similar because c is repeated in the first one but not the second one
-
We should start with figuring out a precise definition for "similar". Can we say that two expressions are similar if they can be transformed into each other by replacing the some variables with other variables? If yes, are a+b and 2a similar? Replacing b by a in a+b gives 2a. (This would be a problem for pattern matching.) Do you have a short fixed list of variables that can appear? Are all your expressions polynomial or do you also have Sin[a] in there? –  Szabolcs Mar 24 '14 at 15:44
Thanks Szabolcs, I added an update to make the "similarity" clearer. –  NicoDean Mar 24 '14 at 15:54
Can you please choose a better display name than user3378652? It doesn't have to be your real name, but it'd be nice if it were something we can remember instead of the automatically assigned generic name. –  Szabolcs Mar 24 '14 at 18:29
Ah thats possible, thought I forgot that while registration and cannot change it anymore :). Done. –  NicoDean Mar 24 '14 at 18:32
StackExchange wanted to keep the entry barrier low, so it's possible to ask a question without registering or giving any name at all. In that case a name will be generated automatically. If you register, you can always change the display name to anything you like (I think there's a limit on how many changes you can make in a given time period). Your user is kept track by a numerical ID (12750 in your case, you can see it in some URLs) which is not used for display. –  Szabolcs Mar 24 '14 at 18:35

Jump straight down to Update 2 for the final code. I'll leave the previous iterations here as they explain how that solution developed.

This is based on the following definition of similarity:

Two expressions are similar if they become identical when all variables are replaced by the same generic variable.

For example, both $a+b$ and $b+c$ become $G+G=2G$ when their variables are replaced by $G$, hence they are similar. Note: according to this definition $a+b$ and $2a$ are similar.

First we need a function to extract variables:

variables[expr_] := Cases[Level[expr, {-1}], v_ /; ! NumberQ[v]]


(Note that Variables works for polynomials only.)

This function replaces all variables by generic:

Clear[generic]
generalize[expr_] := expr /. Thread[variables[expr] -> generic]


list = {I (a^2 + b^2), a (I b + e), b (I a + d), b (I a + f), a b, a (I b + f), I (b^2 + c^2)}


Now all we need is a GatherBy:

GatherBy[list, generalize]

(* ==>

{{I (a^2 + b^2), I (b^2 + c^2)},
{a (I b + e), b (I a + d), b (I a + f), a (I b + f)},
{a b}}

*)


There are some problems here:

First I considered using Hold in generalize to keep the structure of the expression unchanged, as the OP requested:

generalize[expr_] := With[{e = expr}, Hold[e]] /. Thread[variables[expr] :> generic]


When using this on a^2+b or b^2+a, it gives structurally different expressions: generic^2+generic or generic+generic^2, due to the ordering of a and b within Plus. If we decide to keep the structure intact, then it would still be necessary to manually apply the effects of the attributes Flat and Orderless in the appropriate functions. This would make the code considerably more complicated. Mathematically it made sense not to use Hold, so finally I didn't. But keep in mind that now 2a and a+b will be considered equivalent, i.e. this solution doesn't require that distinct variables be kept distinct.

Update:

Here's a version that does not consider $a+b$ and $2a$ similar and takes care of Orderless and Flatten through pattern matching:

makePattern[expr_] :=
With[{e = expr}, HoldPattern[e]] /.

patterns = Union[makePattern /@ list]

Table[Cases[list, p, {1}], {p, patterns}]

(* ==> {{a b}, {a (I b + e), b (I a + d), b (I a + f), a (I b + f)}, {I (a^2 + b^2), I (b^2 + c^2)}} *)


This solution does require that distinct variables be kept distinct.

Pattern matching does take the Flat and Orderless attributes into account so a^2+b will match both HoldPattern[_^2+_] and HoldPattern[_+_^2] even though HoldPattern prevents any evaluation, including reordering.

Note on the choice of pattern: a variable is a Symbol that is not a number (NumberQ). For example Pi or E are both symbols and numbers, but not variables.

Update 2:

The following takes into account which variables must be the same and which must be different. For example,

{ a*(c + d) + b*(c + e),
a*(c + d) + b*(f + e) }


needed to be considered different because c is repeated in the first one but not the second one.

The implementation got rather hairy because this is essentially constructing code (patterns) while making sure not to evaluate it. It's also not very efficient.

Clear[variables, makePattern, iMakePattern, categorize]

variables[expr_] := Union@Cases[Level[expr, {-1}], v_ /; ! NumberQ[v]]

makePattern[expr_] := iMakePattern[expr, variables[expr]]

iMakePattern[expr_, {vars___}] :=
Module[{condition = Condition},
SetAttributes[condition, HoldRest];
condition[
expr /. Function[var, var -> var_Symbol?(Not@NumberQ[#] &)] /@ {vars},
UnsameQ[vars]
]
]

categorize[list_] := Union@Table[Cases[list, p, {1}], {p, makePattern /@ list}]


Now let's test it:

categorize[{1, I (a^2 + b^2), a (I b + e), b (I a + d), b (I a + f), a b, a (I b + f), I (b^2 + c^2)}]
(* ==> {{1}, {a b}, {I (a^2 + b^2), I (b^2 + c^2)}, {a (I b + e), b (I a + d), b (I a + f), a (I b + f)}} *)

categorize[{a*(c + d) + b*(c + e), a*(c + d) + b*(f + e)}]
(* ==> {{a (c + d) + b (c + e)}, {a (c + d) + b (e + f)}} *)

categorize[{a^2 + b, a + b^2}]
(* ==> {{a^2 + b, a + b^2}} *)

-
Thanks, that works as it should, and the idea behind it is also as I expected it to be (creating a list of different patterns). I tried to understand it, but i was not able to follow your makePattern-function. Could you please explain this in a bit more detail? Specifically, what does _Symbol?(Not@NumberQ[#] &) mean? Thanks! –  NicoDean Mar 24 '14 at 18:02
@user3378652 Let's break it down (please look up the pieces in the docs): _ matches anything. _Symbol matches anything with Head Symbol, i..e it matches a but not 1. _?fun matches anything for which the function fun evaluates to True. Thus _Symbol?(Not@NumberQ[#] &) would match an expression x if x is a Symbol and Not@NumberQ[x] is True. This is necessary to exclude numerical constants such as Pi from being matched. (I is not a Symbol but a Complex). –  Szabolcs Mar 24 '14 at 18:08
I just recognized some potential problems when one does not save the information about same variable-names:list = {a*(c + d) + b*(c + e), a*(c + d) + b*(f + e)};. With your function, this would give me one single result. But in fact, they are different, because in the first case, both terms in brackets contain c, in the second one, one c is replaced by f. Many of such examples can be creates, and I think one has to save the information about the same variable names aswell somehow. Do you have any idea? –  NicoDean Mar 24 '14 at 19:52
@NicoDean Stay tuned. I sort of have a solution but implementing it is turning out to be more difficult than I expected. –  Szabolcs Mar 24 '14 at 21:22
@NicoDean This is getting very hairy, and I had to use a number of non-obvious tricks to prevent undesired evaluation and undesired interpretations of Condition. I updated the post. Please test it. –  Szabolcs Mar 24 '14 at 21:40
data = {I (a^2 + b^2) (*1*), a (I b + e)   (*2*), b (I a + d)   (*3*),
b (I a + f)   (*4*), a b (*5*), a (I b + f)   (*6*),  I (b^2 + c^2) (*7*)}
systemnames = Names["System*"];
test[expr_] :=
Select[{Extract[expr, #], #} & /@ Position[expr, _Symbol, Infinity],
MemberQ[systemnames , ToString@(#[[1]])] &]
Gather[data, test[#1] == test[#2] &]

-
Thanks for this solution. I think I understand the main idea of this test, namely that it creates the test-function and compares each element. However, I'm not able to understand whats the main idea of the test-function. The function is unfortunatly too complicated for me to get any sense out of it, yet. Could you please give a short hint on how it works - will try to find out the rest on my own. Thanks! –  NicoDean Mar 24 '14 at 18:09
@user3378652 There are some problems with this approach. What it does is that it checks whether the various operations such as Plus (+) and Times (*) appear in the same position in different expressions. It only looks at operations which are in the System  context. Using this implementation 2a+b and 3a+b and 1+b are all considered equivalent because the + appears in the same place. However, a^2+b and a+b^2 are not considered equivalent because the Power appears in different places (due to automatic sorting of a,b). –  Szabolcs Mar 24 '14 at 18:26