Combinatorics helpers

[denisrosset]

Put all of this in an extras subfolder

• Self-contained Matlab function that takes a matrix of generators (permutations), one per row, and returns the closure of that as matrix with the same convention.

• Function that computes all the permutations of a row vector under the action of generators. Either use the Dimino function above, or an orbit algorithm.

• Function that returns the permutation that maps a row vector to another row vector if it exists from the closure of a list of generators. Bonus point if it returns the corresponding word.

generator is x1 = [2 3 4 1]
we want to map [1 1 2 2] to [2 2 1 1]`

Then output would be perm = [3 4 1 2], and word = [1 1] meaning x1 * x1

How to compute words?

Convention is: positive indices are generators, negative indices are generator inverses

[1 2 -1] is x1 x2 x1^-1

Take the list of elements from Dimino, we write the i-th element el{i}, assuming identity is the first one.

By convention, gen(i) = xi if i > 0 and gen(i) = x{-i}^-1 if i < 0.

We maintain three additional vectors G (generator index), I (image index), L (length), they represent a graph.

We have that action(gen(G(i)), el{i}) == el{I(i)}, L(i) = L(I(i)) + 1. For the identity G(1) = I(1) = L(1) = 0 (basically, G and I are not used for the identity).

Now, fill these vectors minimizing L(i). For that, maintain a list of elements that have been discovered, starting with the identity, called toCheck.

(depth first graph traversal of the Cayley graph of the group)

while ~isempty(toCheck)
  h = toCheck(1)
  remove h from toCheck
  apply generators to el{h}, see if you find any new element
  if yes, update G, I, L accordingly
  add the new elements to toCheck
end

(example: 2x2 rubik cube)