# Filter pattern from a list

I have group elements, that I'd like to condense down according to group rules. Take the modular group. This has generators $S,T$ that satisfy the groups relations $S^2 = I, (ST)^3 = I$.

So given a group element as a list of generators (for instance, $S T^2 S$ I'd write as {S,T,T,S} in Mathematica), I'd like to collapse the expression down according to group rules.

For instance, in our example, we'd have

Collapse[{S,T,S,S,T}] = {S,T,T}


I've tried using ReplaceAll, but can't get it to match substrings. StringReplace seems to have the correct functionality, but only works on actual strings.

How would one go about doing this?

• In general, this is sort of a hard problem. My take on it in the past has been to choose a "normal order", since writing group elements in terms of generators is not unique in general. Maybe start with this question and answer. I know there are many more on this site. The real question is, what do you want to do with this? Do you want to have a list of all the group elements in terms of the generators? How do you decide when you're done? Jan 31, 2016 at 18:52
• By the way, does this particular presentation lead to a finite group? Jan 31, 2016 at 19:04

Using replacement Rules

collapse[lst_?VectorQ] := lst //. {
{b___, S, S, e___} :> {b, e},
{b___, S, T, S, T, S, T, e___} :> {b, e}}

collapse[{S, T, S, S, T}]

(*  {S, T, T}  *)

collapse[{S, S, T, S, T, S, T, S, T, S, S, T}]

(*  {T, T}  *)

• I think I would go with {b___, T, S, T, S, T, e___} :> {b, S, e} instead of the second one. It along with the first rule makes your second rule, but this one will get more cases. +1 Jan 31, 2016 at 19:21

Using SubstitutionSystem:

collapse[lst_?VectorQ, rule_] := Module[{
str = StringJoin @@ ToString /@ lst},
Characters@SubstitutionSystem[rule, str]
];

vecs = {{S, T, S, S, T}, {S, S, T, S, T, S, T, S, T, S, S, T}};

rule = {"SS" -> "", "STSTST" -> ""}


Usage:

collapse[#, rule] & /@ vecs


Result:

{{"S", "T", "T"}, {"T", "T"}}

Here I have assumed that the input vector has Symbols, so a conversion to String is necessary. If the input vectors already have String characters, then another function with the same name but a different input can be defined. To get symbols back, one can additionally run ToExpression on the output of the function.