We have a train of \(n\) distinct carriages labelled \(A,B,C,\dots\). Simon sorts it using only suffix reversals: at stage \(i\) (using 0-based indexing, as in the code), he takes the next required letter in sorted order, moves it to the tail if necessary, and then reverses the suffix starting at \(i\) so that this letter lands permanently at position \(i\). A starting permutation is called maximix if Simon is forced to use the largest possible total number of moves. For Project Euler 336, the task is to list all maximix arrangements for \(n=11\), sort them lexicographically, and select the requested rank without hard-coding the answer.
Let \(R_i\) denote the operation “reverse the suffix beginning at index \(i\)”. Because a reversal is an involution, \(R_i^{-1}=R_i\); this observation is what makes it possible to construct all maximix states backwards instead of testing every permutation forwards.
Fix a stage \(i\in\{0,\dots,n-2\}\). The target symbol is the \(i\)-th symbol of the sorted word \(A_1A_2\cdots A_n\). If that symbol is already at index \(i\), Simon does nothing. Otherwise, if it is at an interior position \(p\in\{i+1,\dots,n-2\}\), Simon first applies \(R_p\) to move it to the tail, and then applies \(R_i\) to bring it from the tail back to index \(i\). If it is already at the tail \(n-1\), only the second reversal \(R_i\) is needed.
So the move count at stage \(i\) is
$$m_i=\begin{cases} 0, & \text{if the target is already at } i,\\ 1, & \text{if the target is at } n-1,\\ 2, & \text{if the target is at some } p\in\{i+1,\dots,n-2\}. \end{cases}$$
For stages \(i=0,1,\dots,n-3\), Simon can spend at most two moves. At the final nontrivial stage \(i=n-2\), only two letters remain, so the target can be either already correct (0 moves) or at the tail (1 move); two moves are impossible there.
Therefore the global maximum is
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
A permutation is maximix exactly when every early stage \(i\le n-3\) forces the two-move case, and the last stage \(i=n-2\) forces the one-move case.
This gives a precise local condition. Just before stage \(i\le n-3\), the target letter must lie strictly inside the active suffix, not at its left boundary and not at its right boundary. In other words, its position must belong to \(\{i+1,\dots,n-2\}\). For the last stage, the smaller of the final two remaining letters must be sitting at position \(n-1\), so that a last reversal \(R_{n-2}\) is still required.
That description is much stronger than “takes many moves”: it tells us exactly which predecessors are allowed at each stage, which is why a constructive enumeration becomes possible.
Let \(w^\star = A_1A_2\cdots A_n\) be the fully sorted word. Any maximix arrangement must end at \(w^\star\) after Simon finishes. Since each reversal is its own inverse, we can reconstruct all valid predecessors.
The final stage is forced: to need one move at \(i=n-2\), the state immediately before the last move must be
$$w_{n-2}=R_{n-2}(w^\star).$$
Now suppose we already know an after-state for stage \(i\), with positions \(0,\dots,i\) fixed correctly. In the forward direction, a two-move stage must have been \(R_p\) followed by \(R_i\), where \(p\in\{i+1,\dots,n-2\}\). Reversing that step gives
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
Each admissible \(p\) yields one branch, and no value \(p=n-1\) is allowed, because that would correspond to the one-move case rather than the required two-move case.
At stage \(i\), there are exactly \(n-i-2\) admissible choices for \(p\). Hence the total number of choice sequences is
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$$
This is not merely an upper bound. Simon's forward run determines the actual position \(p\) uniquely at each stage, so every maximix arrangement corresponds to exactly one branch sequence \((p_0,p_1,\dots,p_{n-3})\), and every such sequence reconstructs exactly one maximix arrangement. Therefore
$$|\mathcal{M}_n|=(n-2)!.$$
For \(n=11\), this means there are \(9! = 362{,}880\) maximix arrangements, which is small enough to generate explicitly.
The sorted word is \(ABCD\). First invert the forced last move:
$$ABCD \xrightarrow{R_2} ABDC.$$
For stage \(i=1\), the only possible choice is \(p=2\):
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
For stage \(i=0\), we first apply \(R_0\):
$$ACBD \xrightarrow{R_0} DBCA.$$
Then there are two valid branches:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
So the complete maximix set for \(n=4\) is \(\{DACB, DBAC\}\), and indeed its size is \((4-2)! = 2\). This is the same checkpoint used by the C++ implementation.
The helper reverse_suffix implements \(R_i\). The generator starts from the sorted string ABC..., applies the inverse last move R(n-2), and then iterates \(i\) from \(n-3\) down to 0. For every current after state it first computes R(i), then branches over all valid \(p\in[i+1,n-2]\) by applying R(p). The resulting list of states is exactly the maximix set.
After generation, the states are sorted lexicographically. Because the containers are zero-indexed, the code reads index 2010 to obtain the 2011th maximix arrangement for \(n=11\). The C++ version also validates the construction on the known \(n=4\) and \(n=6\) checkpoints before producing the final ranked string; the Python and Java versions keep the same core generator with less scaffolding.
The generator produces exactly \((n-2)!\) final states. Each branch performs suffix reversals on strings of length \(n\), so generation costs \(O((n-2)!\cdot n)\). The final lexicographic sort costs \(O((n-2)!\log((n-2)!)\cdot n)\) when string-comparison length is taken into account. Memory usage is \(O((n-2)!\cdot n)\), since the algorithm stores the full state list. For the fixed input \(n=11\), these bounds are entirely practical.
Wir betrachten einen Zug aus \(n\) verschiedenen Wagen mit den Bezeichnungen \(A,B,C,\dots\). Simon sortiert ihn ausschließlich durch Suffix-Umkehrungen: In Stufe \(i\) (mit 0-basierter Indizierung wie im Code) nimmt er den als Nächstes benötigten Buchstaben der sortierten Reihenfolge, bringt ihn bei Bedarf ans Ende und kehrt dann das Suffix ab \(i\) um, sodass dieser Buchstabe dauerhaft auf Position \(i\) landet. Eine Startpermutation heißt maximix, wenn Simon zur größtmöglichen Gesamtzahl von Zügen gezwungen wird. In Project Euler 336 sollen für \(n=11\) alle maximix-Anordnungen erzeugt, lexikographisch sortiert und der geforderte Rang ausgewählt werden, ohne die Antwort fest einzubauen.
Sei \(R_i\) die Operation „kehre das Suffix ab Index \(i\) um“. Da eine Umkehrung eine Involution ist, gilt \(R_i^{-1}=R_i\). Genau diese Eigenschaft erlaubt es, alle maximix-Zustände rückwärts zu konstruieren, statt jede Permutation vorwärts zu testen.
Betrachte eine Stufe \(i\in\{0,\dots,n-2\}\). Das Zielsymbol ist das \(i\)-te Symbol des sortierten Wortes \(A_1A_2\cdots A_n\). Befindet es sich bereits an Index \(i\), passiert nichts. Liegt es an einer inneren Position \(p\in\{i+1,\dots,n-2\}\), so führt Simon zuerst \(R_p\) aus, um das Symbol ans Ende zu bringen, und danach \(R_i\), um es vom Ende zurück auf Index \(i\) zu ziehen. Liegt es schon am Ende \(n-1\), ist nur \(R_i\) nötig.
Damit ist die Zugzahl in Stufe \(i\)
$$m_i=\begin{cases} 0, & \text{wenn das Zielsymbol bereits an } i \text{ steht},\\ 1, & \text{wenn das Zielsymbol an } n-1 \text{ steht},\\ 2, & \text{wenn das Zielsymbol an einem } p\in\{i+1,\dots,n-2\} \text{ steht}. \end{cases}$$
In den Stufen \(i=0,1,\dots,n-3\) sind höchstens zwei Züge möglich. In der letzten nichttrivialen Stufe \(i=n-2\) bleiben nur zwei Buchstaben übrig; das Ziel kann also entweder schon richtig stehen (0 Züge) oder am Ende liegen (1 Zug). Zwei Züge sind dort unmöglich.
Somit ist das globale Maximum
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
Eine Permutation ist genau dann maximix, wenn jede frühe Stufe \(i\le n-3\) den Zwei-Zug-Fall erzwingt und die letzte Stufe \(i=n-2\) den Ein-Zug-Fall erzwingt.
Daraus folgt eine präzise lokale Bedingung. Unmittelbar vor einer Stufe \(i\le n-3\) muss der Zielbuchstabe strikt im Inneren des aktiven Suffixes liegen, also weder an dessen linker noch an dessen rechter Grenze. Seine Position muss also zu \(\{i+1,\dots,n-2\}\) gehören. Für die letzte Stufe muss der kleinere der letzten beiden übrigen Buchstaben an Position \(n-1\) stehen, damit die abschließende Umkehrung \(R_{n-2}\) noch notwendig ist.
Diese Beschreibung ist viel stärker als „braucht viele Züge“: Sie sagt exakt, welche Vorgängerzustände in jeder Stufe zulässig sind. Erst dadurch wird eine konstruktive Aufzählung möglich.
Sei \(w^\star = A_1A_2\cdots A_n\) das vollständig sortierte Wort. Jede maximix-Anordnung muss nach Simons Verfahren in \(w^\star\) enden. Da jede Umkehrung ihre eigene Inverse ist, können wir alle gültigen Vorgänger rekonstruieren.
Die letzte Stufe ist erzwungen: Damit bei \(i=n-2\) genau ein Zug nötig ist, muss der Zustand unmittelbar vor dem letzten Zug gleich
$$w_{n-2}=R_{n-2}(w^\star)$$
sein.
Angenommen, wir kennen bereits einen after-Zustand für Stufe \(i\), in dem die Positionen \(0,\dots,i\) korrekt fixiert sind. Vorwärts betrachtet muss eine Zwei-Zug-Stufe aus \(R_p\) gefolgt von \(R_i\) bestanden haben, wobei \(p\in\{i+1,\dots,n-2\}\). Rückwärts ergibt das
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
Jeder zulässige Wert \(p\) liefert einen Ast. Der Wert \(p=n-1\) ist ausgeschlossen, weil er dem Ein-Zug-Fall und nicht dem geforderten Zwei-Zug-Fall entsprechen würde.
In Stufe \(i\) gibt es also genau \(n-i-2\) zulässige Möglichkeiten für \(p\). Damit erhält man insgesamt
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!$$
Wahlfolgen.
Das ist nicht nur eine obere Schranke. Der Vorwärtslauf von Simon bestimmt die tatsächlich benutzte Position \(p\) in jeder Stufe eindeutig. Daher entspricht jede maximix-Anordnung genau einer Verzweigungsfolge \((p_0,p_1,\dots,p_{n-3})\), und jede solche Folge rekonstruiert genau eine maximix-Anordnung. Also gilt
$$|\mathcal{M}_n|=(n-2)!.$$
Für \(n=11\) bedeutet das \(9! = 362{,}880\) maximix-Anordnungen; diese Anzahl ist noch klein genug, um explizit erzeugt zu werden.
Das sortierte Wort ist \(ABCD\). Zuerst invertieren wir den erzwungenen letzten Zug:
$$ABCD \xrightarrow{R_2} ABDC.$$
Für Stufe \(i=1\) gibt es nur die Wahl \(p=2\):
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
Für Stufe \(i=0\) wenden wir zunächst \(R_0\) an:
$$ACBD \xrightarrow{R_0} DBCA.$$
Dann entstehen zwei gültige Äste:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
Damit lautet die vollständige maximix-Menge für \(n=4\): \(\{DACB, DBAC\}\). Ihre Größe ist tatsächlich \((4-2)! = 2\). Genau dieses Beispiel verwendet auch die C++-Implementierung als Prüfschritt.
Die Hilfsfunktion reverse_suffix implementiert \(R_i\). Der Generator beginnt mit der sortierten Zeichenkette ABC..., wendet den inversen letzten Zug R(n-2) an und läuft dann mit \(i\) von \(n-3\) bis 0 rückwärts. Für jeden aktuellen after-Zustand wird zuerst R(i) berechnet und danach über alle zulässigen \(p\in[i+1,n-2]\) verzweigt, indem R(p) angewendet wird. Die so entstandene Zustandsliste ist genau die maximix-Menge.
Nach der Erzeugung werden alle Zustände lexikographisch sortiert. Weil die Container 0-basiert indiziert sind, liest der Code den Index 2010, um die 2011. maximix-Anordnung für \(n=11\) zu erhalten. Die C++-Version prüft die Konstruktion zusätzlich an den bekannten Kontrollpunkten \(n=4\) und \(n=6\), bevor die finale Rangfolge ausgegeben wird; Python und Java verwenden denselben Kerngenerator mit weniger Zusatzgerüst.
Der Generator erzeugt genau \((n-2)!\) Endzustände. Jeder Ast führt Suffix-Umkehrungen auf Strings der Länge \(n\) aus, also kostet die Erzeugung \(O((n-2)!\cdot n)\). Das abschließende lexikographische Sortieren kostet \(O((n-2)!\log((n-2)!)\cdot n)\), wenn man die Zeichenkettenlänge in den Vergleichen berücksichtigt. Der Speicherbedarf beträgt \(O((n-2)!\cdot n)\), da die vollständige Zustandsliste gehalten wird. Für den festen Fall \(n=11\) ist das problemlos praktikabel.
\(A,B,C,\dots\) harfleriyle etiketlenmiş \(n\) farklı vagondan oluşan bir tren düşünelim. Simon bu dizilişi yalnızca sonek ters çevirme hamleleriyle sıralıyor: \(i\). aşamada (kodla uyumlu olacak şekilde 0 tabanlı indisleme kullanıyoruz) sıradaki hedef harfi buluyor, gerekiyorsa kuyruğa taşıyor ve ardından \(i\) indisinden başlayan soneği ters çevirerek bu harfi kalıcı biçimde \(i\) konumuna yerleştiriyor. Bir başlangıç permütasyonu, Simon'ı mümkün olan en büyük toplam hamle sayısına zorluyorsa maximix adını alır. Project Euler 336'da amaç, \(n=11\) için tüm maximix dizilişlerini üretmek, sözlük sırasına koymak ve istenen sıradakini cevabı doğrudan gömmeden seçmektir.
\(R_i\), “\(i\) indisinden başlayan soneği ters çevir” işlemi olsun. Ters çevirme bir involüsyon olduğu için \(R_i^{-1}=R_i\) geçerlidir. Tüm maximix durumlarını her permütasyonu ileri yönde deneyerek değil, ters yönden inşa edebilmemizi sağlayan temel gözlem tam olarak budur.
Bir \(i\in\{0,\dots,n-2\}\) aşamasını sabitleyelim. Hedef sembol, sıralı kelime \(A_1A_2\cdots A_n\)'in \(i\). sembolüdür. Bu sembol zaten \(i\) indisindeyse Simon hiçbir şey yapmaz. Eğer sembol iç bölgede bir \(p\in\{i+1,\dots,n-2\}\) konumundaysa önce \(R_p\) uygulanır ve sembol kuyruğa taşınır; sonra \(R_i\) uygulanarak kuyruktan geri \(i\) konumuna getirilir. Eğer sembol zaten son konum \(n-1\)'deyse yalnızca ikinci ters çevirme \(R_i\) gerekir.
Dolayısıyla \(i\). aşamadaki hamle sayısı
$$m_i=\begin{cases} 0, & \text{hedef zaten } i \text{ indisindeyse},\\ 1, & \text{hedef } n-1 \text{ konumundaysa},\\ 2, & \text{hedef } p\in\{i+1,\dots,n-2\} \text{ biçiminde içte bir konumdaysa}. \end{cases}$$
\(i=0,1,\dots,n-3\) aşamalarında en fazla iki hamle harcanabilir. Son anlamlı aşama olan \(i=n-2\)'de ise geriye yalnızca iki harf kaldığı için hedef ya zaten doğrudur (0 hamle) ya da kuyruktadır (1 hamle); burada iki hamle mümkün değildir.
Bu yüzden genel üst sınır
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
Bir permütasyon tam ve ancak tam olarak, her erken aşama \(i\le n-3\) iki hamleyi zorlayıp son aşama \(i=n-2\) tek hamleyi zorladığında maximix olur.
Bu bize kesin bir yerel koşul verir. \(i\le n-3\) aşamasından hemen önce hedef harf, etkin soneğin tam iç kısmında olmalıdır; yani ne sol sınırda ne de sağ sınırda bulunabilir. Başka bir deyişle konumu \(\{i+1,\dots,n-2\}\) kümesinde olmalıdır. Son aşamada ise kalan son iki harften küçük olanı \(n-1\) konumunda durmalıdır ki son \(R_{n-2}\) ters çevirme hâlâ zorunlu olsun.
Bu açıklama “çok hamle harcar” demekten çok daha güçlüdür; her aşamada hangi öncül durumların izinli olduğunu açıkça söyler. Yapıcı üretimi mümkün kılan şey de budur.
\(w^\star = A_1A_2\cdots A_n\) tamamen sıralanmış kelime olsun. Her maximix dizilişi Simon işlemi bittiğinde mutlaka \(w^\star\)'ya ulaşır. Her ters çevirme kendi ters işlemi olduğundan tüm geçerli öncülleri geriye doğru kurabiliriz.
Son aşama zorunludur: \(i=n-2\)'de bir hamle gerekmesi için son hamleden hemen önceki durum
$$w_{n-2}=R_{n-2}(w^\star)$$
olmalıdır.
Şimdi \(i\). aşama sonrasına ait, yani \(0,\dots,i\) konumları doğru sabitlenmiş bir after durumu bildiğimizi varsayalım. İleri yönde iki hamlelik bir aşama, \(p\in\{i+1,\dots,n-2\}\) olmak üzere \(R_p\) ardından \(R_i\) biçiminde gerçekleşmiş olmalıdır. Bu adımı ters çevirdiğimizde
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2$$
elde edilir.
Her geçerli \(p\) bir dal üretir. \(p=n-1\) değerine izin verilmez; çünkü bu, gerekli iki hamle durumu yerine tek hamle durumuna karşılık gelir.
Demek ki \(i\). aşamada \(p\) için tam olarak \(n-i-2\) geçerli seçim vardır. Böylece toplam seçim dizisi sayısı
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!$$
olur.
Bu yalnızca bir üst sınır değildir. Simon'ın ileri yöndeki çalışması, her aşamada kullanılan gerçek \(p\) konumunu tek biçimde belirler. Dolayısıyla her maximix dizilişi tam bir dal seçimi dizisine \((p_0,p_1,\dots,p_{n-3})\) karşılık gelir ve her böyle dizi de tam bir maximix dizilişi üretir. Sonuç olarak
$$|\mathcal{M}_n|=(n-2)!.$$
\(n=11\) için bu sayı \(9! = 362{,}880\)'dir; yani tümünü açıkça üretmek pratik olarak mümkündür.
Sıralı kelime \(ABCD\)'dir. Önce zorunlu son hamleyi tersine çevirelim:
$$ABCD \xrightarrow{R_2} ABDC.$$
\(i=1\) aşamasında tek seçenek \(p=2\)'dir:
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
\(i=0\) aşaması için önce \(R_0\) uygularız:
$$ACBD \xrightarrow{R_0} DBCA.$$
Buradan iki geçerli dal çıkar:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
Dolayısıyla \(n=4\) için tüm maximix kümesi \(\{DACB, DBAC\}\) olur ve boyutu gerçekten \((4-2)! = 2\)'dir. C++ uygulamasındaki kontrol noktası da tam olarak budur.
reverse_suffix yardımcı fonksiyonu \(R_i\)'yi uygular. Üretici fonksiyon sıralı ABC... dizgesiyle başlar, ters son hamle olan R(n-2)'yi uygular ve sonra \(i\)'yi \(n-3\)'ten 0'a kadar geriye doğru dolaşır. Her mevcut after durumu için önce R(i) hesaplanır, ardından tüm geçerli \(p\in[i+1,n-2]\) değerleri üzerinde R(p) uygulanarak dallanılır. Elde edilen durum listesi tam olarak maximix kümesidir.
Üretim tamamlandıktan sonra tüm durumlar sözlük sırasına göre sıralanır. Kaplar 0 tabanlı olduğundan, kod \(n=11\) için 2011. maximix dizilişini almak üzere 2010 indeksini okur. C++ sürümü ayrıca son sıralı dizgeyi üretmeden önce bilinen \(n=4\) ve \(n=6\) kontrol noktalarıyla üretimi doğrular; Python ve Java sürümleri ise aynı çekirdek üreticiyi daha az yardımcı yapı ile kullanır.
Üretici tam olarak \((n-2)!\) adet son durum oluşturur. Her dal, uzunluğu \(n\) olan dizgiler üzerinde sonek ters çevirmeleri yaptığı için üretim maliyeti \(O((n-2)!\cdot n)\)'dir. Son sözlüksel sıralama, dizge karşılaştırma uzunluğu da hesaba katıldığında \(O((n-2)!\log((n-2)!)\cdot n)\) zaman alır. Algoritma tüm durum listesini tuttuğu için bellek kullanımı \(O((n-2)!\cdot n)\)'dir. Sabit girdi \(n=11\) için bu sınırlar tamamen uygulanabilirdir.
Tenemos un tren de \(n\) vagones distintos etiquetados \(A,B,C,\dots\). Simon lo ordena usando solo inversiones de sufijos: en la etapa \(i\) (con índices desde 0, igual que en el código), toma la siguiente letra requerida en el orden final, la lleva al extremo derecho si hace falta y luego invierte el sufijo que comienza en \(i\) para dejar esa letra fijada definitivamente en la posición \(i\). Una permutación inicial se llama maximix si obliga a Simon a usar el mayor número total posible de movimientos. En Project Euler 336, la tarea consiste en generar todas las disposiciones maximix para \(n=11\), ordenarlas lexicográficamente y escoger el rango pedido sin incrustar la respuesta final.
Sea \(R_i\) la operación “invertir el sufijo que empieza en el índice \(i\)”. Como una inversión es una involución, se cumple \(R_i^{-1}=R_i\). Esa observación es la que permite construir todos los estados maximix hacia atrás en lugar de probar cada permutación hacia delante.
Fijemos una etapa \(i\in\{0,\dots,n-2\}\). El símbolo objetivo es el símbolo número \(i\) de la palabra ordenada \(A_1A_2\cdots A_n\). Si ese símbolo ya está en el índice \(i\), Simon no hace nada. Si está en una posición interior \(p\in\{i+1,\dots,n-2\}\), Simon aplica primero \(R_p\) para llevarlo a la cola y luego aplica \(R_i\) para traerlo desde la cola hasta el índice \(i\). Si ya está en la cola \(n-1\), basta con la segunda inversión \(R_i\).
Por tanto, el número de movimientos en la etapa \(i\) es
$$m_i=\begin{cases} 0, & \text{si el objetivo ya está en } i,\\ 1, & \text{si el objetivo está en } n-1,\\ 2, & \text{si el objetivo está en algún } p\in\{i+1,\dots,n-2\}. \end{cases}$$
En las etapas \(i=0,1,\dots,n-3\), Simon puede gastar como mucho dos movimientos. En la última etapa no trivial \(i=n-2\), solo quedan dos letras, así que el objetivo o bien ya está bien colocado (0 movimientos) o bien está en la cola (1 movimiento); allí dos movimientos son imposibles.
Por ello, el máximo global es
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
Una permutación es maximix exactamente cuando toda etapa temprana \(i\le n-3\) fuerza el caso de dos movimientos y la última etapa \(i=n-2\) fuerza el caso de un movimiento.
Esto proporciona una condición local precisa. Justo antes de una etapa \(i\le n-3\), la letra objetivo debe estar estrictamente dentro del sufijo activo, no en su borde izquierdo ni en su borde derecho. Es decir, su posición debe pertenecer a \(\{i+1,\dots,n-2\}\). En la última etapa, la menor de las dos letras restantes debe estar en la posición \(n-1\), para que la inversión final \(R_{n-2}\) siga siendo necesaria.
Esta descripción es mucho más fuerte que “usa muchos movimientos”: nos dice exactamente qué predecesores están permitidos en cada etapa, y por eso la enumeración constructiva es posible.
Sea \(w^\star = A_1A_2\cdots A_n\) la palabra completamente ordenada. Toda disposición maximix debe terminar en \(w^\star\) cuando Simon acaba. Como cada inversión es su propia inversa, podemos reconstruir todos los predecesores válidos.
La última etapa está forzada: para necesitar un movimiento en \(i=n-2\), el estado inmediatamente anterior al último paso debe ser
$$w_{n-2}=R_{n-2}(w^\star).$$
Ahora supongamos que ya conocemos un estado after para la etapa \(i\), con las posiciones \(0,\dots,i\) ya fijadas correctamente. En dirección hacia delante, una etapa de dos movimientos tuvo que ser \(R_p\) seguida de \(R_i\), donde \(p\in\{i+1,\dots,n-2\}\). Al invertir ese paso obtenemos
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
Cada valor admisible de \(p\) produce una rama. El valor \(p=n-1\) no se permite porque correspondería al caso de un solo movimiento, no al caso de dos movimientos que exige maximix.
En la etapa \(i\) hay exactamente \(n-i-2\) elecciones admisibles para \(p\). Por tanto, el número total de secuencias de elección es
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$$
Esto no es solo una cota superior. La ejecución hacia delante de Simon determina de manera única la posición real \(p\) en cada etapa, así que cada disposición maximix corresponde a una única secuencia de ramas \((p_0,p_1,\dots,p_{n-3})\), y cada una de esas secuencias reconstruye exactamente una disposición maximix. Por lo tanto,
$$|\mathcal{M}_n|=(n-2)!.$$
Para \(n=11\), esto significa que existen \(9! = 362{,}880\) disposiciones maximix, una cantidad lo bastante pequeña como para generarla explícitamente.
La palabra ordenada es \(ABCD\). Primero invertimos el último movimiento forzado:
$$ABCD \xrightarrow{R_2} ABDC.$$
Para la etapa \(i=1\), la única elección posible es \(p=2\):
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
Para la etapa \(i=0\), primero aplicamos \(R_0\):
$$ACBD \xrightarrow{R_0} DBCA.$$
Entonces aparecen dos ramas válidas:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
Así, el conjunto maximix completo para \(n=4\) es \(\{DACB, DBAC\}\), y en efecto su tamaño es \((4-2)! = 2\). Ese es el mismo punto de control que usa la implementación en C++.
La función auxiliar reverse_suffix implementa \(R_i\). El generador parte de la cadena ordenada ABC..., aplica el último movimiento inverso R(n-2) y después recorre \(i\) desde \(n-3\) hasta 0. Para cada estado actual after, primero calcula R(i) y luego ramifica sobre todos los \(p\in[i+1,n-2]\) válidos aplicando R(p). La lista resultante de estados coincide exactamente con el conjunto maximix.
Después de generar todos los estados, se ordenan lexicográficamente. Como las estructuras están indexadas desde 0, el código lee el índice 2010 para obtener la 2011.ª disposición maximix de \(n=11\). La versión en C++ además valida la construcción con los puntos de control conocidos para \(n=4\) y \(n=6\) antes de producir la cadena final; las versiones en Python y Java conservan el mismo generador central con menos andamiaje auxiliar.
El generador produce exactamente \((n-2)!\) estados finales. Cada rama realiza inversiones de sufijos sobre cadenas de longitud \(n\), así que la generación cuesta \(O((n-2)!\cdot n)\). La ordenación lexicográfica final cuesta \(O((n-2)!\log((n-2)!)\cdot n)\) si tenemos en cuenta la longitud de las comparaciones entre cadenas. El uso de memoria es \(O((n-2)!\cdot n)\), ya que el algoritmo almacena la lista completa de estados. Para el caso fijo \(n=11\), estas cotas son totalmente manejables.
我们有一列由 \(n\) 个不同车厢组成的火车，标签为 \(A,B,C,\dots\)。Simon 只允许做“后缀翻转”来排序：在第 \(i\) 个阶段（与代码一致，使用从 0 开始的下标），他找到当前应该放到第 \(i\) 位的目标字母，若有必要先把它移到队尾，再翻转从 \(i\) 开始的整个后缀，使该字母永久落在位置 \(i\)。如果某个初始排列会迫使 Simon 使用可能的最大总步数，这个排列就称为 maximix。Project Euler 336 的任务是：在 \(n=11\) 时生成全部 maximix 排列，按字典序排序，并取出题目要求的那个名次，而不是把最终答案硬编码进去。
记 \(R_i\) 为“翻转从下标 \(i\) 开始的后缀”。翻转是一个对合操作，因此 \(R_i^{-1}=R_i\)。正是这个性质，使我们可以逆向构造所有 maximix 状态，而不必正向暴力枚举每个排列。
固定一个阶段 \(i\in\{0,\dots,n-2\}\)。目标符号是有序串 \(A_1A_2\cdots A_n\) 的第 \(i\) 个符号。如果它已经在位置 \(i\)，Simon 什么都不做。如果它位于内部位置 \(p\in\{i+1,\dots,n-2\}\)，Simon 先执行 \(R_p\) 把它送到队尾，再执行 \(R_i\) 把它从队尾送回位置 \(i\)。如果它本来就在队尾 \(n-1\)，则只需要第二次翻转 \(R_i\)。
因此，第 \(i\) 阶段的步数为
$$m_i=\begin{cases} 0, & \text{若目标已经在 } i,\\ 1, & \text{若目标在 } n-1,\\ 2, & \text{若目标在某个 } p\in\{i+1,\dots,n-2\}. \end{cases}$$
对于阶段 \(i=0,1,\dots,n-3\)，Simon 最多只能用两步。到了最后一个非平凡阶段 \(i=n-2\)，只剩两个字母，因此目标要么已经正确（0 步），要么在队尾（1 步）；在那里不可能出现两步。
所以全局最大值为
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
换句话说，一个排列恰好在以下情形下是 maximix：每个早期阶段 \(i\le n-3\) 都触发“两步”情况，而最后阶段 \(i=n-2\) 触发“一步”情况。
这给出了一个非常精确的局部条件。在阶段 \(i\le n-3\) 开始之前，目标字母必须严格位于当前活动后缀的内部，既不能在左端，也不能在右端。也就是说，它的位置必须属于 \(\{i+1,\dots,n-2\}\)。而在最后阶段，剩下两个字母中较小的那个必须处于位置 \(n-1\)，这样最终的 \(R_{n-2}\) 才仍然是必需的。
这比“它会花很多步”更强，因为它精确说明了每一阶段允许哪些前驱状态，也因此才可以进行构造式枚举。
设 \(w^\star = A_1A_2\cdots A_n\) 是完全排好序的字符串。任何 maximix 排列在 Simon 完成后都必须到达 \(w^\star\)。由于每次翻转都是自己的逆，我们可以把所有合法前驱逐层还原出来。
最后一个阶段是强制的：若要在 \(i=n-2\) 恰好需要 1 步，则最后一步之前的状态必须是
$$w_{n-2}=R_{n-2}(w^\star).$$
现在假设我们已经知道某个阶段 \(i\) 的 after 状态，此时位置 \(0,\dots,i\) 都已经正确固定。正向来看，一个两步阶段必然是先做 \(R_p\)，再做 \(R_i\)，其中 \(p\in\{i+1,\dots,n-2\}\)。把这一步反过来，就得到
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
每个合法的 \(p\) 都对应一条分支，而 \(p=n-1\) 不允许出现，因为那对应的是“一步”情况，而不是 maximix 所要求的“两步”情况。
在阶段 \(i\)，合法的 \(p\) 一共有 \(n-i-2\) 个。因此，所有选择序列的总数为
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$$
这不仅仅是一个上界。Simon 的正向执行会在每一阶段唯一确定真实使用的位置 \(p\)，所以每个 maximix 排列都对应唯一的分支序列 \((p_0,p_1,\dots,p_{n-3})\)，反过来每个这样的序列也会重建出唯一一个 maximix 排列。因此
$$|\mathcal{M}_n|=(n-2)!.$$
当 \(n=11\) 时，这个数量是 \(9! = 362{,}880\)，规模足够小，可以直接全部生成。
有序串为 \(ABCD\)。先把最后一个强制步骤反过来：
$$ABCD \xrightarrow{R_2} ABDC.$$
对于阶段 \(i=1\)，唯一可能的选择是 \(p=2\)：
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
对于阶段 \(i=0\)，先应用 \(R_0\)：
$$ACBD \xrightarrow{R_0} DBCA.$$
然后出现两条合法分支：
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
因此 \(n=4\) 的完整 maximix 集合为 \(\{DACB, DBAC\}\)，其大小确实是 \((4-2)! = 2\)。C++ 实现正是用这个例子做校验点。
辅助函数 reverse_suffix 实现 \(R_i\)。生成器从排好序的字符串 ABC... 出发，先应用逆向的最后一步 R(n-2)，然后让 \(i\) 从 \(n-3\) 递减到 0。对每一个当前的 after 状态，先计算 R(i)，再对所有合法的 \(p\in[i+1,n-2]\) 执行 R(p) 完成分支扩展。最终得到的状态列表恰好就是 maximix 集合。
生成完成后，所有状态按字典序排序。由于容器采用 0 下标，代码读取索引 2010，也就是 \(n=11\) 时第 2011 个 maximix 排列。C++ 版本还会在输出最终名次字符串前，用已知的 \(n=4\) 和 \(n=6\) 校验点验证构造过程；Python 与 Java 版本保留了相同的核心生成逻辑，但辅助结构更少。
生成器恰好产生 \((n-2)!\) 个最终状态。每条分支都要对长度为 \(n\) 的字符串执行后缀翻转，所以生成成本为 \(O((n-2)!\cdot n)\)。最后的字典序排序在考虑字符串比较长度时，复杂度为 \(O((n-2)!\log((n-2)!)\cdot n)\)。由于算法需要保存完整状态列表，空间复杂度为 \(O((n-2)!\cdot n)\)。对固定输入 \(n=11\) 而言，这些代价完全可接受。
Рассматривается поезд из \(n\) различных вагонов с метками \(A,B,C,\dots\). Саймон сортирует его, используя только развороты суффиксов: на этапе \(i\) (нумерация с нуля, как и в коде) он берёт следующий нужный символ из окончательно отсортированного порядка, при необходимости переносит его в хвост, а затем разворачивает суффикс, начинающийся в \(i\), чтобы этот символ навсегда встал на позицию \(i\). Начальная перестановка называется maximix, если она заставляет Саймона сделать максимально возможное суммарное число ходов. В задаче Project Euler 336 нужно перечислить все maximix-перестановки для \(n=11\), отсортировать их лексикографически и выбрать требуемый ранг, не зашивая ответ напрямую.
Обозначим через \(R_i\) операцию «развернуть суффикс, начиная с индекса \(i\)». Разворот является инволюцией, поэтому \(R_i^{-1}=R_i\). Именно это свойство позволяет строить все maximix-состояния в обратном направлении, а не проверять каждую перестановку прямым перебором.
Зафиксируем этап \(i\in\{0,\dots,n-2\}\). Целевой символ есть \(i\)-й символ отсортированного слова \(A_1A_2\cdots A_n\). Если он уже стоит на позиции \(i\), делать ничего не нужно. Если он находится во внутренней позиции \(p\in\{i+1,\dots,n-2\}\), Саймон сначала применяет \(R_p\), чтобы перенести символ в хвост, а затем применяет \(R_i\), чтобы вернуть его из хвоста на позицию \(i\). Если же символ уже находится в хвосте \(n-1\), нужен только второй разворот \(R_i\).
Следовательно, число ходов на этапе \(i\) равно
$$m_i=\begin{cases} 0, & \text{если цель уже стоит в } i,\\ 1, & \text{если цель стоит в } n-1,\\ 2, & \text{если цель стоит в некотором } p\in\{i+1,\dots,n-2\}. \end{cases}$$
На этапах \(i=0,1,\dots,n-3\) Саймон может потратить не более двух ходов. На последнем нетривиальном этапе \(i=n-2\) остаются только две буквы, поэтому цель либо уже на месте (0 ходов), либо находится в хвосте (1 ход); два хода там невозможны.
Значит, глобальный максимум равен
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
Перестановка является maximix тогда и только тогда, когда каждый ранний этап \(i\le n-3\) вынуждает случай двух ходов, а последний этап \(i=n-2\) вынуждает случай одного хода.
Отсюда получается точное локальное условие. Непосредственно перед этапом \(i\le n-3\) целевая буква должна находиться строго внутри активного суффикса, то есть не на его левой и не на его правой границе. Иными словами, её позиция должна принадлежать множеству \(\{i+1,\dots,n-2\}\). На последнем этапе меньшая из двух оставшихся букв должна стоять на позиции \(n-1\), чтобы завершающий разворот \(R_{n-2}\) всё ещё был необходим.
Это намного сильнее, чем просто утверждение «требуется много ходов»: оно точно описывает, какие предшествующие состояния допустимы на каждом этапе, а значит делает возможным конструктивное перечисление.
Пусть \(w^\star = A_1A_2\cdots A_n\) — полностью отсортированное слово. Любая maximix-перестановка после завершения процедуры Саймона должна прийти в \(w^\star\). Поскольку каждый разворот совпадает со своей обратной операцией, все допустимые предшественники можно восстанавливать назад.
Последний этап принудителен: чтобы на \(i=n-2\) потребовался ровно один ход, состояние непосредственно перед последним ходом должно быть равно
$$w_{n-2}=R_{n-2}(w^\star).$$
Теперь предположим, что нам уже известен некоторый after-состояние для этапа \(i\), в котором позиции \(0,\dots,i\) уже зафиксированы правильно. В прямом ходе этап с двумя разворотами обязан был иметь вид \(R_p\), затем \(R_i\), где \(p\in\{i+1,\dots,n-2\}\). Если обратить этот шаг, получаем
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
Каждое допустимое значение \(p\) даёт одну ветвь. Значение \(p=n-1\) запрещено, потому что оно соответствовало бы одноходовому случаю, а не нужному maximix-случаю с двумя ходами.
На этапе \(i\) существует ровно \(n-i-2\) допустимых выборов для \(p\). Поэтому общее число последовательностей выбора равно
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$$
Это не просто верхняя оценка. Прямое выполнение алгоритма Саймона однозначно определяет фактическую позицию \(p\) на каждом этапе, поэтому каждой maximix-перестановке соответствует ровно одна последовательность ветвления \((p_0,p_1,\dots,p_{n-3})\), и наоборот, каждая такая последовательность восстанавливает ровно одну maximix-перестановку. Следовательно,
$$|\mathcal{M}_n|=(n-2)!.$$
Для \(n=11\) это даёт \(9! = 362{,}880\) maximix-перестановок, а такой объём ещё вполне можно сгенерировать явно.
Отсортированное слово равно \(ABCD\). Сначала инвертируем принудительный последний ход:
$$ABCD \xrightarrow{R_2} ABDC.$$
Для этапа \(i=1\) существует единственный возможный выбор \(p=2\):
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
Для этапа \(i=0\) сначала применяем \(R_0\):
$$ACBD \xrightarrow{R_0} DBCA.$$
После этого возникают две допустимые ветви:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
Итак, полный maximix-набор для \(n=4\) равен \(\{DACB, DBAC\}\), и его размер действительно равен \((4-2)! = 2\). Этот же пример используется в C++-реализации как контрольная точка.
Вспомогательная функция reverse_suffix реализует \(R_i\). Генератор стартует с отсортированной строки ABC..., применяет обратный последний ход R(n-2), а затем перебирает \(i\) от \(n-3\) вниз до 0. Для каждого текущего состояния after сначала вычисляется R(i), после чего выполняется ветвление по всем допустимым \(p\in[i+1,n-2]\) с применением R(p). Получающийся список состояний в точности совпадает с множеством maximix.
После генерации состояния сортируются лексикографически. Поскольку контейнеры индексируются с нуля, код читает индекс 2010, чтобы получить 2011-ю maximix-перестановку при \(n=11\). Версия на C++ дополнительно проверяет построение на известных контрольных точках \(n=4\) и \(n=6\), прежде чем вывести итоговую строку нужного ранга; версии на Python и Java сохраняют тот же базовый генератор, но с меньшим количеством вспомогательной логики.
Генератор создаёт ровно \((n-2)!\) конечных состояний. Каждая ветвь выполняет развороты суффиксов над строками длины \(n\), поэтому генерация стоит \(O((n-2)!\cdot n)\). Финальная лексикографическая сортировка требует \(O((n-2)!\log((n-2)!)\cdot n)\), если учитывать длину сравниваемых строк. Память составляет \(O((n-2)!\cdot n)\), поскольку алгоритм хранит весь список состояний. Для фиксированного случая \(n=11\) это вполне практично.
لدينا قطار مكوَّن من \(n\) عربات مختلفة موسومة بـ \(A,B,C,\dots\). يقوم Simon بترتيبه باستخدام عمليات قلب لاحقة السلسلة فقط: في المرحلة \(i\) (وبفهرسة تبدأ من الصفر كما في الكود) يأخذ الحرف المطلوب التالي في الترتيب النهائي، وينقله إلى الذيل إذا لزم الأمر، ثم يقلب اللاحقة التي تبدأ عند \(i\) لكي يستقر هذا الحرف نهائيًا في الموضع \(i\). يسمى الترتيب الابتدائي maximix إذا أجبر Simon على تنفيذ أكبر عدد كلي ممكن من الحركات. في Project Euler 336 المطلوب هو توليد جميع ترتيبات maximix عندما \(n=11\)، ثم ترتيبها معجميًا، ثم أخذ الرتبة المطلوبة من دون تضمين الجواب النهائي مباشرة.
لنرمز بـ \(R_i\) إلى العملية «اقلب اللاحقة التي تبدأ عند الفهرس \(i\)». وبما أن القلب عملية تقابل نفسها، فإن \(R_i^{-1}=R_i\). هذه الملاحظة هي التي تسمح لنا ببناء جميع حالات maximix بالعكس بدل اختبار كل تبديل في الاتجاه الأمامي.
ثبّت مرحلة \(i\in\{0,\dots,n-2\}\). الرمز الهدف هو الرمز رقم \(i\) في الكلمة المرتبة \(A_1A_2\cdots A_n\). إذا كان هذا الرمز موجودًا أصلًا عند الموضع \(i\)، فلا يفعل Simon شيئًا. وإذا كان في موضع داخلي \(p\in\{i+1,\dots,n-2\}\)، فإنه يطبق أولًا \(R_p\) لنقل الرمز إلى الذيل، ثم يطبق \(R_i\) لإعادته من الذيل إلى الموضع \(i\). وإذا كان الرمز موجودًا أصلًا في الذيل \(n-1\)، فلا نحتاج إلا إلى القلب الثاني \(R_i\).
لذلك يكون عدد الحركات في المرحلة \(i\)
$$m_i=\begin{cases} 0, & \text{إذا كان الهدف موجودًا أصلًا عند } i,\\ 1, & \text{إذا كان الهدف عند } n-1,\\ 2, & \text{إذا كان الهدف عند موضع } p\in\{i+1,\dots,n-2\}. \end{cases}$$
في المراحل \(i=0,1,\dots,n-3\) يستطيع Simon أن ينفق على الأكثر حركتين. أما في آخر مرحلة غير تافهة \(i=n-2\)، فلا يبقى إلا حرفان، ولذلك يكون الهدف إما في مكانه الصحيح أصلًا (0 حركة) أو في الذيل (1 حركة)؛ ولا يمكن حدوث حالتي حركتين هناك.
ومن ثم يكون الحد الأقصى الكلي
$$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$$
وبالتالي يكون الترتيب maximix إذا وفقط إذا أجبرت كل مرحلة مبكرة \(i\le n-3\) حالة الحركتين، وأجبرت المرحلة الأخيرة \(i=n-2\) حالة الحركة الواحدة.
يعطينا هذا شرطًا محليًا دقيقًا. فقبل المرحلة \(i\le n-3\) مباشرةً، يجب أن يقع الحرف الهدف في داخل اللاحقة النشطة تمامًا، لا عند حدها الأيسر ولا عند حدها الأيمن. أي إن موضعه يجب أن ينتمي إلى \(\{i+1,\dots,n-2\}\). وفي المرحلة الأخيرة يجب أن يكون الأصغر بين الحرفين الأخيرين المتبقّيين موجودًا عند الموضع \(n-1\)، حتى تظل عملية القلب الأخيرة \(R_{n-2}\) ضرورية.
وهذا الوصف أقوى بكثير من مجرد القول إنه “يستهلك حركات كثيرة”، لأنه يحدد بدقة أي الحالات السابقة مسموح بها في كل مرحلة، ومن هنا تأتي إمكانية التوليد البنائي.
لتكن \(w^\star = A_1A_2\cdots A_n\) هي الكلمة المرتبة تمامًا. لا بد أن ينتهي كل ترتيب maximix إلى \(w^\star\) بعد اكتمال إجراء Simon. وبما أن كل عملية قلب هي معكوس نفسها، فيمكننا استرجاع جميع الأسلاف الصحيحة بالعكس.
المرحلة الأخيرة مفروضة: لكي نحتاج حركة واحدة عند \(i=n-2\)، يجب أن تكون الحالة مباشرة قبل الحركة الأخيرة هي
$$w_{n-2}=R_{n-2}(w^\star).$$
والآن افترض أننا نعرف حالة after لمرحلة \(i\)، بحيث تكون المواضع \(0,\dots,i\) قد ثُبِّتت صحيحةً بالفعل. في الاتجاه الأمامي، لا بد أن تكون مرحلة الحركتين قد أخذت الشكل \(R_p\) ثم \(R_i\)، حيث \(p\in\{i+1,\dots,n-2\}\). وعند عكس هذه الخطوة نحصل على
$$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$$
كل قيمة مسموحة لـ \(p\) تعطي فرعًا واحدًا. أما القيمة \(p=n-1\) فهي غير مسموحة لأنها تمثل حالة الحركة الواحدة لا حالة الحركتين المطلوبة في maximix.
في المرحلة \(i\) يوجد بالضبط \(n-i-2\) اختيارًا صالحًا للقيمة \(p\). ولذلك يكون عدد متتاليات الاختيار الكلي
$$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$$
وهذا ليس مجرد حد أعلى. فالتنفيذ الأمامي لخوارزمية Simon يحدد الموضع الحقيقي \(p\) تحديدًا وحيدًا في كل مرحلة، ولذلك يقابل كل ترتيب maximix متتالية فروع وحيدة \((p_0,p_1,\dots,p_{n-3})\)، كما أن كل متتالية من هذا النوع تعيد بناء ترتيب maximix واحد فقط. ومن ثم
$$|\mathcal{M}_n|=(n-2)!.$$
وعندما \(n=11\) نحصل على \(9! = 362{,}880\) ترتيبًا maximix، وهو عدد صغير بما يكفي لتوليده صراحةً.
الكلمة المرتبة هي \(ABCD\). نبدأ بعكس الحركة الأخيرة المفروضة:
$$ABCD \xrightarrow{R_2} ABDC.$$
في المرحلة \(i=1\) لا يوجد إلا الاختيار \(p=2\):
$$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$$
وفي المرحلة \(i=0\) نطبق أولًا \(R_0\):
$$ACBD \xrightarrow{R_0} DBCA.$$
ثم نحصل على فرعين صحيحين:
$$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$$
إذن مجموعة maximix الكاملة عندما \(n=4\) هي \(\{DACB, DBAC\}\)، وحجمها فعلًا يساوي \((4-2)! = 2\). وهذا هو مثال التحقق نفسه المستخدم في تنفيذ C++.
الدالة المساعدة reverse_suffix تنفذ العملية \(R_i\). يبدأ المولّد من السلسلة المرتبة ABC...، ويطبق الحركة العكسية الأخيرة R(n-2)، ثم يمر على \(i\) من \(n-3\) نزولًا إلى 0. ولكل حالة حالية من نوع after يحسب أولًا R(i)، ثم يتشعب على جميع القيم الصحيحة \(p\in[i+1,n-2]\) بتطبيق R(p). والقائمة الناتجة من الحالات هي بالضبط مجموعة maximix.
بعد اكتمال التوليد، تُرتَّب الحالات ترتيبًا معجميًا. وبما أن البنى مفهرسة من الصفر، يقرأ الكود الفهرس 2010 للحصول على الترتيب maximix رقم 2011 عندما \(n=11\). كما تتحقق نسخة C++ من البناء باستخدام نقطتي فحص معروفتين عند \(n=4\) و\(n=6\) قبل إخراج السلسلة النهائية ذات الرتبة المطلوبة، بينما تحتفظ نسختا Python وJava بالجوهر نفسه مع بنية مساعدة أقل.
ينتج المولّد بالضبط \((n-2)!\) حالة نهائية. وكل فرع ينفذ عمليات قلب لاحقات على سلاسل طولها \(n\)، لذا تكون كلفة التوليد \(O((n-2)!\cdot n)\). أما الفرز المعجمي النهائي فيكلف \(O((n-2)!\log((n-2)!)\cdot n)\) إذا أخذنا طول مقارنة السلاسل في الحسبان. ويبلغ استهلاك الذاكرة \(O((n-2)!\cdot n)\) لأن الخوارزمية تحتفظ بقائمة الحالات كاملة. وفي الحالة الثابتة \(n=11\) تكون هذه الحدود عملية تمامًا.