## 3 Methods
### New Measures of Permutation Distance
#### 3.2.3 K-Cycle Distance  
Cycle distance and cycle edit distance assume that arbitrary length cycles can be induced in a single operation, which is needed for \(\text{Cycle}(\alpha)\) since it does not restrict the induced cycle length. However, this is not suitable when characterizing fitness landscapes for the \(\text{Cycle}(kmax)\) mutation operator, which does limit the cycle length to \(kmax\). We now define \(k\)-cycle distance, which limits operations to inducing cycles of lengths \(\{2,3,\dots,k\}\). The \(k\)-cycle distance is not an edit distance. Instead, it is a weighted sum over the cycles of the pair of permutations, where the weight of each cycle is the minimum number of induced cycles of length at most \(k\) necessary to transform the cycle to all fixed points. That is, \(k\)-cycle distance does not consider operations that span multiple cycles. A cycle of length \(c\leq k\) can be transformed to \(c\) fixed points by inducing a cycle of length \(c\). If the cycle length \(c>k\), a sequence of cycles can derive \(c\) fixed points. For \(k\)-cycle distance, iteratively induce cycles of length \(k\) until the remaining cycle length is at most \(k\), completing the transformation with one final cycle operation. Each intermediate cycle creates \(k-1\) fixed points. Consider the following example beginning with permutations:  
\[p_{1} =[0,1,2,3,4,5,6,7,8,9] \tag{29}\] \[p_{2} =[2,3,1,5,6,7,8,9,4,0].\]  
There are two non-singleton permutation cycles in this example with element sets:  
\[\{1,3,5,7,9,0,2\},\{4,6,8\}. \tag{30}\]  
If we are computing 3-cycle distance, then we consider cycle mutations of lengths 2 and 3. The cycle with elements \(\{4,6,8\}\) can thus be transformed into all fixed points with a single cycle mutation since its length is less than or equal to 3 to obtain  
\[p_{1} =[0,1,2,3,4,5,6,7,8,9] \tag{31}\] \[p_{2} =[2,3,1,5,4,7,6,9,8,0].\]  
The longer cycle \(\{1,3,5,7,9,0,2\}\) requires a sequence of three operations. The first two produce \(k-1=2\) fixed points each with one final cycle mutation for the remaining three elements. First, cycle elements \(3,5\), and \(7\), resulting in fixed points for elements \(3\) and \(5\):  
\[p_{1} =[0,1,2,3,4,5,6,7,8,9] \tag{32}\] \[p_{2} =[2,7,1,3,4,5,6,9,8,0].\]  
A cycle of \(\{1,7,9,0,2\}\) remains. Cycle elements \(7\), \(9\), and \(0\), creating fixed points \(7\) and \(9\):  
\[p_{1} =[0,1,2,3,4,5,6,7,8,9] \tag{33}\] \[p_{2} =[2,0,1,3,4,5,6,7,8,9].\]  
A cycle of \(\{1,0,2\}\) remains, which transforms into fixed points with one final cycle mutation:  
\[p_{1} =[0,1,2,3,4,5,6,7,8,9] \tag{34}\] \[p_{2} =[2,3,1,5,6,7,8,9,4,0].\]0  
With this example in mind, we now derive the \(k\)-cycle distance, assuming \(k\geq 2\). First, given a cycle of length \(c\), the fewest cycle edits of length at most \(k\) necessary to transform it to \(c\) fixed points is \([(c-1)/(k-1)]\). To compute \(k\)-cycle distance, sum this over all cycles, \(\text{CycleSet}(p_{1},p_{2})\), of the permutations \(p_{1}\) and \(p_{2}\). Therefore, define \(k\)-cycle distance by  
\[\delta_{k}(p_{1},p_{2})=\sum_{ \begin{subarray}{c}\text{cycle}\in\text{Cycle Set}(p_{1},p_{2})\\ c=\text{cycle}\end{subarray} }\left[\frac{c-1}{k-1}\right]. \tag{35}\]The \(k\)-cycle distance can be computed in \(O(n)\) time. It is a metric when \(k\leq 4\), but it is only a semi-metric for \(k\geq 5\). Independent of \(k\), it trivially satisfies non-negativity since the expression within the sum of Equation (35) is never negative; and since \(\text{CycleSet}(p_{1},p_{2})\) computes the same set of cycles as \(\text{CycleSet}(p_{2},p_{1})\), it is also trivially symmetric. It satisfies the identity of indiscernibles as follows. If \(p_{1}=p_{2}=p\), then there are \(n\) singleton cycles, and since the expression within the sum of Equation (35) is 0 when \(c=1\), we have \(\delta_{k}(p,p)=0\). In the other direction, if \(\delta_{k}(p_{1},p_{2})=0\), then all elements in the summation must be 0, and that only occurs with fixed points. Thus, \(\delta_{k}(p_{1},p_{2})=0\implies p_{1}=p_{2}\).