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.
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\).
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\).
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.
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.
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\).
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.
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.
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.$$
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\).
Die Implementierung betrachtet eine Bozo-Sort-Variante auf Permutationen von \(\{1,2,\dots,n\}\). In einem Schritt werden drei verschiedene Positionen gleichverteilt gewählt, und auf die Werte an diesen Positionen wird eine gleichverteilte Permutation angewendet. Der sortierte Zustand ist die Identität, gesucht ist also die erwartete Anzahl von Schritten bis zum Erreichen der Identität aus einer zufälligen Startpermutation. Für die eigentliche Project-Euler-Aufgabe wird dieser Erwartungswert für \(n=11\) berechnet und anschließend gerundet.
Eine direkte Markow-Kette über alle \(n!\) Permutationen wäre schon für \(n=11\) viel zu groß. Die zentrale Reduktion in den lokalen C++-, Python- und Java-Lösungen ist, dass die Übergangsregel nur vom Zykeltyp abhängt. Deshalb kann man statt einzelner Permutationen die Konjugationsklassen von \(S_n\), also die Partitionen von \(n\), als Zustände verwenden.
Hat eine Permutation den Zykeltyp \(\lambda\), so besitzt jede zu ihr konjugierte Permutation denselben Zykeltyp. Sei \(\mathcal C_\lambda\) die zugehörige Konjugationsklasse. Das Programm erzeugt alle Partitionen von \(n\) und baut zu jeder Partition einen Repräsentanten aus disjunkten Zykeln auf aufeinanderfolgenden Labels.
Diese Kompression ist korrekt, weil die Zugmenge selbst unter Konjugation invariant ist. Gilt \(\sigma'=\tau \sigma \tau^{-1}\) und ist \(t\) eine Transposition, dann
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
Wenn \(\tau^{-1} t \tau\) wieder alle Transpositionen durchläuft, dann ist auch die Menge der erreichbaren Ziel-Zykeltypen identisch. Dasselbe Argument gilt für orientierte \(3\)-Zykel. Somit haben alle Permutationen derselben Klasse dieselben Klassenübergänge.
Für \(n=11\) gibt es \(p(11)=56\) Partitionen, also nur \(56\) komprimierte Zustände statt \(11! = 39916800\) Einzelzustände.
Fixiert man drei Positionen \(i,j,k\), dann gibt es \(3!=6\) gleichwahrscheinliche Umordnungen der drei ausgewählten Werte. Relativ zur aktuellen Anordnung zerfallen diese sechs Permutationen in drei Typen:
$$1 \text{ Identität},\qquad 3 \text{ Transpositionen},\qquad 2 \text{ orientierte }3\text{-Zykel}.$$
Ein Bozo-Schritt ist also genau die Mischung
$$\Pr(\text{keine Änderung})=\frac16,\qquad \Pr(\text{Transposition})=\frac12,\qquad \Pr(\text{orientierter }3\text{-Zykel})=\frac13.$$
Darum zählt der Code Transpositionen und orientierte \(3\)-Zykel getrennt. Wir definieren
$$\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}.$$
Für \(n=11\) bedeutet das \(55\) Transpositionen und \(330\) orientierte \(3\)-Zykel pro Klassenrepräsentant.
Sei \(\sigma\in \mathcal C_\lambda\) ein Repräsentant. Die Implementierungen multiplizieren \(\sigma\) rechts mit jeder Transposition und jedem orientierten \(3\)-Zykel, bestimmen den Zykeltyp des Ergebnisses und zählen die Häufigkeiten jeder Zielklasse \(\mu\). So entstehen die bedingten Wahrscheinlichkeiten
$$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}}.$$
Wegen des Konjugationsarguments hängen diese Größen nicht von der konkreten Wahl des Repräsentanten ab.
Sei \(h_\lambda\) die erwartete Restzahl von Bozo-Schritten bis zur Identität, ausgehend von einer Permutation der Klasse \(\lambda\). Für die Identitätspartition \(1^n\) gilt
$$h_{1^n}=0.$$
Für jede Nicht-Identitätsklasse liefert die Fallunterscheidung nach dem ersten Schritt
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$$
Umgestellt erhält man genau die im Code verwendete Form
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
Es bleiben \(p(n)-1\) Unbekannte. Für \(n=11\) ist die Matrix also \(55\times 55\).
Die verschiedenen Zykeltypen treten mit unterschiedlichen Multiplizitäten auf, daher ist die gesuchte Gesamterwartung kein einfacher Mittelwert der \(h_\lambda\). Für
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots$$
ist die Größe der Konjugationsklasse
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$$
Damit folgt für eine gleichverteilte Startpermutation
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$$
Genau diesen gewichteten Mittelwert berechnen die drei Sprachversionen am Ende.
Die Partitionen von \(4\) sind \((4)\), \((3,1)\), \((2,2)\), \((2,1,1)\) und \((1,1,1,1)\). Die C++-Datei benutzt \(n=4\) als Kontrollwert und prüft, dass die mittlere Erwartung \(27.5\) beträgt.
Für die Klasse \((2,1,1)\) findet der Code
$$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.$$
Eingesetzt ergibt das
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$$
Die Lösung des vollständigen \(4\times 4\)-Systems ist
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$$
Mit Klassengrößen \(6,8,3,6,1\) erhält man
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$$
also genau den Checkpoint der Implementierung.
Die Hilfsfunktion generate_partitions(n) erzeugt alle Partitionen von \(n\). Danach baut build_representative_permutation aus jeder Partition eine konkrete Permutation mit den gewünschten Zykluslängen, während cycle_type_partition nach einem Zug wieder die sortierten Zykluslängen bestimmt. Eine Zuordnung von Partition zu Matrixindex erlaubt das direkte Arbeiten im komprimierten Zustandsraum.
Für jede Nicht-Identitätsklasse enumeriert das Programm bei \(n=11\) alle \(55\) Transpositionen und \(330\) orientierten \(3\)-Zykel, füllt damit eine Zeile des augmentierten Gleichungssystems und löst das dichte System per Gauß-Elimination mit partieller Pivotisierung. Anschließend liefert class_size den Faktor \( |\mathcal C_\lambda| \), der gewichtete Mittelwert wird gebildet, und die zurückgegebene Project-Euler-Antwort ist die gerundete Zahl
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{Antwort}=48271207.$$
Sei \(p(n)\) die Partitionszahl. Der komprimierte Zustandsraum hat \(p(n)\) Klassen, also \(p(n)-1\) unbekannte Erwartungswerte. Für eine Übergangszeile müssen \(\binom{n}{2}\) Transpositionen und \(2\binom{n}{3}\) orientierte \(3\)-Zykel ausprobiert werden, und bei jedem Versuch wird die Zykluszerlegung einer Permutation der Länge \(n\) neu bestimmt. Eine realistische Beschreibung der Implementierung ist daher ungefähr
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
für den Aufbau der Übergänge und anschließend
$$O\!\left((p(n)-1)^3\right)$$
für die dichte Gauß-Elimination. Der Speicherbedarf beträgt \(O(p(n)^2)\) für die augmentierte Matrix sowie \(O(p(n)\,n)\) für Repräsentanten und Hilfsdaten. Für den tatsächlichen Fall \(n=11\) ist das problemlos, weil \(p(11)=56\).
Uygulama, \(\{1,2,\dots,n\}\) kümesinin permütasyonları üzerinde bir Bozo-sort çeşidini inceler. Her adımda üç farklı konum eşit olasılıkla seçilir ve bu konumlardaki değerlere rastgele bir permütasyon uygulanır. Sıralı durum özdeşlik permütasyonudur; dolayısıyla amaç, eşit olasılıklı bir başlangıç permütasyonundan özdeşliğe ulaşmak için gereken beklenen adım sayısını bulmaktır. Project Euler örneğinde kod bu beklentiyi \(n=11\) için hesaplar ve en yakın tam sayıya yuvarlar.
Tüm \(n!\) permütasyonlar üzerinde doğrudan bir Markov zinciri kurmak, \(n=11\) için bile gereksiz derecede büyüktür. Yerel C++, Python ve Java çözümlerindeki temel fikir, geçiş kuralının yalnızca döngü tipine bağlı olmasıdır. Böylece durum uzayı, tek tek permütasyonlar yerine \(S_n\) simetrik grubunun eşleniklik sınıflarına, yani \(n\)'nin bölmelerine indirgenir.
Bir permütasyonun döngü tipi \(\lambda\) ise, ona eşlenik her permütasyon aynı döngü tipine sahiptir. \(\lambda \vdash n\) bölmesine karşılık gelen eşleniklik sınıfını \(\mathcal C_\lambda\) ile gösterelim. Program \(n\)'nin bütün bölmelerini üretir ve her bölme için ardışık etiketler üzerinde ayrık döngülerden oluşan bir temsilci permütasyon kurar.
Bu sıkıştırma doğrudur; çünkü hamle kümesi de eşlenime göre değişmez. Eğer \(\sigma'=\tau \sigma \tau^{-1}\) ve \(t\) bir transpozisyon ise,
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
\(\tau^{-1} t \tau\) yine tüm transpozisyonlar üzerinde dolaştığı için, \(\sigma\) ile \(\sigma'\) için ulaşılan hedef döngü tipleri çokkümeleri aynıdır. Aynı argüman yönlü \(3\)-döngüler için de geçerlidir. Böylece aynı sınıftaki tüm permütasyonlar aynı sınıf-geçiş olasılıklarına sahiptir.
\(n=11\) için bölüm sayısı \(p(11)=56\) olduğundan, sıkıştırılmış zincirde \(11! = 39916800\) yerine sadece \(56\) durum vardır.
Üç konum \(i,j,k\) sabitlendiğinde, seçilen üç değerin \(3!=6\) eşit olasılıklı yeniden sıralanışı vardır. Bunlar mevcut düzene göre üç tipe ayrılır:
$$1 \text{ özdeşlik},\qquad 3 \text{ transpozisyon},\qquad 2 \text{ yönlü }3\text{-döngü}.$$
Dolayısıyla bir Bozo adımı şu karışıma eşdeğerdir:
$$\Pr(\text{değişim yok})=\frac16,\qquad \Pr(\text{transpozisyon})=\frac12,\qquad \Pr(\text{yönlü }3\text{-döngü})=\frac13.$$
Bu yüzden kod transpozisyonları ve yönlü \(3\)-döngüleri ayrı ayrı sayar. Şöyle tanımlayalım:
$$\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}.$$
\(n=11\) için bu sayılar sırasıyla \(55\) ve \(330\)'dur.
\(\sigma\in \mathcal C_\lambda\) bir temsilci olsun. Uygulamalar \(\sigma\)'yı sağdan her transpozisyon ve her yönlü \(3\)-döngü ile çarpar, sonucun döngü tipini çıkarır ve her hedef sınıf \(\mu\) için kaç kez ulaşıldığını sayar. Böylece koşullu olasılıklar
$$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}}$$
elde edilir. Eşlenim argümanı sayesinde bunlar seçilen temsilciye bağlı değildir.
\(h_\lambda\), \(\lambda\) sınıfındaki herhangi bir permütasyondan özdeşlik sınıfına ulaşmak için gereken beklenen kalan Bozo adım sayısı olsun. Özdeşlik bölmesi \(1^n\) için
$$h_{1^n}=0$$
vardır. Özdeşlik dışındaki her sınıf için ilk adıma göre koşullandırınca
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu$$
elde edilir. Kodun çözdüğü biçim tam olarak
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
Böylece \(p(n)-1\) bilinmeyenli bir sistem oluşur. \(n=11\) için boyut \(55\)'tir.
Döngü tiplerinin sınıf büyüklükleri farklı olduğundan, son cevap \(h_\lambda\) değerlerinin basit ortalaması değildir. Eğer
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots$$
ise eşleniklik sınıfının büyüklüğü
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}$$
olur. Dolayısıyla eşit olasılıklı başlangıç permütasyonu için beklenen değer
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda$$
şeklindedir. Üç çözüm dosyasının sonunda hesaplanan ağırlıklı toplam budur.
\(4\)'ün bölmeleri \((4)\), \((3,1)\), \((2,2)\), \((2,1,1)\) ve \((1,1,1,1)\)'dir. C++ kaynağı, kontrol noktası olarak \(n=4\) için ortalama beklentinin \(27.5\) olduğunu doğrular.
\((2,1,1)\) sınıfı için kod
$$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$$
değerlerini bulur. Bunları yerine yazınca
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1$$
çıkar. Tüm \(4\times 4\) sistem çözüldüğünde
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27$$
elde edilir. Sınıf büyüklükleri \(6,8,3,6,1\) olduğundan
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5$$
olur ve bu, implementasyondaki checkpoint ile tam uyumludur.
generate_partitions(n) fonksiyonu \(n\)'nin bütün bölmelerini üretir. Sonra build_representative_permutation her bölmeyi istenen döngü uzunluklarına sahip somut bir permütasyona çevirir; cycle_type_partition ise bir hamleden sonra oluşan döngü uzunluklarını tekrar sıralı biçimde çıkarır. Bölmeden matris indeksine giden sözlük sayesinde program sıkıştırılmış durum uzayında doğrudan çalışır.
Her özdeşlik dışı sınıf için program \(n=11\) durumunda bütün \(55\) transpozisyonu ve \(330\) yönlü \(3\)-döngüyü dener, genişletilmiş doğrusal sistemin bir satırını doldurur ve yoğun sistemi kısmi pivotlamalı Gauss elemesi ile çözer. Son aşamada class_size fonksiyonu \( |\mathcal C_\lambda| \) katsayısını verir, ağırlıklı ortalama alınır ve dönen Project Euler cevabı
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{cevap}=48271207$$
olur.
\(p(n)\) bölüm sayısı olsun. Sıkıştırılmış durum uzayında \(p(n)\) sınıf ve \(p(n)-1\) bilinmeyenli beklenen süre vardır. Bir geçiş satırını kurmak için \(\binom{n}{2}\) transpozisyon ve \(2\binom{n}{3}\) yönlü \(3\)-döngü denenir; her denemede uzunluğu \(n\) olan bir permütasyonun döngü ayrışımı yeniden hesaplanır. Bu nedenle uygulamanın sadık bir karmaşıklık özeti yaklaşık olarak
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
geçiş inşası ve ardından
$$O\!\left((p(n)-1)^3\right)$$
yoğun Gauss elemesi şeklindedir. Bellek kullanımı, genişletilmiş matris için \(O(p(n)^2)\), temsilciler ve yardımcı yapılar için \(O(p(n)\,n)\)'dir. Gerçek girişte \(p(11)=56\) olduğu için yöntem tamamen uygulanabilirdir.
La implementación estudia una variante de Bozo sort sobre permutaciones de \(\{1,2,\dots,n\}\). En cada paso se eligen uniformemente tres posiciones distintas y luego se aplica una permutación uniforme a los valores ubicados en esas posiciones. El estado ordenado es la identidad, así que debemos hallar el número esperado de pasos para llegar a ella desde una permutación inicial uniforme. Para el caso de Project Euler, el código evalúa esa esperanza cuando \(n=11\) y redondea el resultado al entero más cercano.
Una cadena de Markov directa sobre las \(n!\) permutaciones sería demasiado grande incluso para \(n=11\). La reducción decisiva en las soluciones locales de C++, Python y Java es que la regla de transición depende solo de la estructura cíclica. Por eso la cadena se comprime desde permutaciones individuales hasta clases de conjugación de \(S_n\), o de forma equivalente, hasta particiones enteras de \(n\).
Si una permutación tiene tipo de ciclo \(\lambda\), toda permutación conjugada tiene el mismo tipo. Denotemos por \(\mathcal C_\lambda\) la clase de conjugación asociada a la partición \(\lambda \vdash n\). El programa genera todas las particiones de \(n\) y construye, para cada una, un representante formado por ciclos disjuntos sobre etiquetas consecutivas.
La compresión es válida porque el conjunto de movimientos también es invariante por conjugación. Si \(\sigma'=\tau \sigma \tau^{-1}\) y \(t\) es una transposición, entonces
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
Como \(\tau^{-1} t \tau\) vuelve a recorrer todas las transposiciones, el multiconjunto de tipos de ciclo alcanzables desde \(\sigma\) y desde \(\sigma'\) coincide. El mismo razonamiento vale para los \(3\)-ciclos orientados. En consecuencia, todas las permutaciones dentro de la misma clase tienen las mismas probabilidades de transición entre clases.
Cuando \(n=11\), el número de particiones es \(p(11)=56\), así que la cadena comprimida tiene solo \(56\) estados en lugar de \(11! = 39916800\).
Fijadas tres posiciones \(i,j,k\), hay \(3!=6\) reordenamientos equiprobables de los tres valores seleccionados. Respecto al estado actual, esas seis permutaciones se dividen en tres tipos:
$$1 \text{ identidad},\qquad 3 \text{ transposiciones},\qquad 2 \text{ }3\text{-ciclos orientados}.$$
Por lo tanto, un paso de Bozo equivale a la mezcla
$$\Pr(\text{sin cambio})=\frac16,\qquad \Pr(\text{transposición})=\frac12,\qquad \Pr(\text{ }3\text{-ciclo orientado})=\frac13.$$
Por eso el código enumera por separado todas las transposiciones y todos los \(3\)-ciclos orientados. Definimos
$$\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}.$$
Para \(n=11\), esto significa \(55\) transposiciones y \(330\) \(3\)-ciclos orientados por representante de clase.
Tomemos un representante \(\sigma\in \mathcal C_\lambda\). Las implementaciones multiplican a la derecha por cada transposición y por cada \(3\)-ciclo orientado, calculan el tipo de ciclo del resultado y cuentan cuántas veces aparece cada clase destino \(\mu\). Así se obtienen las probabilidades condicionales
$$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}}.$$
Gracias a la invariancia por conjugación, estas cantidades no dependen del representante elegido.
Sea \(h_\lambda\) el número esperado de pasos restantes para alcanzar la clase identidad desde cualquier permutación de clase \(\lambda\). Para la partición identidad \(1^n\) se cumple
$$h_{1^n}=0.$$
Condicionando por el primer paso, para cada clase no identidad se obtiene
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$$
Reordenando, exactamente como en el código,
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
Así quedan \(p(n)-1\) incógnitas. Para \(n=11\), la matriz tiene dimensión \(55\).
Los tipos de ciclo no aparecen con la misma multiplicidad, así que la respuesta final no es la media simple de los \(h_\lambda\). Si
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots,$$
entonces el tamaño de la clase de conjugación es
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$$
Por consiguiente, la esperanza para una permutación inicial uniforme es
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$$
Ese es exactamente el promedio ponderado calculado al final de las tres implementaciones.
Las particiones de \(4\) son \((4)\), \((3,1)\), \((2,2)\), \((2,1,1)\) y \((1,1,1,1)\). El archivo en C++ usa \(n=4\) como punto de control y verifica que la esperanza media vale \(27.5\).
Para la clase \((2,1,1)\), el código obtiene
$$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.$$
Al sustituir se obtiene
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$$
La solución del sistema completo \(4\times 4\) es
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$$
Usando tamaños de clase \(6,8,3,6,1\), la esperanza global resulta
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$$
en perfecto acuerdo con la comprobación de la implementación.
La función generate_partitions(n) lista todas las particiones de \(n\). Luego build_representative_permutation transforma cada partición en una permutación concreta con esas longitudes de ciclo, mientras que cycle_type_partition recupera las longitudes ordenadas después de aplicar un movimiento. Un mapa de partición a índice de fila permite acumular los conteos directamente en el espacio de estados comprimido.
Para cada clase distinta de la identidad, el programa enumera los \(55\) intercambios y los \(330\) \(3\)-ciclos orientados cuando \(n=11\), llena una fila del sistema lineal aumentado y resuelve el sistema denso mediante eliminación gaussiana con pivoteo parcial. Después class_size proporciona el peso \( |\mathcal C_\lambda| \), se forma el promedio ponderado y la respuesta devuelta para Project Euler es el valor redondeado
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{respuesta}=48271207.$$
Sea \(p(n)\) la función de particiones. El espacio de estados comprimido tiene \(p(n)\) clases, por lo que solo quedan \(p(n)-1\) esperanzas desconocidas. Construir una fila de transición requiere enumerar \(\binom{n}{2}\) transposiciones y \(2\binom{n}{3}\) \(3\)-ciclos orientados, y en cada intento se vuelve a calcular la descomposición en ciclos de una permutación de longitud \(n\). Una descripción fiel de la implementación es, por tanto, aproximadamente
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
para construir las transiciones, seguida de
$$O\!\left((p(n)-1)^3\right)$$
para la eliminación gaussiana densa. El uso de memoria es \(O(p(n)^2)\) para la matriz aumentada y \(O(p(n)\,n)\) para representantes y metadatos. En la entrada real, \(p(11)=56\), así que el método es completamente viable.
本实现研究的是 \(\{1,2,\dots,n\}\) 上排列的一种 Bozo 排序变体。每一步都等概率选取三个不同位置，然后对这三个位置上的值施加一个等概率的排列。排好序的状态就是恒等排列，因此目标是求从均匀随机初始排列出发，到达恒等排列所需步数的期望。对 Project Euler 的实际输入，程序计算 \(n=11\) 时的该期望，并把结果四舍五入到最近整数。
若直接在全部 \(n!\) 个排列上建立马尔可夫链，那么 \(n=11\) 时状态数已经过大。局部的 C++、Python 和 Java 解法都利用了同一个关键事实：转移规则只依赖于排列的循环结构。因此可以把状态从具体排列压缩到 \(S_n\) 的共轭类，也就是 \(n\) 的整数分拆。
若一个排列的循环类型是 \(\lambda\)，那么所有与它共轭的排列都有同样的循环类型。记对应的共轭类为 \(\mathcal C_\lambda\)，其中 \(\lambda \vdash n\)。程序先生成 \(n\) 的全部分拆，再为每个分拆构造一个代表元，这个代表元由连续编号上的若干互不相交循环组成。
这种压缩之所以成立，是因为操作集合本身在共轭下不变。若 \(\sigma'=\tau \sigma \tau^{-1}\)，且 \(t\) 是一个换位，那么
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
由于 \(\tau^{-1} t \tau\) 仍然遍历全部换位，因此从 \(\sigma\) 和从 \(\sigma'\) 出发得到的目标循环类型多重集完全相同。对有向 \(3\)-循环也同理。于是，同一共轭类中的任意排列都具有相同的类间转移概率。
当 \(n=11\) 时，分拆数 \(p(11)=56\)，所以压缩后的链只有 \(56\) 个状态，而不是 \(11! = 39916800\) 个状态。
固定三个位置 \(i,j,k\) 后，这三个值的重排共有 \(3!=6\) 种等概率情况。相对于当前排列，这六种情况可分成三类：
$$1 \text{ 个恒等},\qquad 3 \text{ 个换位},\qquad 2 \text{ 个有向 }3\text{-循环}.$$
因此一次 Bozo 操作等价于下面的混合过程：
$$\Pr(\text{不变})=\frac16,\qquad \Pr(\text{换位})=\frac12,\qquad \Pr(\text{有向 }3\text{-循环})=\frac13.$$
这正是代码分别枚举换位与有向 \(3\)-循环的原因。定义
$$\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}.$$
对 \(n=11\) 而言，每个类代表元要检查 \(55\) 个换位和 \(330\) 个有向 \(3\)-循环。
取一个代表元 \(\sigma\in \mathcal C_\lambda\)。程序把 \(\sigma\) 分别右乘每个换位和每个有向 \(3\)-循环，计算结果的循环类型，并统计落入每个目标类 \(\mu\) 的次数。于是得到条件概率
$$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}}.$$
由上面的共轭不变性可知，这两个定义与代表元的具体选取无关。
设 \(h_\lambda\) 表示从类 \(\lambda\) 中任意排列出发，到达恒等类所需剩余 Bozo 步数的期望。对恒等分拆 \(1^n\)，有
$$h_{1^n}=0.$$
对每个非恒等类，按第一步分类讨论得到
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$$
整理后，正好得到代码中构造的方程
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
未知量个数是 \(p(n)-1\)。在 \(n=11\) 时，矩阵维度为 \(55\)。
不同循环类型出现的次数不同，因此最终答案不是简单地对 \(h_\lambda\) 求平均。若
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots,$$
则对应共轭类的大小为
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$$
于是，均匀随机起始排列的期望为
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$$
这就是三个实现最终计算的加权和。
\(4\) 的分拆为 \((4)\)、\((3,1)\)、\((2,2)\)、\((2,1,1)\)、\((1,1,1,1)\)。C++ 源码把 \(n=4\) 作为检查点，并验证平均期望为 \(27.5\)。
对于类 \((2,1,1)\)，代码统计得到
$$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.$$
代入方程可得
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$$
解整个 \(4\times 4\) 线性系统后得到
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$$
再结合类大小 \(6,8,3,6,1\)，总体期望为
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$$
与实现中的检查结果完全一致。
generate_partitions(n) 负责生成全部整数分拆。随后 build_representative_permutation 把每个分拆转换成具有相应循环长度的具体排列，而 cycle_type_partition 在施加一次操作后重新提取并排序循环长度。分拆到矩阵行号的映射使程序能够直接在压缩状态空间中累计计数。
对每个非恒等类，当 \(n=11\) 时程序都要枚举 \(55\) 个换位与 \(330\) 个有向 \(3\)-循环，填充增广线性系统的一行，再用带部分主元的高斯消元求解。最后 class_size 给出权重 \( |\mathcal C_\lambda| \)，程序形成加权平均，并返回四舍五入后的 Project Euler 答案
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{答案}=48271207.$$
设 \(p(n)\) 为分拆数。压缩后的状态数为 \(p(n)\)，未知期望值有 \(p(n)-1\) 个。构造一行转移时，需要枚举 \(\binom{n}{2}\) 个换位与 \(2\binom{n}{3}\) 个有向 \(3\)-循环，并且每次都重新计算一个长度为 \(n\) 的排列的循环分解。因此，对该实现的忠实复杂度描述大致是
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
用于构造转移，再加上
$$O\!\left((p(n)-1)^3\right)$$
用于稠密高斯消元。内存方面，增广矩阵需要 \(O(p(n)^2)\)，代表元和辅助信息需要 \(O(p(n)\,n)\)。对实际输入 \(n=11\) 来说，\(p(11)=56\)，所以该方法完全可行。
В реализации рассматривается вариант Bozo sort на перестановках множества \(\{1,2,\dots,n\}\). За один шаг равновероятно выбираются три различные позиции, после чего к значениям в этих позициях применяется равновероятная перестановка. Отсортированное состояние совпадает с тождественной перестановкой, поэтому нужно найти математическое ожидание числа шагов до попадания в неё из равномерно случайной начальной перестановки. Для задачи Project Euler программа вычисляет это ожидание при \(n=11\) и округляет результат до ближайшего целого.
Если строить цепь Маркова по всем \(n!\) перестановкам, то уже при \(n=11\) пространство состояний будет чрезмерно большим. Ключевая идея локальных решений на C++, Python и Java состоит в том, что правило перехода зависит только от циклического типа. Поэтому цепь можно сжать от отдельных перестановок до классов сопряжённости группы \(S_n\), то есть до разбиений числа \(n\).
Если перестановка имеет циклический тип \(\lambda\), то любая сопряжённая ей перестановка имеет тот же тип. Обозначим через \(\mathcal C_\lambda\) класс сопряжённости, соответствующий разбиению \(\lambda \vdash n\). Программа генерирует все разбиения числа \(n\) и для каждого строит представителя в виде набора непересекающихся циклов на последовательных метках.
Такое сжатие корректно, потому что множество ходов само инвариантно относительно сопряжения. Если \(\sigma'=\tau \sigma \tau^{-1}\) и \(t\) является транспозицией, то
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
Поскольку \(\tau^{-1} t \tau\) снова пробегает все транспозиции, мультимножество достижимых циклических типов из \(\sigma\) и из \(\sigma'\) совпадает. Тот же довод верен и для ориентированных \(3\)-циклов. Значит, у всех перестановок одного класса одинаковые вероятности переходов между классами.
При \(n=11\) число разбиений равно \(p(11)=56\), так что после сжатия остаётся всего \(56\) состояний вместо \(11! = 39916800\).
Зафиксируем три позиции \(i,j,k\). Существует \(3!=6\) равновероятных перестановок трёх выбранных значений. Относительно текущего состояния эти шесть вариантов делятся на три типа:
$$1 \text{ тождественная},\qquad 3 \text{ транспозиции},\qquad 2 \text{ ориентированных }3\text{-цикла}.$$
Следовательно, один шаг Bozo эквивалентен смеси
$$\Pr(\text{без изменения})=\frac16,\qquad \Pr(\text{транспозиция})=\frac12,\qquad \Pr(\text{ориентированный }3\text{-цикл})=\frac13.$$
Именно поэтому код отдельно перебирает все транспозиции и все ориентированные \(3\)-циклы. Обозначим
$$\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}.$$
Для \(n=11\) это даёт \(55\) транспозиций и \(330\) ориентированных \(3\)-циклов на одного представителя класса.
Выберем представителя \(\sigma\in \mathcal C_\lambda\). Реализации домножают \(\sigma\) справа на каждую транспозицию и каждый ориентированный \(3\)-цикл, вычисляют циклический тип результата и подсчитывают, как часто возникает каждый класс \(\mu\). Получаются условные вероятности
$$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}}.$$
Из инвариантности относительно сопряжения следует, что эти величины не зависят от выбора представителя.
Пусть \(h_\lambda\) обозначает ожидаемое число оставшихся шагов Bozo до попадания в класс тождества, если стартовать из любой перестановки класса \(\lambda\). Для разбиения \(1^n\) имеем
$$h_{1^n}=0.$$
Для любого нетождественного класса условие по первому шагу даёт
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$$
После переноса членов получаем в точности ту форму, которую собирает код:
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
Неизвестных \(p(n)-1\), а при \(n=11\) размер матрицы равен \(55\).
Разные циклические типы встречаются с разной кратностью, поэтому итоговый ответ не равен простому среднему значений \(h_\lambda\). Если
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots,$$
то размер класса сопряжённости равен
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$$
Следовательно, для равномерно случайной начальной перестановки
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$$
Именно эту взвешенную сумму в конце вычисляют все три реализации.
Разбиения числа \(4\): \((4)\), \((3,1)\), \((2,2)\), \((2,1,1)\), \((1,1,1,1)\). Файл на C++ использует случай \(n=4\) как проверку и подтверждает, что среднее ожидание равно \(27.5\).
Для класса \((2,1,1)\) код находит
$$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.$$
Подстановка даёт уравнение
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$$
Решая всю систему \(4\times 4\), получаем
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$$
С учётом размеров классов \(6,8,3,6,1\) имеем
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$$
что полностью совпадает с проверкой в реализации.
Функция generate_partitions(n) перечисляет все разбиения числа \(n\). Затем build_representative_permutation превращает каждое разбиение в конкретную перестановку с нужными длинами циклов, а cycle_type_partition после хода восстанавливает и сортирует длины циклов. Отображение «разбиение \(\to\) индекс строки» позволяет сразу накапливать счётчики в сжатом пространстве состояний.
Для каждого нетождественного класса программа при \(n=11\) перебирает все \(55\) транспозиций и \(330\) ориентированных \(3\)-циклов, заполняет одну строку расширенной линейной системы и решает плотную систему методом Гаусса с частичным выбором главного элемента. После этого class_size даёт вес \( |\mathcal C_\lambda| \), формируется взвешенное среднее, и итоговый ответ Project Euler равен
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{ответ}=48271207.$$
Пусть \(p(n)\) обозначает число разбиений. Сжатое пространство содержит \(p(n)\) классов, значит неизвестных ожиданий \(p(n)-1\). Для построения одной строки переходов нужно перебрать \(\binom{n}{2}\) транспозиций и \(2\binom{n}{3}\) ориентированных \(3\)-цикла, причём после каждого хода заново вычисляется циклическое разложение перестановки длины \(n\). Поэтому точное описание сложности реализации имеет вид
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
на построение переходов и затем
$$O\!\left((p(n)-1)^3\right)$$
на решение плотной СЛАУ методом Гаусса. Память составляет \(O(p(n)^2)\) для расширенной матрицы и \(O(p(n)\,n)\) для представителей и служебных структур. Для реального случая \(n=11\) это очень мало, поскольку \(p(11)=56\).
تدرس هذه التنفيذات نسخة من Bozo sort على تبديلات المجموعة \(\{1,2,\dots,n\}\). في كل خطوة نختار ثلاث مواضع مختلفة باحتمال متساوٍ، ثم نطبق تبديلًا عشوائيًا منتظمًا على القيم الموجودة في تلك المواضع. الحالة المرتبة هي التبديل المحايد، ولذلك نريد حساب العدد المتوقع من الخطوات اللازمة للوصول إليه من تبديل ابتدائي عشوائي منتظم. في حالة Project Euler يحسب البرنامج هذا التوقع عند \(n=11\) ثم يقرّبه إلى أقرب عدد صحيح.
إن بناء سلسلة ماركوف مباشرة على جميع التبديلات وعددها \(n!\) غير عملي حتى عندما \(n=11\). الفكرة الأساسية في حلول C++ وPython وJava المحلية هي أن قاعدة الانتقال لا تعتمد إلا على بنية الدورات. لذلك يمكن ضغط فضاء الحالات من التبديلات الفردية إلى أصناف الاقتران في \(S_n\)، أي إلى تقسيمات العدد \(n\).
إذا كان للتبديل نوع دورات \(\lambda\)، فإن كل تبديل مقترن به يملك النوع نفسه. نرمز إلى صنف الاقتران الموافق للتقسيم \(\lambda \vdash n\) بالرمز \(\mathcal C_\lambda\). يولد البرنامج جميع تقسيمات \(n\)، ثم يبني لكل تقسيم ممثلًا على شكل دورات منفصلة فوق تسميات متتالية.
هذا الضغط صحيح لأن مجموعة الحركات نفسها ثابتة تحت الاقتران. فإذا كان \(\sigma'=\tau \sigma \tau^{-1}\) و\(t\) تبديلًا ثنائيًا، فإن
$$\sigma' t = \tau \sigma (\tau^{-1} t \tau)\tau^{-1}.$$
وبما أن \(\tau^{-1} t \tau\) يمر من جديد على جميع التبديلات الثنائية، فإن متعدد مجموعة أنواع الدورات الناتجة من \(\sigma\) يساوي ذلك الناتج من \(\sigma'\). والحجة نفسها تنطبق على الدورات الثلاثية الموجّهة. إذن كل تبديلين في الصنف نفسه يملكان احتمالات انتقال متماثلة بين الأصناف.
عند \(n=11\) يكون عدد التقسيمات \(p(11)=56\)، ولذلك لا تبقى إلا \(56\) حالة مضغوطة بدلًا من \(11! = 39916800\).
إذا ثبتنا ثلاثة مواضع \(i,j,k\)، فهناك \(3!=6\) إعادة ترتيبات متساوية الاحتمال للقيم الثلاث المختارة. بالنسبة إلى الترتيب الحالي تنقسم هذه الحالات الست إلى ثلاثة أنواع:
$$1 \text{ identity},\qquad 3 \text{ transpositions},\qquad 2 \text{ oriented }3\text{-cycles}.$$
إذًا يمكن تمثيل خطوة Bozo بالمزيج التالي:
$$\Pr(\text{no-op})=\frac16,\qquad \Pr(\text{transposition})=\frac12,\qquad \Pr(\text{oriented }3\text{-cycle})=\frac13.$$
لهذا السبب يعدّ الكود جميع التبديلات الثنائية وجميع الدورات الثلاثية الموجّهة على حدة. نعرّف
$$\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}.$$
وعندما \(n=11\) يكون لدينا \(55\) تبديلًا ثنائيًا و\(330\) دورة ثلاثية موجّهة لكل ممثل صنف.
خذ ممثلًا \(\sigma\in \mathcal C_\lambda\). تقوم التنفيذات بضرب \(\sigma\) من اليمين بكل تبديل ثنائي وبكل دورة ثلاثية موجّهة، ثم تحسب نوع الدورات الناتج وتحصي مرات الوصول إلى كل صنف هدف \(\mu\). وبهذا نحصل على الاحتمالين الشرطيين
$$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}}.$$
وبفضل ثبات المسألة تحت الاقتران فإن هاتين الكميتين لا تعتمدان على اختيار الممثل نفسه.
ليكن \(h_\lambda\) هو العدد المتوقع للخطوات المتبقية للوصول إلى صنف الهوية عند البدء من أي تبديل في الصنف \(\lambda\). بالنسبة إلى تقسيم الهوية \(1^n\) لدينا
$$h_{1^n}=0.$$
أما لكل صنف غير الهوية، فبالتكييف على الخطوة الأولى نحصل على
$$h_\lambda=1+\frac16 h_\lambda+\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu+\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu.$$
وبإعادة الترتيب نحصل تمامًا على النظام الذي يبنيه الكود:
$$\boxed{\frac56 h_\lambda-\frac12 \sum_{\mu} P_2(\lambda,\mu)h_\mu-\frac13 \sum_{\mu} P_3(\lambda,\mu)h_\mu=1.}$$
إذن عدد المجاهيل هو \(p(n)-1\)، وعندما \(n=11\) يكون بُعد المصفوفة \(55\).
أنواع الدورات لا تظهر بالتعدد نفسه، ولذلك فالإجابة النهائية ليست المتوسط البسيط لقيم \(h_\lambda\). إذا كتبنا
$$\lambda = 1^{m_1}2^{m_2}3^{m_3}\cdots,$$
فإن حجم صنف الاقتران هو
$$|\mathcal C_\lambda|=\frac{n!}{\prod_{\ell \ge 1}\ell^{m_\ell} m_\ell!}.$$
ومن ثم يكون التوقع عند اختيار تبديل ابتدائي منتظمًا هو
$$\mathbb E[T_n]=\frac{1}{n!}\sum_{\lambda \vdash n} |\mathcal C_\lambda|\,h_\lambda.$$
وهذا هو بالضبط المتوسط الموزون الذي تحسبه الملفات الثلاثة في النهاية.
تقسيمات العدد \(4\) هي \((4)\) و\((3,1)\) و\((2,2)\) و\((2,1,1)\) و\((1,1,1,1)\). يستخدم ملف C++ الحالة \(n=4\) كنقطة تحقق، ويؤكد أن متوسط التوقع يساوي \(27.5\).
بالنسبة إلى الصنف \((2,1,1)\)، يجد الكود أن
$$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.$$
وبالتعويض نحصل على
$$\frac23 h_{(2,1,1)}-\frac13 h_{(3,1)}-\frac1{12} h_{(2,2)}-\frac16 h_{(4)}=1.$$
وحل النظام الكامل \(4\times 4\) يعطي
$$h_{(4)}=30,\qquad h_{(3,1)}=28.5,\qquad h_{(2,2)}=30,\qquad h_{(2,1,1)}=27.$$
وباستخدام أحجام الأصناف \(6,8,3,6,1\) نجد
$$\mathbb E[T_4]=\frac{6\cdot 30+8\cdot 28.5+3\cdot 30+6\cdot 27}{24}=27.5,$$
وهو نفس مقدار نقطة التحقق الموجودة في التنفيذ.
الدالة generate_partitions(n) تعدد جميع تقسيمات العدد \(n\). بعد ذلك تقوم build_representative_permutation بتحويل كل تقسيم إلى تبديل فعلي يملك أطوال الدورات المطلوبة، بينما تستخرج cycle_type_partition أطوال الدورات المرتبة بعد تنفيذ الحركة. كما تسمح خريطة من التقسيم إلى رقم الصف بالعمل مباشرة داخل فضاء الحالات المضغوط.
لكل صنف غير الهوية، يجرّب البرنامج عند \(n=11\) جميع التبديلات الثنائية وعددها \(55\) وجميع الدورات الثلاثية الموجّهة وعددها \(330\)، ثم يملأ صفًا واحدًا من النظام الخطي الموسع ويحل النظام الكثيف بالحذف الغاوسي مع اختيار محوري جزئي. بعد ذلك توفّر class_size الوزن \( |\mathcal C_\lambda| \)، ويؤخذ المتوسط الموزون، وتكون إجابة Project Euler النهائية هي
$$\mathbb E[T_{11}] \approx 48271206.59545692,\qquad \text{answer}=48271207.$$
ليكن \(p(n)\) عدد تقسيمات \(n\). يحتوي فضاء الحالات المضغوط على \(p(n)\) أصناف، وبالتالي يوجد \(p(n)-1\) زمنًا متوقعًا مجهولًا. يتطلب بناء صف انتقال واحد تعداد \(\binom{n}{2}\) تبديلًا ثنائيًا و\(2\binom{n}{3}\) دورة ثلاثية موجّهة، ومع كل تجربة يعاد حساب تفكيك الدورات لتبديل طوله \(n\). لذا فإن وصفًا دقيقًا لتعقيد التنفيذ هو تقريبًا
$$O\!\left(p(n)\left(\binom{n}{2}+2\binom{n}{3}\right)n\right)$$
لبناء الانتقالات، يتبعه
$$O\!\left((p(n)-1)^3\right)$$
لحل النظام الخطي الكثيف. أما الذاكرة فهي \(O(p(n)^2)\) للمصفوفة الموسعة و\(O(p(n)\,n)\) للممثلين والبيانات المساعدة. وفي الإدخال الفعلي \(n=11\) يكون \(p(11)=56\)، لذا فهذه الكلفة عملية جدًا.