4
$\begingroup$

The Caley distance measures the distance between two permutations (see this question for a definition https://math.stackexchange.com/questions/1932991/catalan-number-and-cayley-distance-inequality-in-permutation-group). Mathematica has lots of nice commands for permutations but the Caley distance is not a built-in function. I'm looking for Mathematica code that implements it.

$\endgroup$

2 Answers 2

5
$\begingroup$

If I understand correctly the Cayley distance, then

patt = RandomInteger[{0, 9}, 10]
dis = RandomSample @ patt

{3, 5, 5, 0, 1, 7, 7, 0, 7, 2}

{7, 7, 5, 1, 0, 0, 3, 2, 5, 7}

The distance should be the sum of the lengths of the cycles each diminished by one, or in other words the sum of the lengths diminished by the number of cycles; equal to 8 in this case because

perm = FindPermutation[patt, dis]

Cycles[{{1, 7, 2, 3, 9, 10, 8, 6}, {4, 5}}]

The distance is equal to the order of the permutation:

PermutationOrder @ perm

8

As a function:

CayleyDistance[patt_, dis_] := 
 PermutationOrder @ FindPermutation[patt, dis]
$\endgroup$
3
  • $\begingroup$ Nice, I did not know about FindPermutation. $\endgroup$ Commented Oct 26, 2016 at 23:59
  • 4
    $\begingroup$ I will tell you a secret, but don't tell anyone: 30 mins ago I also didn't know about it ;) Sometimes having the slightest idea about what you want to achieve allows to browse through the documentation and stumble upon something useful. In this case, I started with Permute. $\endgroup$
    – corey979
    Commented Oct 27, 2016 at 0:02
  • 2
    $\begingroup$ @corey979 -- nice job... this is why stackexchange is one of the best resources for learning Mathematica! $\endgroup$
    – bill s
    Commented Oct 27, 2016 at 0:04
0
$\begingroup$

If we want to measure the Caley distance using as inputs two permutations given in Cycle notation:

f[x_, y_] := Module[{z}, 
             z = PermutationProduct[InversePermutation[Cycles[x]],Cycles[y]][[1]];
               Length[Flatten[z]] - Length[z]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.