Commutator
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 formulas in a Rubik's cube can be written as commutators.
Currently, the time complexity of this algorithm is 
. It is still unknown if there is a faster algorithm or if this algorithm can detect all possible commutators.
If you have a better algorithm, please let me know. Thank you.
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 b]"
Explanation: a b + c b + b' a' + b' c' = a b c a' b' c'.
And "[a c',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.
9 Aug 10, 2022
6 Jan 1, 2023
157.8k Dec 29, 2022
42k Jan 4, 2023
7k Jan 4, 2023
24 Jun 2, 2022
1 Jan 3, 2022
7 Aug 5, 2022
29 Dec 3, 2022
1 Nov 14, 2022