## 3 Methods
### Cycle Mutation
#### 3.1.1 Shared Notation and Operations  
Let \(p\) be a permutation of length \(n\), such that \(p(i)\) is the element at index \(i\). Assume that indexes into \(p\) are 0-based (i.e., valid indexes are \(\{0,1,\ldots,n-1\}\)), as are array indexes. Algorithm 1 shows pseudocode for the core operation of both variations of cycle mutation. Namely, it induces a cycle in the given permutation \(p\) from an array of indexes into \(p\).  
```
1:temp \(\leftarrow\)\(p\)(indexes\([0]\))
2:for\(i=1\)to\(n-1\)do
3:\(p\)(indexes\([i-1]\)) \(\leftarrow\)\(p\)(indexes\([i]\))
4:\(p\)(indexes\([n-1]\)) \(\leftarrow\) temp
```  
**Algorithm 1** CreateCycle\((p,\text{indexes})\)As an example of its behavior, consider the following permutation:  
\[p=[2,6,0,5,3,8,7,9,4,1]. \tag{10}\]  
Now consider the following array of indexes into \(p\):  
\[\text{indexes}=[3,7,1,4]. \tag{11}\]  
Executing CreateCycle(\(p\), indexes) will produce the permutation \(p^{\prime}\) such that \(p^{\prime}(3)=p(7)\), \(p^{\prime}(7)=p(1)\), \(p^{\prime}(1)=p(4)\), and\(p^{\prime}(4)=p(3)\), resulting in the following:  
\[p^{\prime}=[2,3,0,9,5,8,7,6,4,1]. \tag{12}\]  
The runtime of CreateCycle is linear in the induced cycle length.  
One of the steps of cycle mutation requires sampling \(k\) random indexes into permutation \(p\) without replacement. Algorithm 2 shows our sampling approach, which uses one of three algorithms depending on the value of \(k\) relative to the permutation length \(n\).  
```
1:if\(k\geq\frac{n}{2}\)then
2:returnReservoirSample(\(n,k\))
3:elseif\(k\geq\sqrt{n}\)then
4:returnPoolSample(\(n,k\))
5:else
6:returnInsertionSample(\(n,k\))
```  
**Algorithm 2** Sample(\(n,k\))  
When \(k\geq\frac{n}{2}\), we use [PERSON]'s reservoir sampling algorithm [69] (line 2 of Algorithm 2), which has a runtime of \(O(n)\) and utilizes \(O(n-k)\) random numbers. When \(\sqrt{n}\leq k<\frac{n}{2}\), we use [PERSON] and [PERSON]'s sampling algorithm [70], which we refer to as PoolSample in line 4 of Algorithm 2, and which also has a runtime of \(O(n)\), but requires \(O(k)\) random numbers. Asymptotic runtime of both of these options is \(O(n)\), but since random number generation is a costly operation with very significant impact on the runtime of an EA [71], our approach chooses the sampling algorithm that requires fewer random numbers.  
When \(k<\sqrt{n}\), we use what we believe is a brand new sampling algorithm: insertion sampling (Algorithm 2, line 6). Insertion sampling's runtime is \(O(k^{2})\), and requires \(O(k)\) random numbers. Since runtime increases quadratically in \(k\), insertion sampling is only a good choice when \(k\) is very small relative to \(n\). Pseudocode for insertion sampling is in Algorithm 3. To ensure a duplicate-free result, it maintains a sorted list of the integers selected thus far, and inserts into that list in a way similar to insertion sort. The \(\text{Rand}(a,b)\) in Algorithm 3 is a uniform random variable over the interval \([a,b]\), inclusive.  
```
1:result - a new array of length \(k\)
2:for\(i=0\)to\(k-1\)do
3:\(p\leftarrow\text{Rand}(0,n-i-1)\)
4:\(j\gets k-i\)
5:while\(j<k\)and\(v\geq\text{result}[j]\)do
6:\(v\gets v+1\)
7:\(\text{result}[j-1]\leftarrow\text{result}[j]\)
8:\(j\gets j+1\)
9:\(\text{result}[j-1]\gets v\)
10:returnresult
```  
**Algorithm 3** InsertionSample(\(n,k\))  
The composite sampling algorithm of Algorithm 2 runs in \(O(\min(n,k^{2}))\) time and requires \(O(\min(k,n-k))\) random numbers. We integrated this composite sampling algorithm, the new insertion sampling algorithm, as well as our implementations of reservoir sampling and pool sampling into an open source Java library \(\rho\mu\) ([[https://github.com/cicirello/rho-mu](https://github.com/cicirello/rho-mu)]([https://github.com/cicirello/rho-mu](https://github.com/cicirello/rho-mu)), accessed on 26 May 2022), independent of the application to EA of this article.