Introduction
Decompose algorithms in commutator notation.
Let
be any
group. If
, then the commutator of
and
is the
element
. The expression
denotes the conjugate of
by
,
defined as
. Therefore,
means
.
In this repository, we assume that
is a
free group.
In mathematics, the free group
over a given set
consists of all words that can be built from members of
,
considering two words to be different unless their equality follows from the group axioms (e.g.
, but
for
). The members of
are
called generators of
,
and the number of generators is the rank of the free group. An arbitrary group
is
called free if it is isomorphic to
for some subset
of
, that
is, if there is a subset
of
such
that every element of
can be
written in exactly one way as a product of finitely many elements of
and
their inverses (disregarding trivial variations such as
).
It is worth researching since many 3-cycle and 5-cycle algorithms in a Rubik's cube can be decomposed into commutators.
Example 1:
Input: s = "R U R' U'"
Output: "[R,U]"
Example 2:
Input: s = "a b c a' b' c'"
Output: "[a b,c a']"
Explanation: a b + c a' + b' a' + a c' = a b c a' b' c'.
And "[a b,c b]" is also a valid answer.
Example 3:
Input: s = "D F' R U' R' D' R D U R' F R D' R'"
Output: "D:[F' R U' R',D' R D R']"
And "[D F' R U' R' D',R D R' D']" is also a valid answer.
Example 4:
Input: s = "R' F' R D' R D R2 F2 R2 D' R' D R' F' R"
Output: "R' F':[R D' R D R2,F2]"
Example 5:
Input: s = "R U R'"
Output: "Not found."
Constraints:
- s consist of only English letters.