Detailed mathematical approach

Problem Summary

The implementation studies a Bozo-sort variant on permutations of \(\{1,2,\dots,n\}\). In one step we choose three distinct positions uniformly and then apply a uniformly random permutation to the values in those positions. The sorted permutation is the identity, and the goal is the expected number of steps needed to reach it from a uniformly random starting permutation. For the Project Euler instance the code evaluates this expectation for \(n=11\) and rounds the result to the nearest integer.

Mathematical Approach

A naive Markov chain on all \(n!\) permutations is already huge for \(n=11\). The key reduction in the local C++, Python, and Java solutions is that the transition rule depends only on cycle structure, so the chain can be compressed from individual permutations to conjugacy classes of \(S_n\), equivalently to integer partitions of \(n\).

Step 1: Compress States by Cycle Type

If a permutation has cycle type \(\lambda\), every conjugate permutation has the same cycle type. Write \(\mathcal C_\lambda\) for the conjugacy class corresponding to the partition \(\lambda \vdash n\). The program generates all partitions of \(n\), and for each partition builds one representative permutation consisting of disjoint cycles on consecutive labels.

This compression is valid because the move set is itself invariant under conjugation. If \(\sigma'=\tau \sigma \tau^{-1}\) and \(t\) is a transposition, then

$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$

As \(\tau^{-1} t \tau\) runs through all transpositions again, the multiset of destination cycle types from \(\sigma\) and from \(\sigma'\) is identical. The same argument holds for oriented \(3\)-cycles. Therefore every permutation in the same class has the same transition probabilities between classes.

For \(n=11\), the number of partitions is \(p(11)=56\), so the compressed chain has only \(56\) states instead of \(11! = 39916800\).

Step 2: Decompose One Bozo Step

Fix three positions \(i,j,k\). A uniform random permutation of those three entries has \(3!=6\) possibilities. Relative to the current arrangement, these six permutations split into three types:

$1 \text{ identity},\qquad 3 \text{ transpositions},\qquad 2 \text{ oriented }3\text{-cycles}.$

Hence one Bozo step is equivalent to the mixture

$\Pr(\text{no change})=\frac16,\qquad \Pr(\text{transposition})=\frac12,\qquad \Pr(\text{oriented }3\text{-cycle})=\frac13.$

The code therefore enumerates all transpositions and all oriented \(3\)-cycles separately. Define

$\mathcal T_n=\{(i\ j): 1 \le i \lt j \le n\},\qquad |\mathcal T_n|=\binom{n}{2},$

$\mathcal K_n=\{(i\ j\ k),(i\ k\ j): 1 \le i \lt j \lt k \le n\},\qquad |\mathcal K_n|=2\binom{n}{3}.$

For \(n=11\) this gives \(55\) transpositions and \(330\) oriented \(3\)-cycles per class representative.

Step 3: Transition Probabilities Between Classes

Choose a representative \(\sigma\in \mathcal C_\lambda\). The implementations multiply on the right by every transposition and every oriented \(3\)-cycle, compute the cycle type of the result, and count how often each destination class \(\mu\) appears. This yields the conditional class-to-class probabilities

$P_2(\lambda,\mu)=\frac{\#\{t\in \mathcal T_n:\operatorname{type}(\sigma t)=\mu\}}{\binom{n}{2}},$

$P_3(\lambda,\mu)=\frac{\#\{c\in \mathcal K_n:\operatorname{type}(\sigma c)=\mu\}}{2\binom{n}{3}}.$

Because of the conjugation argument above, these definitions do not depend on which representative of \(\lambda\) is chosen.

Step 4: Linear Equations for Expected Hitting Time

Let \(h_\lambda\) be the expected remaining number of Bozo steps needed to reach the identity class from any permutation of class \(\lambda\). For the identity partition \(1^n\) we have

$h_{1^n}=0.$

For every non-identity class, conditioning on the first step gives

$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$

Rearranging, exactly as in the code,

$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$

There are \(p(n)-1\) unknowns, since the identity state is fixed at zero. For \(n=11\), the matrix dimension is \(55\).

Step 5: Average Over All Permutations

Cycle types occur with different multiplicities, so the final answer is not the simple mean of the \(h_\lambda\). If

$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots,$

then the size of the conjugacy class is

$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$

Therefore the expectation for a uniformly random starting permutation is

$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$

This is the weighted sum computed at the end of all three language implementations.

Worked Example: \(n=4\)

The partitions of \(4\) are \((4)\), \((3,1)\), \((2,2)\), \((2,1,1)\), and \((1,1,1,1)\). The C++ source uses \(n=4\) as a checkpoint and verifies that the average expectation is \(27.5\).

For the class \((2,1,1)\), the code finds

$P_2((2,1,1),(3,1))=\frac46,\quad P_2((2,1,1),(2,2))=\frac16,\quad P_2((2,1,1),(1,1,1,1))=\frac16,$

$P_3((2,1,1),(4))=\frac48=\frac12,\quad P_3((2,1,1),(2,1,1))=\frac48=\frac12.$

Substituting into the expectation equation gives

$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$

Solving the full \(4\times 4\) system yields

$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$

Using class sizes \(6,8,3,6,1\), the overall expectation is

$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$

which matches the checkpoint in the implementation.

How the Code Works

The helper generate_partitions(n) lists all partitions of \(n\). Then build_representative_permutation converts each partition into a concrete permutation with the requested cycle lengths, while cycle_type_partition recovers the sorted cycle lengths after a move. A map from partition to row index lets the program accumulate counts directly in the compressed state space.

For every non-identity class, the program enumerates all \(55\) transpositions and all \(330\) oriented \(3\)-cycles when \(n=11\), fills one row of the augmented linear system, and solves the dense system by Gaussian elimination with partial pivoting. Finally class_size provides the weighting factor \( |\mathcal C_\lambda| \), the weighted mean is formed, and the returned Project Euler answer is the rounded value

$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{answer}=48271207.$

Complexity Analysis

Let \(p(n)\) be the partition number. The compressed state space has \(p(n)\) classes, so only \(p(n)-1\) unknown expectations remain. Building one transition row requires enumerating \(\binom{n}{2}\) transpositions and \(2\binom{n}{3}\) oriented \(3\)-cycles, and each trial recomputes a cycle decomposition of a length-\(n\) permutation. A faithful description of the implementation is therefore roughly

$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$

for transition construction, followed by

$O\!\left((p(n)-1)^3\right)$

for dense Gaussian elimination. Memory usage is \(O(p(n)^2)\) for the augmented matrix plus \(O(p(n)\,n)\) for representatives and metadata. For the actual input \(n=11\), this is completely practical because \(p(11)=56\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=367
2. Symmetric group and conjugacy classes: Wikipedia — Symmetric group
3. Integer partitions: Wikipedia — Partition (number theory)
4. Expected hitting times in Markov chains: Wikipedia — Markov chain
5. Gaussian elimination: Wikipedia — Gaussian elimination