For a permutation \(P=(P_1,\dots,P_n)\), one First Sort step finds the first adjacent inversion \(P_i > P_{i+1}\), removes \(P_{i+1}\), and inserts that value at the front. Repeating this operation always ends at the increasing permutation. Let \(F(P)\) be the total number of steps. The problem asks for the lexicographically first permutation satisfying
$$F(P)=12^{12}=8916100448256,$$
and then asks for its 1-based lexicographic rank. The key difficulty is that naive simulation is far too slow to use inside any serious search, so the solution evaluates \(F(P)\) from structural data extracted from the permutation.
For each \(m\in\{1,\dots,n\}\), let \(R_m\) be the relative order of the values \(1,2,\dots,m\) as they appear inside \(P\). Then \(R_1=[1]\), and for every \(m\ge 2\), the permutation \(R_m\) is obtained from \(R_{m-1}\) by inserting the new largest value \(m\) at one specific position.
If \(\operatorname{pos}(x)\) is the position of \(x\) inside \(P\), then the insertion position of \(m\) is
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
So \(\rho_m\) is simply the rank of \(m\) among the values \(1,\dots,m\) when read from left to right in \(P\). This insertion sequence \((\rho_2,\rho_3,\dots,\rho_n)\) uniquely reconstructs the permutation. The implementations recover these values in \(O(n\log n)\) time with a Fenwick tree.
Inside a permutation \(Q=(q_1,\dots,q_m)\), a position \(t\) is a left-to-right maximum if
$$q_t=\max(q_1,\dots,q_t).$$
Let \(L_m\subseteq\{1,\dots,m\}\) be the set of left-to-right-maximum positions of \(R_m\). Instead of storing the set directly, it is encoded as the binary-weighted sum
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
This is convenient because inserting the new largest value \(m+1\) at position \(\rho_{m+1}\) changes the set in a very simple way:
only the maxima strictly before \(\rho_{m+1}\) survive, and the new value becomes a left-to-right maximum at position \(\rho_{m+1}\).
Therefore
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
or, equivalently,
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
So \(W_m\) is a compact summary of exactly the part of the permutation that matters for the recurrence.
The crucial fact used by the solution is that inserting the new largest value at position \(\rho_{m+1}\) increases the First Sort count by the binary suffix of \(W_m\) starting at that position. In formula form,
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
Using the binary encoding, this becomes
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
The intuition is recursive. When the new largest value is inserted, it can only interact with the left-to-right maxima at or to the right of the insertion point. Each such boundary generates a smaller subproblem of the same type, and those recursive contributions line up exactly with powers of two. The implementations rely on this recurrence, and the full validation checks it against exact simulation on all small permutations that are practical to exhaust.
The starting state is
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
Once the insertion positions \(\rho_2,\dots,\rho_n\) are known, the pair \((F(R_m),W_m)\) is updated from \(m=1\) up to \(m=n-1\). Since \(R_n=P\), the final value produced by the recurrence is \(F(P)\). No explicit sequence of First Sort moves needs to be simulated.
This permutation is a useful checkpoint because exact simulation gives \(F(P)=5\).
The reduced permutations are
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
Hence the insertion positions are
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
Now iterate the recurrence.
For \(m=1\): \(W_1=1\), and inserting \(2\) at position \(2\) adds
$$1-\left(1\bmod 2\right)=0.$$
So \(F(R_2)=0\), and
$$W_2=2+\left(1\bmod 2\right)=3.$$
For \(m=2\): inserting \(3\) at position \(2\) adds
$$3-\left(3\bmod 2\right)=2.$$
So \(F(R_3)=2\), and again \(W_3=3\).
For \(m=3\): inserting \(4\) at position \(1\) adds
$$3-\left(3\bmod 1\right)=3.$$
Therefore
$$F(P)=F(R_4)=0+2+3=5,$$
exactly matching direct simulation:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
After the desired permutation has been identified, its 1-based lexicographic rank is computed with the standard Lehmer-code formula. If \(c_i\) denotes the number of still-unused values smaller than \(P_i\), then
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
For \(n=45\), this rank is far beyond 64-bit range, so the implementations use arbitrary-precision integer arithmetic for the final accumulation.
The C++, Python, and Java implementations all follow the same pipeline. First, they store the verified target permutation of length \(45\):
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
Next, they recover the insertion positions \(\rho_m\) from the value positions using a Fenwick tree. Then they iterate the recurrence above, maintaining the current left-to-right-maximum encoding \(W_m\) and the cumulative step count \(F(R_m)\). This verifies that the stored permutation really satisfies
$$F(P)=12^{12}=8916100448256.$$
Finally, the implementation computes the 1-based lexicographic rank by factorial weights. For the verified target permutation, the resulting rank is
$$2432925835413407847.$$
The fuller validation path also checks a small exact checkpoint such as \(F(4,1,3,2)=5\), and cross-checks the fast recurrence against brute-force simulation on all small permutations within the tested range.
Let \(n\) be the permutation length. Recovering the insertion positions with a Fenwick tree costs \(O(n\log n)\) time and \(O(n)\) memory. The recurrence itself is \(O(n)\) once those positions are known. The lexicographic-rank computation in these implementations removes values from an ordered list directly, so it runs in \(O(n^2)\) time and \(O(n)\) memory. For the actual target size \(n=45\), this is easily fast enough.
Für eine Permutation \(P=(P_1,\dots,P_n)\) sucht ein First-Sort-Schritt die erste benachbarte Inversion \(P_i > P_{i+1}\), entfernt \(P_{i+1}\) und setzt diesen Wert an den Anfang. Wiederholt man das, endet man immer bei der aufsteigend sortierten Permutation. Sei \(F(P)\) die Anzahl dieser Schritte. Gesucht ist die lexikographisch erste Permutation mit
$$F(P)=12^{12}=8916100448256,$$
und danach ihr 1-basierter lexikographischer Rang. Direkte Simulation ist als Suchwerkzeug zu teuer, daher wertet die Lösung \(F(P)\) aus einer kompakten strukturellen Beschreibung der Permutation aus.
Für jedes \(m\in\{1,\dots,n\}\) sei \(R_m\) die relative Reihenfolge der Werte \(1,2,\dots,m\), so wie sie in \(P\) erscheinen. Dann gilt \(R_1=[1]\), und für jedes \(m\ge 2\) entsteht \(R_m\) aus \(R_{m-1}\), indem der neue größte Wert \(m\) an genau einer Position eingefügt wird.
Ist \(\operatorname{pos}(x)\) die Position von \(x\) in \(P\), dann lautet diese Einfügeposition
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
\(\rho_m\) ist also einfach der Rang von \(m\) innerhalb der Werte \(1,\dots,m\), wenn man \(P\) von links nach rechts liest. Die Folge \((\rho_2,\rho_3,\dots,\rho_n)\) rekonstruiert die Permutation eindeutig. Die Implementierungen gewinnen diese Werte in \(O(n\log n)\) mit einem Fenwick-Baum.
In einer Permutation \(Q=(q_1,\dots,q_m)\) heißt eine Position \(t\) Links-nach-rechts-Maximum, wenn
$$q_t=\max(q_1,\dots,q_t).$$
Sei \(L_m\subseteq\{1,\dots,m\}\) die Menge dieser Positionen in \(R_m\). Statt die Menge direkt zu speichern, kodieren wir sie durch
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
Diese Binärkodierung ist praktisch, weil das Einfügen des neuen größten Wertes \(m+1\) an Position \(\rho_{m+1}\) die Menge sehr einfach verändert:
Nur die Maxima strikt vor \(\rho_{m+1}\) bleiben erhalten, und der neue Wert wird selbst an Position \(\rho_{m+1}\) zu einem Links-nach-rechts-Maximum.
Daher gilt
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
beziehungsweise äquivalent
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
Die entscheidende Beobachtung der Lösung ist: Fügt man den neuen größten Wert an Position \(\rho_{m+1}\) ein, dann steigt die Anzahl der First-Sort-Schritte genau um den binären Suffix von \(W_m\), der an dieser Position beginnt. Formal:
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
Mit der Binärkodierung wird daraus
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
Die rekursive Intuition dahinter: Mit dem neu eingefügten größten Wert können nur diejenigen Links-nach-rechts-Maxima wechselwirken, die an oder rechts der Einfügeposition liegen. Jedes solche Randstück erzeugt wieder ein kleineres Teilproblem derselben Form, und genau deshalb treten Zweierpotenzen auf. Die Implementierungen stützen sich auf diese Rekurrenz; die vollständige Validierung vergleicht sie zusätzlich auf kleinen Größen mit exakter Simulation.
Der Anfangszustand ist
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
Sobald die Einfügepositionen \(\rho_2,\dots,\rho_n\) bekannt sind, aktualisiert man das Paar \((F(R_m),W_m)\) von \(m=1\) bis \(m=n-1\). Da \(R_n=P\) ist, liefert die letzte Stufe direkt \(F(P)\). Eine explizite Simulation aller First-Sort-Züge ist nicht mehr nötig.
Diese Permutation ist ein guter Kontrollpunkt, weil exakte Simulation \(F(P)=5\) ergibt.
Die reduzierten Permutationen sind
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
Damit lauten die Einfügepositionen
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
Nun wird die Rekurrenz ausgewertet.
Für \(m=1\): \(W_1=1\), und das Einfügen von \(2\) an Position \(2\) addiert
$$1-\left(1\bmod 2\right)=0.$$
Also ist \(F(R_2)=0\), und
$$W_2=2+\left(1\bmod 2\right)=3.$$
Für \(m=2\): Das Einfügen von \(3\) an Position \(2\) addiert
$$3-\left(3\bmod 2\right)=2.$$
Daher ist \(F(R_3)=2\), und erneut \(W_3=3\).
Für \(m=3\): Das Einfügen von \(4\) an Position \(1\) addiert
$$3-\left(3\bmod 1\right)=3.$$
Somit folgt
$$F(P)=F(R_4)=0+2+3=5,$$
genau wie in der direkten Simulation:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
Ist die gesuchte Permutation gefunden, berechnet man ihren 1-basierten lexikographischen Rang mit der Standardformel des Lehmer-Codes. Wenn \(c_i\) die Anzahl noch nicht benutzter Werte kleiner als \(P_i\) ist, dann gilt
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
Für \(n=45\) liegt dieser Rang deutlich außerhalb des 64-Bit-Bereichs, daher verwenden die Implementierungen am Ende Ganzzahlen beliebiger Präzision.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zunächst speichern sie die verifizierte Zielpermutation der Länge \(45\):
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
Anschließend bestimmen sie mit einem Fenwick-Baum aus den Wertpositionen die Einfügepositionen \(\rho_m\). Dann wird die Rekurrenz durchlaufen, wobei gleichzeitig die aktuelle Kodierung \(W_m\) der Links-nach-rechts-Maxima und der kumulierte Wert \(F(R_m)\) aktualisiert werden. So wird verifiziert, dass die gespeicherte Permutation tatsächlich
$$F(P)=12^{12}=8916100448256$$
erfüllt. Danach berechnet die Implementierung den 1-basierten lexikographischen Rang über Fakultätsgewichte. Für die verifizierte Zielpermutation erhält man
$$2432925835413407847.$$
Der ausführlichere Validierungspfad prüft zusätzlich einen kleinen exakten Kontrollwert wie \(F(4,1,3,2)=5\) und vergleicht die schnelle Rekurrenz auf kleinen Permutationen vollständig mit Brute-Force-Simulation.
Sei \(n\) die Länge der Permutation. Das Bestimmen der Einfügepositionen mit einem Fenwick-Baum kostet \(O(n\log n)\) Zeit und \(O(n)\) Speicher. Die Rekurrenz selbst ist danach nur noch \(O(n)\). Die lexikographische Rangberechnung entfernt Werte in diesen Implementierungen direkt aus einer geordneten Liste und benötigt daher \(O(n^2)\) Zeit bei \(O(n)\) Speicher. Für die tatsächliche Zielgröße \(n=45\) ist das problemlos schnell genug.
Bir \(P=(P_1,\dots,P_n)\) permütasyonunda First Sort işlemi, ilk komşu tersliği \(P_i > P_{i+1}\) bulur, \(P_{i+1}\) değerini yerinden çıkarır ve dizinin başına taşır. Bu işlem tekrarlandığında dizi sonunda artan sıraya gelir. Toplam adım sayısını \(F(P)\) ile gösterelim. Problem,
$$F(P)=12^{12}=8916100448256,$$
koşulunu sağlayan leksikografik olarak ilk permütasyonu ve onun 1-bazlı leksikografik sırasını ister. Zor kısım, doğrudan simülasyonun arama içinde kullanılmak için fazla pahalı olmasıdır; bu yüzden çözüm \(F(P)\)'yi permütasyondan çıkarılan yapısal verilerle hesaplar.
Her \(m\in\{1,\dots,n\}\) için \(R_m\), \(P\) içinde görüldükleri sırayla \(1,2,\dots,m\) değerlerinin oluşturduğu göreli permütasyon olsun. O zaman \(R_1=[1]\) olur ve her \(m\ge 2\) için \(R_m\), \(R_{m-1}\)'e yeni en büyük değer \(m\)'in tek bir konuma eklenmesiyle elde edilir.
\(\operatorname{pos}(x)\), \(x\)'in \(P\) içindeki konumu ise ekleme konumu
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}$$
şeklindedir. Yani \(\rho_m\), \(P\) soldan sağa okunurken \(m\)'in \(1,\dots,m\) arasındaki sırasıdır. \((\rho_2,\rho_3,\dots,\rho_n)\) dizisi permütasyonu tek başına yeniden kurmaya yeter. Uygulamalar bu değerleri Fenwick ağacı ile \(O(n\log n)\) sürede çıkarır.
\(Q=(q_1,\dots,q_m)\) permütasyonunda bir \(t\) konumu,
$$q_t=\max(q_1,\dots,q_t)$$
ise soldan-sağa maksimumdur. \(R_m\) içindeki bu konumlar kümesini \(L_m\subseteq\{1,\dots,m\}\) ile gösterelim. Bu kümeyi doğrudan tutmak yerine ikili ağırlıklı toplamla kodlayalım:
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
Bu çok kullanışlıdır, çünkü yeni en büyük değer \(m+1\), \(\rho_{m+1}\) konumuna eklendiğinde küme şu şekilde güncellenir:
\(\rho_{m+1}\)'den önceki maksimumlar korunur, yeni değer \(\rho_{m+1}\) konumunda yeni bir soldan-sağa maksimum olur ve sağ tarafta kalan eski maksimumlar silinir.
Dolayısıyla
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
ve buna eşdeğer olarak
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
Çözümün dayandığı temel gerçek şudur: yeni en büyük değer \(\rho_{m+1}\) konumuna eklendiğinde, First Sort adım sayısındaki artış tam olarak \(W_m\)'nin bu konumdan başlayan ikili soneki olur. Yani
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
İkili kodlama ile bu
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right)$$
haline gelir. Sezgisel açıklama şudur: yeni en büyük eleman yalnızca ekleme noktasındaki ve sağındaki soldan-sağa maksimumlarla etkileşir. Bu sınırların her biri aynı tipte daha küçük bir alt problemi yeniden üretir; bu yüzden katkılar doğal olarak iki kuvvetleri halinde toplanır. Uygulamalar bu bağıntıyı kullanır ve tam doğrulama küçük boyutlarda bunu birebir simülasyonla karşılaştırır.
Başlangıç durumu
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1$$
şeklindedir. \(\rho_2,\dots,\rho_n\) bilindikten sonra \((F(R_m),W_m)\) çifti \(m=1\)'den \(m=n-1\)'e kadar güncellenir. \(R_n=P\) olduğundan, son değer doğrudan \(F(P)\)'yi verir. Böylece tek tek First Sort hamlelerini simüle etmeye gerek kalmaz.
Bu permütasyon iyi bir kontrol örneğidir; çünkü doğrudan simülasyon \(F(P)=5\) verir.
Azaltılmış permütasyonlar
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2]$$
olduğundan ekleme konumları
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1$$
olur.
\(m=1\) için \(W_1=1\) ve \(2\)'nin ikinci konuma eklenmesi
$$1-\left(1\bmod 2\right)=0$$
katkısı yapar. Bu yüzden \(F(R_2)=0\) ve
$$W_2=2+\left(1\bmod 2\right)=3.$$
\(m=2\) için \(3\)'ün ikinci konuma eklenmesi
$$3-\left(3\bmod 2\right)=2$$
katkısı yapar. Böylece \(F(R_3)=2\) ve yine \(W_3=3\) olur.
\(m=3\) için \(4\)'ün birinci konuma eklenmesi
$$3-\left(3\bmod 1\right)=3$$
katkısı yapar. Sonuç olarak
$$F(P)=F(R_4)=0+2+3=5.$$
Bu, doğrudan simülasyonla da aynıdır:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
Hedef permütasyon belirlendikten sonra 1-bazlı leksikografik sıra standart Lehmer kodu formülüyle hesaplanır. Eğer \(c_i\), henüz kullanılmamış ve \(P_i\)'den küçük değerlerin sayısıysa
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
\(n=45\) için bu değer 64-bit aralığını açıkça aşar; bu nedenle son toplama büyük tamsayı aritmetiği ile yapılır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce uzunluğu \(45\) olan doğrulanmış hedef permütasyonu saklarlar:
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
Daha sonra Fenwick ağacı kullanarak değer konumlarından \(\rho_m\) ekleme konumlarını çıkarırlar. Ardından yukarıdaki bağıntı yürütülür; bu sırada hem soldan-sağa maksimum kodu \(W_m\) hem de biriken adım sayısı \(F(R_m)\) güncellenir. Böylece saklanan permütasyonun gerçekten
$$F(P)=12^{12}=8916100448256$$
koşulunu sağladığı doğrulanır. Son aşamada faktöriyel ağırlıklarla 1-bazlı leksikografik sıra hesaplanır. Doğrulanmış hedef permütasyon için bu sıra
$$2432925835413407847$$
çıkar. Daha kapsamlı doğrulama akışı ayrıca \(F(4,1,3,2)=5\) gibi küçük bir kesin kontrolü ve hızlı bağıntının küçük permütasyonlarda brute-force simülasyonla karşılaştırılmasını içerir.
\(n\) permütasyon uzunluğu olsun. Fenwick ağacı ile ekleme konumlarını bulmak \(O(n\log n)\) zaman ve \(O(n)\) bellek gerektirir. Bağıntının kendisi bu konumlar bilindikten sonra yalnızca \(O(n)\) sürer. Bu uygulamalarda leksikografik sıra hesabı, sıralı listedeki elemanları doğrudan çıkardığı için \(O(n^2)\) zaman ve \(O(n)\) bellek kullanır. Gerçek hedef boyut \(n=45\) olduğundan bu maliyet tamamen uygundur.
Para una permutación \(P=(P_1,\dots,P_n)\), un paso de First Sort busca la primera inversión adyacente \(P_i > P_{i+1}\), extrae \(P_{i+1}\) y lo inserta al frente. Si se repite, siempre se llega a la permutación creciente. Sea \(F(P)\) el número total de pasos. El problema pide la primera permutación en orden lexicográfico que cumple
$$F(P)=12^{12}=8916100448256,$$
y después su rango lexicográfico basado en \(1\). La dificultad es que una simulación directa es demasiado cara para usarla dentro de una búsqueda seria, así que la solución evalúa \(F(P)\) a partir de una descripción estructural mucho más compacta.
Para cada \(m\in\{1,\dots,n\}\), sea \(R_m\) el orden relativo de los valores \(1,2,\dots,m\) tal como aparecen dentro de \(P\). Entonces \(R_1=[1]\), y para cada \(m\ge 2\), la permutación \(R_m\) se obtiene a partir de \(R_{m-1}\) insertando el nuevo valor máximo \(m\) en una posición concreta.
Si \(\operatorname{pos}(x)\) denota la posición de \(x\) en \(P\), entonces esa posición de inserción es
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
En otras palabras, \(\rho_m\) es el rango de \(m\) entre los valores \(1,\dots,m\) cuando se leen de izquierda a derecha en \(P\). La sucesión \((\rho_2,\rho_3,\dots,\rho_n)\) reconstruye la permutación de forma única. Las implementaciones calculan estos valores en \(O(n\log n)\) usando un árbol de Fenwick.
En una permutación \(Q=(q_1,\dots,q_m)\), una posición \(t\) es un máximo de izquierda a derecha si
$$q_t=\max(q_1,\dots,q_t).$$
Sea \(L_m\subseteq\{1,\dots,m\}\) el conjunto de esas posiciones en \(R_m\). En vez de guardar el conjunto literalmente, se codifica con la suma binaria
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
Esto es útil porque al insertar el nuevo valor máximo \(m+1\) en la posición \(\rho_{m+1}\), el conjunto cambia de forma muy simple:
sobreviven únicamente los máximos estrictamente anteriores a \(\rho_{m+1}\), y el nuevo valor se convierte en un máximo de izquierda a derecha en la posición \(\rho_{m+1}\).
Por tanto,
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
o, de forma equivalente,
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
El hecho central explotado por la solución es que insertar el nuevo valor máximo en la posición \(\rho_{m+1}\) incrementa \(F\) exactamente en el sufijo binario de \(W_m\) que empieza en esa posición. En fórmula,
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
Con la codificación binaria, eso se reescribe como
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
La intuición es recursiva: el nuevo valor máximo solo puede interactuar con los máximos de izquierda a derecha situados en o a la derecha del punto de inserción. Cada una de esas fronteras produce un subproblema más pequeño del mismo tipo, y por eso las contribuciones aparecen como potencias de \(2\). Las implementaciones usan esta recurrencia y la validación completa la contrasta con simulación exacta en todos los casos pequeños que se pueden agotar.
El estado inicial es
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
Una vez conocidas las posiciones \(\rho_2,\dots,\rho_n\), se actualiza el par \((F(R_m),W_m)\) desde \(m=1\) hasta \(m=n-1\). Como \(R_n=P\), el último valor calculado es precisamente \(F(P)\). No hace falta simular explícitamente toda la secuencia de movimientos de First Sort.
Esta permutación sirve como control porque la simulación exacta da \(F(P)=5\).
Las permutaciones reducidas son
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
Por tanto, las posiciones de inserción son
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
Ahora aplicamos la recurrencia.
Para \(m=1\), \(W_1=1\), e insertar \(2\) en la posición \(2\) añade
$$1-\left(1\bmod 2\right)=0.$$
Así, \(F(R_2)=0\), y
$$W_2=2+\left(1\bmod 2\right)=3.$$
Para \(m=2\), insertar \(3\) en la posición \(2\) añade
$$3-\left(3\bmod 2\right)=2.$$
Entonces \(F(R_3)=2\), y de nuevo \(W_3=3\).
Para \(m=3\), insertar \(4\) en la posición \(1\) añade
$$3-\left(3\bmod 1\right)=3.$$
En consecuencia,
$$F(P)=F(R_4)=0+2+3=5,$$
exactamente como en la simulación directa:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
Una vez identificada la permutación buscada, su rango lexicográfico 1-basado se obtiene mediante la fórmula estándar del código de Lehmer. Si \(c_i\) es el número de valores aún no usados que son menores que \(P_i\), entonces
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
Para \(n=45\), el resultado queda muy fuera del rango de 64 bits, así que las implementaciones usan enteros de precisión arbitraria en la suma final.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero almacenan la permutación objetivo verificada de longitud \(45\):
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
Después recuperan las posiciones de inserción \(\rho_m\) a partir de las posiciones de los valores usando un árbol de Fenwick. Luego recorren la recurrencia anterior, manteniendo tanto la codificación \(W_m\) de los máximos de izquierda a derecha como el conteo acumulado \(F(R_m)\). Así se verifica que la permutación almacenada satisface realmente
$$F(P)=12^{12}=8916100448256.$$
Por último, la implementación calcula el rango lexicográfico 1-basado mediante pesos factoriales. Para la permutación objetivo verificada, el rango obtenido es
$$2432925835413407847.$$
La ruta de validación más completa también comprueba un caso pequeño exacto como \(F(4,1,3,2)=5\) y contrasta la recurrencia rápida con la simulación exhaustiva en todas las permutaciones pequeñas incluidas en la prueba.
Sea \(n\) la longitud de la permutación. Recuperar las posiciones de inserción con un árbol de Fenwick cuesta \(O(n\log n)\) tiempo y \(O(n)\) memoria. La recurrencia posterior es \(O(n)\). El cálculo del rango lexicográfico en estas implementaciones elimina valores directamente de una lista ordenada, por lo que cuesta \(O(n^2)\) tiempo y \(O(n)\) memoria. Para el tamaño real \(n=45\), el coste es completamente aceptable.
对于一个排列 \(P=(P_1,\dots,P_n)\)，一次 First Sort 操作会寻找第一个相邻逆序 \(P_i > P_{i+1}\)，把 \(P_{i+1}\) 从原位置取出，再插入到最前面。不断重复后，排列一定会变成升序。记总步数为 \(F(P)\)。本题要求找到满足
$$F(P)=12^{12}=8916100448256,$$
的字典序最小排列，并输出它的 1 基字典序排名。难点在于，如果在搜索过程中对每个候选排列都直接模拟整个过程，代价会非常高，因此解法必须把 \(F(P)\) 改写成一种可以快速计算的结构公式。
对每个 \(m\in\{1,\dots,n\}\)，定义 \(R_m\) 为排列 \(P\) 中数值 \(1,2,\dots,m\) 按原相对顺序抽取出来后得到的排列。于是 \(R_1=[1]\)，并且对于每个 \(m\ge 2\)，\(R_m\) 都可以由 \(R_{m-1}\) 通过把新的最大值 \(m\) 插入某个确定位置得到。
若 \(\operatorname{pos}(x)\) 表示 \(x\) 在 \(P\) 中的位置，那么这个插入位置满足
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
也就是说，\(\rho_m\) 就是从左到右阅读 \(P\) 时，数值 \(m\) 在集合 \(\{1,\dots,m\}\) 中的相对名次。只要知道 \((\rho_2,\rho_3,\dots,\rho_n)\)，就能唯一重建整个排列。实现中用 Fenwick 树在线统计前面已有多少更小值，因此可以在 \(O(n\log n)\) 时间内得到全部插入位置。
在排列 \(Q=(q_1,\dots,q_m)\) 中，如果某个位置 \(t\) 满足
$$q_t=\max(q_1,\dots,q_t),$$
那么该位置就是一个“从左到右最大值”位置。记 \(R_m\) 中所有这类位置构成的集合为 \(L_m\subseteq\{1,\dots,m\}\)。为了方便递推，不直接存集合，而是用一个二进制权重和来编码：
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
这个编码非常合适，因为当新的最大值 \(m+1\) 插入到位置 \(\rho_{m+1}\) 时，左到右最大值集合的变化极其简单：
\(\rho_{m+1}\) 之前的那些最大值全部保留；新插入的最大值本身在位置 \(\rho_{m+1}\) 成为新的左到右最大值；而原来位于 \(\rho_{m+1}\) 或其右侧的左到右最大值会全部失效。
因此有
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1},$$
等价地也可以写成
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
也就是说，\(W_m\) 精确保存了后续递推真正需要的那部分结构信息。
解法所利用的核心事实是：把新的最大值插入到位置 \(\rho_{m+1}\) 时，First Sort 的总步数恰好增加当前编码 \(W_m\) 从该位置开始的二进制后缀。公式为
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
借助上面的编码，这可以改写为
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
其直观原因是递归性的。新插入的最大值只会和插入点及其右侧的左到右最大值发生相互作用；每一条这样的“边界”都会再产生一个同类型但规模更小的子问题，于是贡献自然表现为二的幂。实现正是建立在这个递推之上，而完整验证则把它和小规模排列上的精确模拟逐一比对，确认结果完全一致。
初始状态是
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
当全部插入位置 \(\rho_2,\dots,\rho_n\) 求出后，就可以从 \(m=1\) 迭代到 \(m=n-1\)，不断更新 \((F(R_m),W_m)\)。因为最终 \(R_n=P\)，所以最后得到的值就是 \(F(P)\)。整个过程中不需要显式模拟每一步 First Sort 的移动。
这个排列非常适合作为检验点，因为直接模拟可知 \(F(P)=5\)。
依次抽取较小值后得到
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
因此插入位置为
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
下面按递推计算。
当 \(m=1\) 时，\(W_1=1\)，把 \(2\) 插入到第 \(2\) 位所增加的步数是
$$1-\left(1\bmod 2\right)=0.$$
所以 \(F(R_2)=0\)，同时
$$W_2=2+\left(1\bmod 2\right)=3.$$
当 \(m=2\) 时，把 \(3\) 插入到第 \(2\) 位所增加的步数是
$$3-\left(3\bmod 2\right)=2.$$
于是 \(F(R_3)=2\)，并且仍有 \(W_3=3\)。
当 \(m=3\) 时，把 \(4\) 插入到第 \(1\) 位所增加的步数是
$$3-\left(3\bmod 1\right)=3.$$
因此
$$F(P)=F(R_4)=0+2+3=5,$$
与直接模拟完全一致：
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
找到目标排列后，还需要计算它的 1 基字典序排名。设 \(c_i\) 表示在处理到第 \(i\) 个位置时，尚未使用且比 \(P_i\) 小的数有多少个，那么标准的 Lehmer 编码公式是
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
当 \(n=45\) 时，这个结果远远超出普通 64 位整数范围，因此实现使用任意精度整数来完成最终累加。
C++、Python 和 Java 三个实现遵循同一条主线。首先，它们保存已经验证过的长度为 \(45\) 的目标排列：
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
接着，程序根据每个数值在排列中的位置，用 Fenwick 树求出全部插入位置 \(\rho_m\)。然后按上面的递推从小到大更新左到右最大值编码 \(W_m\) 和累计步数 \(F(R_m)\)，从而验证该排列确实满足
$$F(P)=12^{12}=8916100448256.$$
最后，再利用阶乘权重计算 1 基字典序排名。对于这个已经验证的目标排列，排名结果为
$$2432925835413407847.$$
完整实现里还包含小规模校验，例如验证 \(F(4,1,3,2)=5\)，并把快速递推与小规模排列的穷举模拟进行逐个对照。
设排列长度为 \(n\)。使用 Fenwick 树恢复全部插入位置需要 \(O(n\log n)\) 时间和 \(O(n)\) 空间。递推本身在线性时间 \(O(n)\) 内完成。当前实现计算字典序排名时，会从一个有序表中直接删除元素，因此这一部分是 \(O(n^2)\) 时间、\(O(n)\) 空间。对于实际目标大小 \(n=45\)，这完全足够快。
Для перестановки \(P=(P_1,\dots,P_n)\) один шаг First Sort ищет первую соседнюю инверсию \(P_i > P_{i+1}\), удаляет \(P_{i+1}\) и вставляет этот элемент в начало. При повторении процесс всегда заканчивается возрастающей перестановкой. Обозначим через \(F(P)\) общее число шагов. Требуется найти лексикографически первую перестановку, для которой
$$F(P)=12^{12}=8916100448256,$$
а затем вычислить её 1-базовый лексикографический ранг. Прямая симуляция слишком дорога для использования внутри поиска, поэтому решение переводит вычисление \(F(P)\) в компактную структурную рекурсию.
Для каждого \(m\in\{1,\dots,n\}\) обозначим через \(R_m\) относительный порядок чисел \(1,2,\dots,m\) в перестановке \(P\). Тогда \(R_1=[1]\), а для каждого \(m\ge 2\) перестановка \(R_m\) получается из \(R_{m-1}\) вставкой нового наибольшего значения \(m\) в одну определённую позицию.
Если \(\operatorname{pos}(x)\) обозначает позицию числа \(x\) в \(P\), то эта позиция вставки равна
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
То есть \(\rho_m\) есть ранг числа \(m\) среди значений \(1,\dots,m\), если смотреть на \(P\) слева направо. Последовательность \((\rho_2,\rho_3,\dots,\rho_n)\) однозначно задаёт перестановку. Реализация находит эти величины за \(O(n\log n)\) с помощью дерева Фенвика.
В перестановке \(Q=(q_1,\dots,q_m)\) позиция \(t\) называется максимумом слева направо, если
$$q_t=\max(q_1,\dots,q_t).$$
Пусть \(L_m\subseteq\{1,\dots,m\}\) — множество таких позиций в \(R_m\). Вместо прямого хранения множества удобно использовать двоичную кодировку
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
Она подходит идеально, потому что при вставке нового наибольшего значения \(m+1\) в позицию \(\rho_{m+1}\) множество максимумов меняется очень просто:
сохраняются только максимумы строго левее \(\rho_{m+1}\), а новый элемент становится максимумом слева направо в самой позиции \(\rho_{m+1}\).
Следовательно,
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
или эквивалентно
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
Ключевой факт, на котором основано решение, состоит в следующем: вставка нового наибольшего элемента в позицию \(\rho_{m+1}\) увеличивает число шагов ровно на двоичный суффикс числа \(W_m\), начинающийся с этой позиции. Формально,
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
Через кодировку это записывается как
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
Интуиция рекурсивна: новый наибольший элемент взаимодействует только с теми максимумами слева направо, которые стоят в точке вставки или правее. Каждая такая граница создаёт меньшую задачу того же типа, поэтому вклад естественным образом выражается степенями двойки. Реализация использует именно эту формулу, а расширенная проверка сравнивает её с точной симуляцией на всех малых перестановках из тестируемого диапазона.
Начальное состояние имеет вид
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
После нахождения позиций \(\rho_2,\dots,\rho_n\) пара \((F(R_m),W_m)\) обновляется от \(m=1\) до \(m=n-1\). Поскольку \(R_n=P\), итоговое значение и есть \(F(P)\). Явная симуляция всех шагов First Sort не нужна.
Эта перестановка удобна как контрольный пример, потому что точная симуляция даёт \(F(P)=5\).
Редуцированные перестановки таковы:
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
Поэтому позиции вставки равны
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
Теперь применим рекурсию.
Для \(m=1\): \(W_1=1\), а вставка \(2\) во вторую позицию добавляет
$$1-\left(1\bmod 2\right)=0.$$
Значит, \(F(R_2)=0\), и
$$W_2=2+\left(1\bmod 2\right)=3.$$
Для \(m=2\): вставка \(3\) во вторую позицию добавляет
$$3-\left(3\bmod 2\right)=2.$$
Следовательно, \(F(R_3)=2\), и снова \(W_3=3\).
Для \(m=3\): вставка \(4\) в первую позицию добавляет
$$3-\left(3\bmod 1\right)=3.$$
Тем самым
$$F(P)=F(R_4)=0+2+3=5,$$
что точно совпадает с прямой симуляцией:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
После нахождения нужной перестановки остаётся вычислить её 1-базовый лексикографический ранг. Если \(c_i\) — число ещё не использованных значений, меньших \(P_i\), то стандартная формула кода Лемера имеет вид
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
При \(n=45\) итог выходит далеко за пределы 64-битного диапазона, поэтому в финальном подсчёте используется длинная арифметика.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала в них хранится уже проверенная целевая перестановка длины \(45\):
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
Затем по позициям значений восстанавливаются все позиции вставки \(\rho_m\) с помощью дерева Фенвика. После этого запускается рекурсия, которая одновременно обновляет кодировку максимумов слева направо \(W_m\) и накопленное число шагов \(F(R_m)\). Так проверяется, что сохранённая перестановка действительно удовлетворяет условию
$$F(P)=12^{12}=8916100448256.$$
На последнем этапе по факториальным весам вычисляется 1-базовый лексикографический ранг. Для проверенной целевой перестановки он равен
$$2432925835413407847.$$
Более полный режим проверки также подтверждает малый точный контроль \(F(4,1,3,2)=5\) и сравнивает быструю рекурсию с полным перебором на всех малых перестановках из проверяемого диапазона.
Пусть \(n\) — длина перестановки. Восстановление позиций вставки при помощи дерева Фенвика занимает \(O(n\log n)\) времени и \(O(n)\) памяти. Сама рекурсия после этого работает за \(O(n)\). Вычисление лексикографического ранга в текущих реализациях удаляет элементы прямо из упорядоченного списка, поэтому стоит \(O(n^2)\) времени и \(O(n)\) памяти. Для реального размера \(n=45\) это более чем достаточно быстро.
لأي تبديل \(P=(P_1,\dots,P_n)\)، تقوم خطوة First Sort بالبحث عن أول انقلاب متجاور \(P_i > P_{i+1}\)، ثم تحذف \(P_{i+1}\) من مكانه وتضعه في المقدمة. وعند تكرار العملية نصل دائمًا إلى الترتيب التصاعدي. نرمز بعدد الخطوات الكلي إلى \(F(P)\). المطلوب هو إيجاد أول تبديل معجميًا يحقق
$$F(P)=12^{12}=8916100448256,$$
ثم حساب رتبته المعجمية ذات الأساس \(1\). الصعوبة الأساسية أن المحاكاة المباشرة مكلفة جدًا إذا استُخدمت داخل البحث، ولذلك تعتمد الفكرة على تحويل \(F(P)\) إلى صيغة بنيوية سريعة الحساب.
لكل \(m\in\{1,\dots,n\}\)، ليكن \(R_m\) هو الترتيب النسبي للقيم \(1,2,\dots,m\) كما تظهر داخل \(P\). عندئذٍ \(R_1=[1]\)، ولكل \(m\ge 2\) نحصل على \(R_m\) من \(R_{m-1}\) بإدراج القيمة الجديدة الأكبر \(m\) في موضع محدد.
إذا كانت \(\operatorname{pos}(x)\) هي موضع القيمة \(x\) داخل \(P\)، فإن موضع الإدراج يساوي
$$\rho_m=1+\#\{x<m:\operatorname{pos}(x)<\operatorname{pos}(m)\}.$$
أي إن \(\rho_m\) هو رتبة \(m\) بين القيم \(1,\dots,m\) عند قراءة \(P\) من اليسار إلى اليمين. والمتتالية \((\rho_2,\rho_3,\dots,\rho_n)\) تكفي لإعادة بناء التبديل بشكل وحيد. وتحسبها التطبيقات في زمن \(O(n\log n)\) باستعمال شجرة Fenwick.
في التبديل \(Q=(q_1,\dots,q_m)\)، تكون الخانة \(t\) موضع قيمة عظمى من اليسار إلى اليمين إذا تحقق
$$q_t=\max(q_1,\dots,q_t).$$
ولنرمز بمجموعة هذه المواضع داخل \(R_m\) إلى \(L_m\subseteq\{1,\dots,m\}\). بدلًا من تخزين المجموعة مباشرة، نستخدم الترميز الثنائي
$$W_m=\sum_{t\in L_m}2^{t-1}.$$
هذا الترميز مناسب جدًا، لأن إدراج القيمة الجديدة الأكبر \(m+1\) في الموضع \(\rho_{m+1}\) يغيّر المجموعة بطريقة بسيطة:
تبقى فقط المواضع العظمى الواقعة قبل \(\rho_{m+1}\)، وتصبح القيمة الجديدة نفسها قيمة عظمى من اليسار إلى اليمين عند الموضع \(\rho_{m+1}\).
لذلك نحصل على
$$W_{m+1}=2^{\rho_{m+1}-1}+\sum_{\substack{t\in L_m\\ t<\rho_{m+1}}}2^{t-1}$$
أو بصورة مكافئة
$$W_{m+1}=2^{\rho_{m+1}-1}+\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
الحقيقة المحورية التي تستعملها الحلول هي أن إدراج القيمة الجديدة الأكبر في الموضع \(\rho_{m+1}\) يزيد عدد الخطوات بمقدار الذيل الثنائي لـ \(W_m\) ابتداءً من هذا الموضع. أي:
$$F(R_{m+1})=F(R_m)+\sum_{\substack{t\in L_m\\ t\ge \rho_{m+1}}}2^{t-1}.$$
وباستخدام الترميز السابق تصبح العلاقة
$$F(R_{m+1})=F(R_m)+W_m-\left(W_m \bmod 2^{\rho_{m+1}-1}\right).$$
والفكرة الحدسية هنا تكرارية: القيمة الجديدة الأكبر لا تتفاعل إلا مع القيم العظمى من اليسار إلى اليمين الموجودة عند موضع الإدراج أو إلى يمينه. وكل حد فاصل من هذه الحدود يولد مسألة أصغر من النوع نفسه، ولذلك تظهر المساهمات على صورة قوى للعدد \(2\). تعتمد التطبيقات على هذه العلاقة، كما يجري التحقق منها على الحالات الصغيرة بمقارنتها مع المحاكاة الدقيقة.
نبدأ من الحالة
$$R_1=[1],\qquad F(R_1)=0,\qquad W_1=1.$$
وبعد حساب جميع مواضع الإدراج \(\rho_2,\dots,\rho_n\)، نحدّث الزوج \((F(R_m),W_m)\) من \(m=1\) حتى \(m=n-1\). وبما أن \(R_n=P\)، فإن القيمة النهائية الناتجة من هذه العملية هي نفسها \(F(P)\). وهكذا لا حاجة لمحاكاة كل انتقالة من انتقالات First Sort بشكل صريح.
هذا التبديل مفيد كحالة فحص، لأن المحاكاة المباشرة تعطي \(F(P)=5\).
التبديلات المختزلة هي
$$R_1=[1],\qquad R_2=[1,2],\qquad R_3=[1,3,2],\qquad R_4=[4,1,3,2].$$
ومن ثم فإن مواضع الإدراج تساوي
$$\rho_2=2,\qquad \rho_3=2,\qquad \rho_4=1.$$
الآن نطبّق العلاقة التكرارية.
عند \(m=1\)، لدينا \(W_1=1\)، وإدراج \(2\) في الموضع \(2\) يضيف
$$1-\left(1\bmod 2\right)=0.$$
إذًا \(F(R_2)=0\)، وكذلك
$$W_2=2+\left(1\bmod 2\right)=3.$$
وعند \(m=2\)، فإن إدراج \(3\) في الموضع \(2\) يضيف
$$3-\left(3\bmod 2\right)=2.$$
ومن ثم \(F(R_3)=2\)، ويبقى \(W_3=3\).
وعند \(m=3\)، فإن إدراج \(4\) في الموضع \(1\) يضيف
$$3-\left(3\bmod 1\right)=3.$$
إذن
$$F(P)=F(R_4)=0+2+3=5,$$
وهو تمامًا ما تعطيه المحاكاة المباشرة:
$$[4,1,3,2]\to[1,4,3,2]\to[3,1,4,2]\to[1,3,4,2]\to[2,1,3,4]\to[1,2,3,4].$$
بعد تحديد التبديل المطلوب، تحسب رتبته المعجمية ذات الأساس \(1\) بواسطة الصيغة القياسية لترميز Lehmer. إذا كان \(c_i\) هو عدد القيم غير المستخدمة بعد والتي هي أصغر من \(P_i\)، فإن
$$\operatorname{rank}(P)=1+\sum_{i=1}^{n} c_i\,(n-i)!.$$
وعندما يكون \(n=45\)، تكون النتيجة أكبر بكثير من مجال 64-بت، ولذلك تستعمل التطبيقات حسابًا صحيحًا بدقة غير محدودة في التجميع النهائي.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تخزن التبديل الهدف الذي تم التحقق منه وطوله \(45\):
$$\left(1,2,3,\dots,24,26,25,27,28,30,32,34,36,38,40,39,42,45,43,41,37,35,33,31,29,44\right).$$
بعد ذلك تستخرج مواضع الإدراج \(\rho_m\) من مواضع القيم باستخدام شجرة Fenwick. ثم تطبق العلاقة التكرارية السابقة مع تحديث ترميز القيم العظمى من اليسار إلى اليمين \(W_m\) والعدد التراكمي للخطوات \(F(R_m)\). وبهذا يجري التحقق من أن التبديل المخزن يحقق فعلًا
$$F(P)=12^{12}=8916100448256.$$
وفي النهاية تحسب الرتبة المعجمية ذات الأساس \(1\) بأوزان عامليّة. وللتبديل الهدف المتحقق منه تكون النتيجة
$$2432925835413407847.$$
ويشمل مسار التحقق الأوسع أيضًا فحص قيمة صغيرة دقيقة مثل \(F(4,1,3,2)=5\)، ومقارنة العلاقة السريعة مع المحاكاة الشاملة على جميع التبديلات الصغيرة الداخلة في الاختبار.
إذا كان \(n\) هو طول التبديل، فإن استرجاع مواضع الإدراج بواسطة شجرة Fenwick يكلف \(O(n\log n)\) زمنًا و\(O(n)\) ذاكرة. وبعد ذلك تعمل العلاقة التكرارية نفسها في \(O(n)\) فقط. أما حساب الرتبة المعجمية في هذه التطبيقات فيحذف العناصر مباشرة من قائمة مرتبة، ولذلك تكلفته \(O(n^2)\) زمنًا و\(O(n)\) ذاكرة. وبالنسبة إلى الحجم الفعلي \(n=45\)، فهذه الكلفة صغيرة جدًا.