# Decompose algorithms in commutator notation



## nbwzx (Mar 19, 2022)

Some algorithms in the Rubik's cube may not be too easy to decompose.
For example, actually D F' R U' R' D' R D U R' F R D' R' can be decomposed as D:[F' R U' R',D' R D R'], R' U S' U' S R U' R S R' S' U can be decomposed as [R' U S',U' S R S'].

Recently I made a tool to decompose algorithms in commutator notation.
You can view the website here.

It is mainly based on the following methods.
For an algorithm s in the Rubik's cube, suppose n is the length of s.
Firstly, since c a b a' b' c'=c:[a,b]=[c a c',c b c'], we only need to calculate the case when the first step and the last step of the algorithm cannot be offset.
Secondly, let i from 1 to n, j is the number of length of the i+1 th to nth string that can be offset, k from 1 to i. Let X=the first ith char of s ,Y=the (i+1)th char to the (i+j)th char of s add the (i-k)th char to the (i-1)th char of s.
Thirdly, do some post-processing to make the length of X and Y as small as possible.

Let me explain the second step with the example R' U S' U' S R U' R S R' S' U
In this example, we have i=3 by loop, X=R' U S', in U' S R U' R S R' S' U the first 3 steps and the last 3 steps can be offset, so j=1, and we have k=1 by loop, Y=U' S R S'
After checking, R' U S' U' S R U' R S R' S' U=[R' U S',U' S R S']

Another example U R S R' S' U2 R' S R S' U
We only need to decompose R S R' S' U2 R' S R S' U2 because of the first step.
In this example, we have i=4 by loop, X=R S R' S', in U2 R' S R S' U2 the first 1 step and the last 1 step can be offset, so j=1, and we have k=3 by loop,Y=U2 S R' S'
After checking, U R S R' S' U2 R' S R S' U=U:[R S R' S',U2 S R' S']=U:[R U2,U2 S R' S'] (since [a,b]=[a b',b])

Currently, the time complexity of the main parts (the second step) of this algorithm is O(n^2). It is still unknown if there is a faster algorithm or if this algorithm can detect all possible commutators. But this algorithm seems to perform well after much testing.


----------



## qwr (Mar 20, 2022)

I did not look at the details of this algorithm, but is this a string problem like palindrome?
Some string problems can be computed quicker with appropriate prefix sum or dynamic programming methods or automata search type algorithms
if I ever get better at such string competition programming problems I'll come back and look at it. You or I may also ask on stack overflow for string algorithm ideas.


----------



## nbwzx (Mar 20, 2022)

qwr said:


> I did not look at the details of this algorithm, but is this a string problem like palindrome?
> Some string problems can be computed quicker with appropriate prefix sum or dynamic programming methods or automata search type algorithms
> if I ever get better at such string competition programming problems I'll come back and look at it. You or I may also ask on stack overflow for string algorithm ideas.


Yes you are right. Essentially it's a string problem. We can consider this problem in terms of free groups. It consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. For algorithms in the Rubik's cube, the additional restriction is that the order is 4, which means U4=identity, F4=identity, etc.


----------



## abunickabhi (Mar 20, 2022)

Super useful tool. Thanks for the good work nbwzx!


----------



## qwr (Mar 20, 2022)

nbwzx said:


> Yes you are right. Essentially it's a string problem. We can consider this problem in terms of free groups. It consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. For algorithms in the Rubik's cube, the additional restriction is that the order is 4, which means U4=identity, F4=identity, etc.


I do not think it is necessary to consider the string problem in terms of free groups because we do not apply any reductions here (ex. we don't actually need the fact that U U = U2)
I didn't really understand your description but I assume your idea was my first thought which was using two indices i,j on string s of length n such that C = s[0:i], A = s[i:j], B = s[j:n/2]. I believe you can match all C to C' with incrementing i and all AB to A'B' with incrementing i,j with each match in constant time using a rolling hash. This gives us n^2/4 operations for the whole program without actually using any property of alg inverses. I assume this is what you proposed but I did not understand what you meant by offset in first step. You did not mention how you do string matching or how you found C (greedy? I don't think that will work) which I assume is what you mean by offset.


----------



## nbwzx (Mar 20, 2022)

qwr said:


> I do not think it is necessary to consider the string problem in terms of free groups because we do not apply any reductions here (ex. we don't actually need the fact that U U = U2)
> I didn't really understand your description but I assume your idea was my first thought which was using two indices i,j on string s of length n such that C = s[0:i], A = s[i:j], B = s[j:n/2]. I believe you can match all C to C' with incrementing i and all AB to A'B' with incrementing i,j with each match in constant time using a rolling hash. This gives us n^2/4 operations for the whole program without actually using any property of alg inverses. I assume this is what you proposed but I did not understand what you meant by offset in first step. You did not mention how you do string matching or how you found C (greedy? I don't think that will work) which I assume is what you mean by offset.


Sorry for my vague statement. English is not my mother tongue.

U2 may mean U U, or may mean U' U' in a Rubik's cube.
U may mean U, or may mean U' U' U' in a Rubik's cube, they may be different in the decomposion.
For example, U M U M' U M' U M=[U M U,M' U U]. However it is actually U M U M' U M' U' U' U' M.

The first step is just finding the C.
For example,
for R U' D' R' U R D R' U' R U R', the first two chars (R U') and the last two chars (U R') can be offset. But the third char is D' and the third to last char is R, they cannot be offset. So C=R U'.

Actually, C doesn't matter at all. R U' D' R' U R D R' U' R U R' is R U':[D',R' U R], but it can also be decompose into [R U' D' U R,R U' R' U R U R] using c a b a' b' c'=c:[a,b]=[c a c',c b c']. C is only used to make A and B short.

Just use A = s[0:j], B = s[j:n/2] can't work in some cases. For example a b c a' b' c'=[a b,c b].


----------



## qwr (Mar 20, 2022)

Oh I see, you actually want to do reductions (things like cancelling U U'). Then the problem becomes harder.
The reason I said you couldn't take C greedily is because in an string like C A B A' B' C', you would be taking some x from the start of A and x' from the end of B' (also the start of B). But if you allow a simple cancelling rewriting system, since it is a context-free grammar maybe efficient algorithms exist anyway. I will think about it when I am less busy.


----------



## nbwzx (Mar 20, 2022)

Yes, reductions make this problem not very easy. Looking forward to seeing a better or improved algorithms from you.


----------



## qwr (Mar 21, 2022)

How many moves are you willing to add to make an alg into a commutator? Is it bounded by a small number?


----------



## nbwzx (Mar 22, 2022)

qwr said:


> How many moves are you willing to add to make an alg into a commutator? Is it bounded by a small number?


What is your meaning of moves in this problem? Does it mean the moves of reductions? If so, I don't know the exact boundary of the reductions. But I guess that the moves of reductions won't be too long.


----------



## Luke Solves Cubes (Mar 22, 2022)

maths


----------

