Problem Summary

The task is to start from the letters of the target word in increasing alphabetical order and follow the Steinhaus-Johnson-Trotter ordering of all permutations of those letters. Because consecutive permutations in that order differ by exactly one adjacent transposition, the required quantity is the zero-based SJT rank of the target arrangement.

The words used by the implementation have distinct letters, so sorting the letters gives a unique reference ordering and the target word becomes an ordinary permutation problem.

Mathematical Approach

Let the sorted letters be encoded as $0,1,\dots,n-1$. If the target word corresponds to the permutation $\pi\in S_n$, define $R_n(\pi)$ to be its zero-based position in SJT order. The answer is exactly $R_n(\pi)$.

Step 1: Convert the Word into a Permutation

Sort the letters increasingly and assign ranks from $0$ to $n-1$. Replacing each letter of the target word by its rank produces a permutation.

For example, the letters of BELFRY sort as $B,E,F,L,R,Y$. Therefore BELFRY becomes

$$\pi=(0,1,3,2,4,5).$$

After this translation, the original wording disappears and only permutation structure remains.

Step 2: Use the Recursive Block Structure of SJT Order

SJT order on $S_n$ is built from SJT order on $S_{n-1}$. Take a permutation of size $n-1$, then insert the largest symbol $n-1$ into all $n$ positions, moving it by adjacent swaps. So the permutations of size $n$ are grouped into blocks of size $n$.

If $\pi'$ is obtained from $\pi$ by deleting the symbol $n-1$, then the block containing $\pi$ is indexed by the smaller rank

$$B=R_{n-1}(\pi').$$

That is the key reduction: first rank the shorter permutation, then determine where the removed largest symbol sits inside that block.

Step 3: Determine the Offset Inside the Block

Let $j$ be the zero-based position of $n-1$ inside $\pi$. Adjacent blocks are traversed in opposite directions. When the smaller rank $B$ is even, the largest symbol sweeps from right to left through the block. When $B$ is odd, it sweeps from left to right.

Therefore the within-block offset is

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

Combining block index and offset gives the recurrence

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

with base case $R_1((0))=0$.

Step 4: Why This Equals the Number of Adjacent Swaps

Inside one block, the largest symbol moves one place at a time, so consecutive members of the block differ by one adjacent swap. Between consecutive blocks, the shorter permutation $\pi'$ changes by one SJT step as well. Hence the full SJT ordering of size $n$ is still a Gray code under adjacent transpositions.

So increasing the rank by $1$ means performing exactly one adjacent transposition. The zero-based rank is therefore the number of adjacent swaps performed from the initial sorted word until the target word first appears.

Step 5: Worked Example with BELFRY

We already found

$$\pi=(0,1,3,2,4,5).$$

Now remove the largest symbol repeatedly and record its position each time:

$$\begin{aligned} (0,1,3,2,4,5)&\to j_6=5,\quad (0,1,3,2,4),\\ (0,1,3,2,4)&\to j_5=4,\quad (0,1,3,2),\\ (0,1,3,2)&\to j_4=2,\quad (0,1,2),\\ (0,1,2)&\to j_3=2,\quad (0,1),\\ (0,1)&\to j_2=1,\quad (0). \end{aligned}$$

Starting from $R_1=0$, the recurrence yields

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

Thus BELFRY appears after $59$ adjacent-swap steps in SJT order, exactly matching the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same algorithm. They first sort the input letters and assign each distinct letter its rank in that sorted order. Reading the target word through that lookup table produces the permutation $\pi$.

The implementation then evaluates the recurrence above recursively. At each level it locates the current largest symbol, removes it to form the shorter permutation, computes the smaller SJT rank, and applies the parity rule to decide whether the offset is measured from the right end or the left end of the block. The returned value is the required number of adjacent swaps. Built-in checks confirm, for instance, that CBA has rank $3$ and BELFRY has rank $59$.

Complexity Analysis

For a word of length $n$, each recursive level scans the current permutation to locate the largest symbol and copies the remaining entries into a list of length $n-1$. The total work is therefore

$$n+(n-1)+\cdots+1=O(n^2).$$

The recursion depth is $O(n)$, and the active extra storage is also $O(n)$ because only one shrinking permutation is kept per level. This is easily sufficient for the target input length used in the problem.

Footnotes and References

Problem page: https://projecteuler.net/problem=868
Steinhaus-Johnson-Trotter algorithm: Wikipedia — Steinhaus-Johnson-Trotter algorithm
Adjacent transposition: Wikipedia — Adjacent transposition
Permutation: Wikipedia — Permutation
Gray code: Wikipedia — Gray code

Problemzusammenfassung

Gesucht ist die Anzahl der Schritte in der Steinhaus-Johnson-Trotter-Reihenfolge, die von der alphabetisch sortierten Anordnung der Buchstaben bis zum Zielwort benötigt werden. Da sich zwei aufeinanderfolgende Permutationen in dieser Reihenfolge immer nur durch eine benachbarte Vertauschung unterscheiden, ist die gesuchte Zahl genau der nullbasierte SJT-Rang der Zielanordnung.

Die vom Programm betrachteten Wörter besitzen paarweise verschiedene Buchstaben. Dadurch liefert das Sortieren der Buchstaben eine eindeutige Referenzordnung, und das Wort wird zu einem reinen Permutationsproblem.

Mathematischer Ansatz

Wir kodieren die sortierten Buchstaben als $0,1,\dots,n-1$. Entspricht das Zielwort der Permutation $\pi\in S_n$, so sei $R_n(\pi)$ ihre nullbasierte Position in der SJT-Reihenfolge. Genau dieser Wert ist die gesuchte Antwort.

Schritt 1: Das Wort in eine Permutation umwandeln

Sortiere die Buchstaben aufsteigend und vergib die Ränge $0$ bis $n-1$. Ersetzt man anschließend jeden Buchstaben des Zielworts durch seinen Rang, erhält man eine Permutation.

Für BELFRY ist die sortierte Reihenfolge $B,E,F,L,R,Y$. Also wird BELFRY zu

$$\pi=(0,1,3,2,4,5).$$

Damit verschwindet die konkrete Wortdarstellung, und übrig bleibt nur noch die Struktur der Permutation.

Schritt 2: Die rekursive Blockstruktur der SJT-Reihenfolge nutzen

Die SJT-Reihenfolge auf $S_n$ wird aus der SJT-Reihenfolge auf $S_{n-1}$ aufgebaut. Zu jeder kleineren Permutation wird das größte Symbol $n-1$ in alle $n$ möglichen Positionen eingefügt und dabei jeweils per Nachbartausch weitergeschoben. Deshalb zerfällt $S_n$ in Blöcke der Größe $n$.

Entsteht $\pi'$ durch Entfernen des Symbols $n-1$ aus $\pi$, dann ist der zugehörige Block durch den kleineren Rang

$$B=R_{n-1}(\pi')$$

bestimmt. Zuerst rangiert man also die verkürzte Permutation, danach bestimmt man die Lage des entfernten größten Symbols innerhalb dieses Blocks.

Schritt 3: Den Offset innerhalb des Blocks bestimmen

Sei $j$ die nullbasierte Position von $n-1$ in $\pi$. Benachbarte Blöcke werden in entgegengesetzter Richtung durchlaufen. Ist $B$ gerade, wandert das größte Symbol im Block von rechts nach links. Ist $B$ ungerade, wandert es von links nach rechts.

Damit lautet der Block-Offset

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

Zusammen mit dem Blockindex ergibt sich die Rekursion

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

mit Anfangswert $R_1((0))=0$.

Schritt 4: Warum das genau die Anzahl benachbarter Vertauschungen ist

Innerhalb eines Blocks bewegt sich das größte Symbol immer nur um eine Position weiter, also durch genau einen Nachbartausch. Zwischen zwei aufeinanderfolgenden Blöcken ändert sich die kleinere Permutation $\pi'$ ebenfalls um genau einen SJT-Schritt. Daher bleibt die gesamte SJT-Reihenfolge ein Gray-Code bezüglich benachbarter Vertauschungen.

Jede Rangsteigerung um $1$ entspricht also genau einem benachbarten Tausch. Der nullbasierte Rang ist damit exakt die Zahl der benachbarten Vertauschungen vom sortierten Startwort bis zum Zielwort.

Schritt 5: Durchgerechnetes Beispiel mit BELFRY

Wir haben bereits

$$\pi=(0,1,3,2,4,5).$$

Nun entfernen wir schrittweise jeweils das größte Symbol und notieren seine Position:

Ausgehend von $R_1=0$ folgt

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

BELFRY erscheint also nach $59$ Nachbartausch-Schritten in der SJT-Reihenfolge. Das stimmt genau mit dem Kontrollwert der Implementierung überein.

Wie der Code arbeitet

Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst sortieren sie die Eingabebuchstaben und weisen jedem verschiedenen Buchstaben seinen Rang in dieser Sortierung zu. Liest man das Zielwort durch diese Zuordnung aus, entsteht die Permutation $\pi$.

Danach wendet die Implementierung die obige Rekursion an. Auf jeder Ebene wird das aktuell größte Symbol lokalisiert, entfernt, die kürzere Permutation rekursiv rangiert und anschließend per Paritätsregel entschieden, ob der Offset vom rechten oder linken Blockende gezählt wird. Der zurückgegebene Rang ist genau die gesuchte Zahl benachbarter Vertauschungen. Eingebaute Tests prüfen unter anderem, dass CBA den Rang $3$ und BELFRY den Rang $59$ besitzt.

Komplexitätsanalyse

Für ein Wort der Länge $n$ durchsucht jede Rekursionsebene die aktuelle Permutation nach dem größten Symbol und kopiert die restlichen Elemente in eine Liste der Länge $n-1$. Der Gesamtaufwand ist daher

$$n+(n-1)+\cdots+1=O(n^2).$$

Die Rekursionstiefe beträgt $O(n)$, und der gleichzeitig aktive Zusatzspeicher ist ebenfalls $O(n)$, weil pro Ebene nur eine kürzere Permutation gehalten wird. Für die in diesem Problem vorkommende Wortlänge ist das problemlos ausreichend.

Fußnoten und Referenzen

Problemseite: https://projecteuler.net/problem=868
Steinhaus-Johnson-Trotter-Algorithmus: Wikipedia — Steinhaus-Johnson-Trotter algorithm
Benachbarte Transposition: Wikipedia — Adjacent transposition
Permutation: Wikipedia — Permutation
Gray-Code: Wikipedia — Gray-Code

Problem Özeti

İstenen değer, harfleri alfabetik olarak sıralanmış başlangıç düzeninden hedef kelimeye Steinhaus-Johnson-Trotter sırası boyunca ulaşmak için geçen adım sayısıdır. Bu sıralamada ardışık iki permütasyon tam olarak bir bitişik takasla ayrıldığı için aranan nicelik, hedef düzenin sıfır tabanlı SJT sırasıdır.

Uygulamanın ele aldığı kelimelerde harfler birbirinden farklıdır. Bu yüzden sıralama tek bir referans diziliş üretir ve problem doğrudan bir permütasyon sıralama problemine dönüşür.

Matematiksel Yaklaşım

Sıralanmış harfleri $0,1,\dots,n-1$ olarak kodlayalım. Hedef kelime $\pi\in S_n$ permütasyonuna karşılık geliyorsa, $R_n(\pi)$ ile bunun SJT sırasındaki sıfır tabanlı konumunu gösterelim. Aranan cevap tam olarak bu değerdir.

Adım 1: Kelimeyi Bir Permütasyona Dönüştür

Harfleri artan sırada dizip $0$'dan $n-1$'e kadar dereceler verin. Hedef kelimedeki her harfi bu dereceyle değiştirdiğinizde bir permütasyon elde edersiniz.

Örneğin BELFRY kelimesinin sıralı harfleri $B,E,F,L,R,Y$ olur. Dolayısıyla BELFRY şu permütasyona dönüşür:

$$\pi=(0,1,3,2,4,5).$$

Bundan sonra harflerin kendisi önemsizdir; geriye yalnızca permütasyon yapısı kalır.

Adım 2: SJT Sırasının Özyinelemeli Blok Yapısını Kullan

$S_n$ üzerindeki SJT sırası, $S_{n-1}$ üzerindeki sıradan inşa edilir. Önce daha kısa bir permütasyon alınır, sonra en büyük sembol $n-1$ komşu takaslarla ilerletilerek $n$ olası konumun her birine yerleştirilir. Bu nedenle uzunluğu $n$ olan permütasyonlar, boyutu $n$ olan bloklar halinde gruplanır.

$\pi$ içinden $n-1$ sembolü çıkarılarak $\pi'$ elde edilsin. O halde $\pi$'nin bulunduğu blok, daha kısa permütasyonun sırası ile belirlenir:

$$B=R_{n-1}(\pi').$$

Yani önce kısalan permütasyonun sırası bulunur, sonra çıkarılan en büyük sembolün blok içindeki konumu hesaplanır.

Adım 3: Blok İçi Ofseti Belirle

$j$, $n-1$ sembolünün $\pi$ içindeki sıfır tabanlı konumu olsun. Ardışık bloklar ters yönlerde dolaşılır. $B$ çift ise en büyük sembol blok içinde sağdan sola hareket eder. $B$ tek ise soldan sağa hareket eder.

Bu yüzden blok içi ofset

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

olur. Blok numarasıyla birleştirince özyineleme

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

şeklini alır; başlangıç durumu $R_1((0))=0$ olur.

Adım 4: Bunun Neden Bitişik Takas Sayısı Olduğunu Açıkla

Tek bir blok içinde en büyük sembol her seferinde yalnızca bir konum kayar; yani her ardışık düzen arasında tam bir komşu takas vardır. İki ardışık blok arasında da kısa permütasyon $\pi'$ yalnızca bir SJT adımı ilerler. Böylece tüm sıra, komşu takaslara göre bir Gray code olarak kalır.

Dolayısıyla sıra değeri her $1$ arttığında tam bir bitişik takas yapılmış olur. Sıfır tabanlı sıra, sıralı başlangıç kelimesinden hedef kelimeye kadar yapılan bitişik takas sayısına tam olarak eşittir.

Adım 5: BELFRY Üzerinde Çözümlü Örnek

Az önce

$$\pi=(0,1,3,2,4,5)$$

bulmuştuk. Şimdi her adımda en büyük sembolü çıkarıp konumunu yazalım:

$R_1=0$ ile başlayınca özyineleme şu değerleri verir:

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

Böylece BELFRY, SJT sırası içinde $59$ bitişik takas sonra görünür. Bu sonuç uygulamadaki kontrol değeriyle aynıdır.

Kod Nasıl Çalışır

C++, Python ve Java implementasyonları aynı akışı izler. Önce giriş kelimesinin harflerini sıralar ve her farklı harfe bu sıralamadaki derecesini atarlar. Hedef kelime bu tablo üzerinden okununca $\pi$ permütasyonu elde edilir.

Daha sonra uygulama yukarıdaki özyinelemeyi hesaplar. Her seviyede o andaki en büyük sembol bulunur, çıkarılır, kısalan permütasyonun SJT sırası hesaplanır ve parite kuralına göre ofsetin blok içinde soldan mı sağdan mı ölçüleceği seçilir. Dönen değer doğrudan aranan bitişik takas sayısıdır. Yerleşik doğrulamalar CBA için $3$, BELFRY için $59$ sonucunu verir.

Karmaşıklık Analizi

Uzunluğu $n$ olan bir kelime için her özyineleme seviyesinde en büyük sembol bulunur ve kalan elemanlar uzunluğu $n-1$ olan yeni bir listeye kopyalanır. Toplam iş yükü bu nedenle

$$n+(n-1)+\cdots+1=O(n^2)$$

olur. Özyineleme derinliği $O(n)$, aynı anda tutulan ek bellek de $O(n)$ düzeyindedir; çünkü her seviyede yalnızca bir küçülmüş permütasyon yaşar. Problemin hedef girdi boyutu için bu maliyet fazlasıyla küçüktür.

Dipnotlar ve Kaynaklar

Problem sayfası: https://projecteuler.net/problem=868
Steinhaus-Johnson-Trotter algoritması: Wikipedia — Steinhaus-Johnson-Trotter algorithm
Bitişik transpozisyon: Wikipedia — Adjacent transposition
Permütasyon: Wikipedia — Permütasyon
Gray kodu: Wikipedia — Gri kod

Resumen del Problema

Se pide contar cuántos pasos del orden de Steinhaus-Johnson-Trotter separan la disposición alfabéticamente ordenada de las letras de la palabra objetivo. Como en ese orden dos permutaciones consecutivas siempre difieren en una sola transposición adyacente, la cantidad buscada es exactamente el rango SJT, indexado desde $0$, de la disposición objetivo.

Las palabras utilizadas por la implementación tienen letras distintas, así que al ordenar las letras aparece una referencia única y el problema se convierte en un problema puro de ranking de permutaciones.

Enfoque Matemático

Codificamos las letras ordenadas como $0,1,\dots,n-1$. Si la palabra objetivo corresponde a la permutación $\pi\in S_n$, llamemos $R_n(\pi)$ a su posición con índice inicial $0$ en el orden SJT. Ese valor es precisamente la respuesta.

Paso 1: Convertir la Palabra en una Permutación

Ordena las letras de menor a mayor y asigna rangos desde $0$ hasta $n-1$. Si reemplazamos cada letra de la palabra objetivo por su rango, obtenemos una permutación.

Por ejemplo, las letras de BELFRY se ordenan como $B,E,F,L,R,Y$. Por tanto BELFRY se convierte en

$$\pi=(0,1,3,2,4,5).$$

Desde ese momento ya no importa la palabra en sí: solo importa la estructura de la permutación.

Paso 2: Usar la Estructura Recursiva por Bloques del Orden SJT

El orden SJT sobre $S_n$ se construye a partir del orden SJT sobre $S_{n-1}$. A cada permutación más corta se le inserta el símbolo máximo $n-1$ en las $n$ posiciones posibles, desplazándolo mediante swaps adyacentes. Por eso las permutaciones de tamaño $n$ quedan agrupadas en bloques de tamaño $n$.

Si $\pi'$ se obtiene de $\pi$ eliminando el símbolo $n-1$, entonces el bloque que contiene a $\pi$ queda determinado por el rango menor

$$B=R_{n-1}(\pi').$$

La reducción esencial es esta: primero se clasifica la permutación corta y luego se localiza la posición del símbolo máximo dentro de su bloque.

Paso 3: Determinar el Desplazamiento Dentro del Bloque

Sea $j$ la posición, indexada desde $0$, del símbolo $n-1$ dentro de $\pi$. Los bloques consecutivos se recorren en direcciones opuestas. Si $B$ es par, el símbolo máximo atraviesa el bloque de derecha a izquierda. Si $B$ es impar, lo hace de izquierda a derecha.

Por tanto, el desplazamiento interno es

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

Al combinar índice de bloque y desplazamiento se obtiene la recurrencia

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

con caso base $R_1((0))=0$.

Paso 4: Por Qué Esta Recurrencia Cuenta Swaps Adyacentes

Dentro de un bloque, el símbolo máximo avanza una posición cada vez, así que dos miembros consecutivos del bloque difieren en exactamente un swap adyacente. Entre dos bloques consecutivos, la permutación corta $\pi'$ también cambia mediante un único paso SJT. En consecuencia, todo el orden SJT sigue siendo un Gray code respecto de transposiciones adyacentes.

Eso significa que aumentar el rango en $1$ equivale a ejecutar exactamente un swap adyacente. El rango con índice inicial $0$ coincide, por tanto, con el número de swaps adyacentes efectuados desde la palabra ordenada hasta la palabra objetivo.

Paso 5: Ejemplo Trabajado con BELFRY

Ya tenemos

$$\pi=(0,1,3,2,4,5).$$

Eliminamos ahora el símbolo máximo repetidamente y registramos su posición en cada nivel:

Partiendo de $R_1=0$, la recurrencia da

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

Así, BELFRY aparece tras $59$ pasos de swaps adyacentes en el orden SJT, exactamente el mismo valor de comprobación que usa la implementación.

Cómo Funciona el Código

Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero ordenan las letras de entrada y asignan a cada letra distinta el rango que ocupa en ese orden. Al leer la palabra objetivo con esa tabla de equivalencias se obtiene la permutación $\pi$.

Después, la implementación evalúa recursivamente la fórmula anterior. En cada nivel localiza el símbolo máximo actual, lo elimina para formar la permutación más corta, calcula el rango SJT reducido y usa la regla de paridad para decidir si el desplazamiento debe medirse desde el extremo derecho o desde el izquierdo del bloque. El valor final devuelto es el número buscado de swaps adyacentes. Las comprobaciones incluidas verifican, por ejemplo, que CBA tiene rango $3$ y BELFRY rango $59$.

Análisis de Complejidad

Para una palabra de longitud $n$, cada nivel recursivo recorre la permutación actual para localizar el símbolo máximo y copia el resto en una lista de longitud $n-1$. Por ello el trabajo total es

$$n+(n-1)+\cdots+1=O(n^2).$$

La profundidad de la recursión es $O(n)$, y el almacenamiento extra activo también es $O(n)$, porque en cada nivel solo se conserva una permutación cada vez más corta. Para el tamaño de entrada de este problema, ese coste es muy pequeño.

Notas y Referencias

Página del problema: https://projecteuler.net/problem=868
Algoritmo de Steinhaus-Johnson-Trotter: Wikipedia — Steinhaus-Johnson-Trotter algorithm
Transposición adyacente: Wikipedia — Adjacent transposition
Permutación: Wikipedia — Permutación
Código Gray: Wikipedia — Código Gray

问题概述

题目要求从“把目标单词的字母按字母序排好”的起始状态出发，沿着 Steinhaus-Johnson-Trotter 排列顺序前进，直到第一次到达目标单词。由于该顺序中任意两个相邻排列都只相差一次相邻交换，所以所求的数量就是目标排列在 SJT 顺序中的零基排名。

这里处理的单词都由互不重复的字母组成，因此排序后得到的参考顺序是唯一的，整个问题可以完全转写成一个排列排名问题。

数学方法

把排序后的字母编码成 $0,1,\dots,n-1$。若目标单词对应的排列为 $\pi\in S_n$，记 $R_n(\pi)$ 为它在 SJT 顺序中的零基位置。那么最终答案就是 $R_n(\pi)$。

步骤 1：把单词转成排列

先把字母从小到大排序，再依次赋予 $0$ 到 $n-1$ 的编号。把目标单词中的每个字母替换为对应编号后，就得到一个排列。

例如，BELFRY 的排序结果是 $B,E,F,L,R,Y$，因此 BELFRY 被编码成

$$\pi=(0,1,3,2,4,5).$$

经过这一步以后，原来的字符串信息已经不再重要，剩下的只是排列本身的结构。

步骤 2：利用 SJT 顺序的递归分块结构

$S_n$ 上的 SJT 顺序是由 $S_{n-1}$ 上的 SJT 顺序递归构造出来的。对于每一个长度为 $n-1$ 的排列，都把最大符号 $n-1$ 插入到全部 $n$ 个可能位置，并且通过相邻交换让它逐格移动。因此，长度为 $n$ 的排列自然分成一个个大小为 $n$ 的块。

若从 $\pi$ 中删去符号 $n-1$ 得到 $\pi'$，那么 $\pi$ 所在的块由更短排列的排名决定：

$$B=R_{n-1}(\pi').$$

也就是说，先求短排列的 SJT 排名，再决定被删去的最大符号在该块中的具体位置。

步骤 3：确定块内偏移量

设 $j$ 是符号 $n-1$ 在 $\pi$ 中的零基位置。相邻两个块的扫描方向是交替反转的。如果 $B$ 为偶数，那么最大符号在该块内是从右向左扫过所有位置；如果 $B$ 为奇数，那么它从左向右扫过所有位置。

因此块内偏移量为

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

把块号和块内偏移结合起来，就得到递推公式

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

其初始条件是 $R_1((0))=0$。

步骤 4：为什么这个递推正好计数相邻交换

在同一个块内部，最大符号每次只移动一个位置，所以块内相邻两个排列必然只差一次相邻交换。相邻两个块之间，短排列 $\pi'$ 也只会前进一步 SJT 变换，因此整个长度为 $n$ 的 SJT 顺序仍然是关于相邻交换的 Gray code。

这意味着排名每增加 $1$，就恰好执行了一次相邻交换。因此，零基排名本身就是从排序后的起始单词走到目标单词所经历的相邻交换次数。

步骤 5：以 BELFRY 为例

我们已经得到

$$\pi=(0,1,3,2,4,5).$$

接着不断删去当前最大符号，并记录它在该层中的位置：

从 $R_1=0$ 开始逐层回代：

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

所以 BELFRY 会在 SJT 顺序中经过 $59$ 次相邻交换后出现，这与实现里使用的校验值完全一致。

代码如何实现

C++、Python 和 Java 实现使用的是同一套思路。首先，它们把输入单词的字母排序，并为每个不同字母建立“排序位置到编号”的映射。随后按这个映射读取目标单词，就得到排列 $\pi$。

接下来，实现递归计算上面的 SJT 排名公式。在每一层里，程序先找到当前最大的符号，把它删掉形成更短的排列，再求出较短排列的 SJT 排名，最后依据奇偶性规则判断块内偏移应该从右端还是左端计算。最终返回的就是所求的相邻交换次数。内置校验还验证了 CBA 的排名为 $3$，BELFRY 的排名为 $59$。

复杂度分析

对于长度为 $n$ 的单词，每一层递归都要在线性时间内找到当前最大符号，并把剩余元素复制到一个长度为 $n-1$ 的新列表中。因此总工作量为

$$n+(n-1)+\cdots+1=O(n^2).$$

递归深度是 $O(n)$，同时活跃的额外存储也是 $O(n)$，因为每一层只保留一个更短的排列视图。对题目中的目标单词长度来说，这个复杂度非常轻松。

注释与参考资料

题目页面：https://projecteuler.net/problem=868
Steinhaus-Johnson-Trotter 算法：Wikipedia — Steinhaus-Johnson-Trotter algorithm
相邻换位：Wikipedia — Adjacent transposition
排列：Wikipedia — 置换
Gray 码：Wikipedia — 格雷码

Краткое описание задачи

Нужно определить, сколько шагов в порядке Steinhaus-Johnson-Trotter отделяет алфавитно отсортированное расположение букв от целевого слова. Поскольку соседние перестановки в этом порядке всегда отличаются ровно одной соседней транспозицией, искомая величина совпадает с нулевым по индексации рангом целевой перестановки в порядке SJT.

Во всех словах, используемых реализацией, буквы различны. Поэтому после сортировки букв появляется единственный опорный порядок, и задача полностью сводится к ранжированию перестановки.

Математический подход

Закодируем отсортированные буквы числами $0,1,\dots,n-1$. Если целевому слову соответствует перестановка $\pi\in S_n$, обозначим через $R_n(\pi)$ её нулевой ранг в порядке SJT. Именно это число и требуется найти.

Шаг 1: Превратить слово в перестановку

Сначала отсортируем буквы по возрастанию и присвоим им номера от $0$ до $n-1$. Затем заменим каждую букву целевого слова её номером в этой сортировке. Так получается перестановка.

Например, для BELFRY упорядоченный набор букв равен $B,E,F,L,R,Y$, поэтому BELFRY кодируется как

$$\pi=(0,1,3,2,4,5).$$

После такого преобразования буквенный контекст уже не важен: остаётся только структура перестановки.

Шаг 2: Использовать рекурсивную блочную структуру порядка SJT

Порядок SJT на $S_n$ строится из порядка SJT на $S_{n-1}$. Для каждой более короткой перестановки максимальный символ $n-1$ вставляется во все $n$ возможных позиций и перемещается по ним соседними обменами. Поэтому перестановки длины $n$ естественным образом разбиваются на блоки размера $n$.

Пусть $\pi'$ получается из $\pi$ удалением символа $n-1$. Тогда блок, содержащий $\pi$, определяется меньшим рангом

$$B=R_{n-1}(\pi').$$

Это и есть основной шаг редукции: сначала ранжируется укороченная перестановка, затем определяется положение удалённого максимального символа внутри соответствующего блока.

Шаг 3: Определить смещение внутри блока

Пусть $j$ — нулевая позиция символа $n-1$ в $\pi$. Соседние блоки проходят в противоположных направлениях. Если $B$ чётно, максимальный символ движется внутри блока справа налево. Если $B$ нечётно, он движется слева направо.

Следовательно, внутреннее смещение равно

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

Отсюда получаем рекуррентную формулу

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

с базой $R_1((0))=0$.

Шаг 4: Почему эта рекурсия считает соседние обмены

Внутри одного блока максимальный символ сдвигается каждый раз только на одну позицию, значит соседние элементы блока отличаются ровно одним соседним обменом. Между соседними блоками укороченная перестановка $\pi'$ тоже изменяется на один шаг SJT. Следовательно, весь порядок SJT остаётся Gray-кодом относительно соседних транспозиций.

Поэтому увеличение ранга на $1$ означает выполнение ровно одного соседнего обмена. Нулевой ранг и есть точное число соседних перестановок, выполненных от исходного отсортированного слова до целевого.

Шаг 5: Разобранный пример BELFRY

Мы уже получили

$$\pi=(0,1,3,2,4,5).$$

Теперь последовательно удалим максимальный символ и запишем его позицию на каждом уровне:

Начиная с $R_1=0$, подстановка назад даёт

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

Значит, BELFRY появляется после $59$ шагов соседних обменов в порядке SJT. Это полностью совпадает с контрольным значением, используемым реализацией.

Как работает код

Реализации на C++, Python и Java устроены одинаково. Сначала они сортируют буквы входного слова и присваивают каждой различной букве её номер в отсортированном порядке. Затем по этому соответствию строится перестановка $\pi$, описывающая целевое слово.

Далее реализация рекурсивно вычисляет приведённую выше формулу. На каждом уровне ищется текущий максимальный символ, удаляется из перестановки, вычисляется ранг укороченной перестановки, а затем по правилу чётности определяется, считать ли смещение от правого края блока или от левого. Возвращаемое значение и есть искомое число соседних обменов. Встроенные проверки подтверждают, например, что для CBA получается $3$, а для BELFRY — $59$.

Анализ сложности

Для слова длины $n$ каждый уровень рекурсии линейно ищет максимальный символ и копирует остальные элементы в список длины $n-1$. Поэтому суммарная работа равна

$$n+(n-1)+\cdots+1=O(n^2).$$

Глубина рекурсии составляет $O(n)$, и активная дополнительная память также имеет порядок $O(n)$, потому что на каждом уровне одновременно хранится только одна укороченная перестановка. Для длины целевого слова из задачи это более чем достаточно.

Примечания и ссылки

Страница задачи: https://projecteuler.net/problem=868
Алгоритм Steinhaus-Johnson-Trotter: Wikipedia — Steinhaus-Johnson-Trotter algorithm
Соседняя транспозиция: Wikipedia — Adjacent transposition
Перестановка: Wikipedia — Перестановка
Код Грея: Wikipedia — Код Грея

ملخص المسألة

المطلوب هو عدد الخطوات في ترتيب Steinhaus-Johnson-Trotter التي تفصل بين الترتيب الأبجدي للحروف وبين الكلمة الهدف. وبما أن كل ترتيبين متتاليين في هذا الترتيب يختلفان بعملية تبديل جوار واحدة فقط، فإن القيمة المطلوبة تساوي رتبة التبديل الهدف في ترتيب SJT مع اعتماد الفهرسة من الصفر.

الكلمات التي تتعامل معها الشيفرة تتكوّن من حروف مميزة لا تتكرر. لذلك فإن فرز الحروف يعطي ترتيبًا مرجعيًا وحيدًا، وتتحول المسألة كلها إلى مسألة ترتيب تبديل فقط.

المنهج الرياضي

لنرمّز الحروف بعد فرزها تصاعديًا بالأعداد $0,1,\dots,n-1$. وإذا كانت الكلمة الهدف تقابل التبديل $\pi\in S_n$، فلنكتب $R_n(\pi)$ لرتبته الصفرية في ترتيب SJT. هذه القيمة هي الجواب مباشرة.

الخطوة 1: تحويل الكلمة إلى تبديل

نرتب الحروف تصاعديًا ثم نعطيها الرتب من $0$ إلى $n-1$. بعد ذلك نستبدل كل حرف في الكلمة الهدف برتبته فنحصل على تبديل.

على سبيل المثال، الحروف في BELFRY بعد الفرز هي $B,E,F,L,R,Y$، ولذلك تصبح BELFRY هي

$$\pi=(0,1,3,2,4,5).$$

بعد هذه الخطوة تختفي خصوصية الكلمة نفسها، ولا يبقى إلا البناء التبديلـي.

الخطوة 2: استعمال البنية الكتلية العودية لترتيب SJT

يُبنى ترتيب SJT على $S_n$ انطلاقًا من ترتيب SJT على $S_{n-1}$. نأخذ تبديلًا أقصر، ثم ندرج الرمز الأكبر $n-1$ في جميع المواضع $n$ الممكنة، مع تحريكه عبر تبديلات الجوار. ولهذا تتجمع تبديلات الطول $n$ في كتل، حجم كل كتلة منها يساوي $n$.

إذا كان $\pi'$ ناتجًا عن حذف الرمز $n-1$ من $\pi$، فإن الكتلة التي تحتوي $\pi$ يحددها ترتيب التبديل الأقصر:

$$B=R_{n-1}(\pi').$$

إذًا الفكرة الأساسية هي أن نرتب التبديل الأقصر أولًا، ثم نحدد موضع الرمز الأكبر المحذوف داخل كتلته.

الخطوة 3: تحديد الإزاحة داخل الكتلة

ليكن $j$ هو الموضع الصفري للرمز $n-1$ داخل $\pi$. الكتل المتجاورة تُقرأ في اتجاهين متعاكسين. فإذا كان $B$ زوجيًا، فإن الرمز الأكبر يتحرك داخل الكتلة من اليمين إلى اليسار. وإذا كان $B$ فرديًا، فإنه يتحرك من اليسار إلى اليمين.

وعليه تكون الإزاحة داخل الكتلة مساوية لـ

$$\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2. \end{cases}$$

وبدمج رقم الكتلة مع هذه الإزاحة نحصل على العلاقة العودية

$$R_n(\pi)=nB+\begin{cases} n-1-j, & B\equiv 0\pmod 2,\\ j, & B\equiv 1\pmod 2, \end{cases}$$

مع الحالة الابتدائية $R_1((0))=0$.

الخطوة 4: لماذا تعد هذه العلاقة عدد تبديلات الجوار

داخل الكتلة الواحدة، يتحرك الرمز الأكبر بمقدار خانة واحدة كل مرة، ولذلك فإن كل ترتيبين متتاليين داخل الكتلة يختلفان بعملية تبديل جوار واحدة بالضبط. وبين كتلتين متتاليتين يتغير التبديل الأقصر $\pi'$ أيضًا بخطوة SJT واحدة. لذلك يبقى الترتيب الكامل Gray code بالنسبة لتبديلات الجوار.

هذا يعني أن زيادة الرتبة بمقدار $1$ تعادل تنفيذ تبديل جوار واحد تمامًا. ومن ثم فإن الرتبة الصفرية تساوي عدد تبديلات الجوار من الكلمة المرتبة في البداية حتى ظهور الكلمة الهدف لأول مرة.

الخطوة 5: مثال محلول على BELFRY

لقد وجدنا أن

$$\pi=(0,1,3,2,4,5).$$

والآن نحذف الرمز الأكبر تدريجيًا ونسجل موضعه في كل مستوى:

وبالانطلاق من $R_1=0$ نحصل بالرجوع العكسي على

$$\begin{aligned} R_2&=2\cdot 0+(1-1)=0,\\ R_3&=3\cdot 0+(2-2)=0,\\ R_4&=4\cdot 0+(3-2)=1,\\ R_5&=5\cdot 1+4=9,\\ R_6&=6\cdot 9+5=59. \end{aligned}$$

إذن تظهر BELFRY بعد $59$ خطوة من تبديلات الجوار في ترتيب SJT، وهو تمامًا مقدار التحقق الذي تعتمد عليه الشيفرة.

كيف تعمل الشيفرة

تتبع تطبيقات C++ وPython وJava الخوارزمية نفسها. فهي تبدأ بفرز حروف الإدخال، ثم تعطي كل حرف مميز رتبته في هذا الفرز. وعند قراءة الكلمة الهدف عبر هذا الجدول نحصل على التبديل $\pi$.

بعد ذلك تحسب الشيفرة العلاقة العودية السابقة. في كل مستوى تبحث عن الرمز الأكبر الحالي، وتحذفه لتكوين تبديل أقصر، وتحسب رتبة SJT للتبديل الأقصر، ثم تستخدم قاعدة الفردية والزوجية لتقرر هل تُقاس الإزاحة من الطرف الأيمن للكتلة أم من الطرف الأيسر. والقيمة النهائية المرجعة هي عدد تبديلات الجوار المطلوب. كما تؤكد اختبارات التحقق المضمنة أن CBA تعطي $3$ وأن BELFRY تعطي $59$.

تحليل التعقيد

إذا كان طول الكلمة $n$، فإن كل مستوى عودي يفحص التبديل الحالي للعثور على الرمز الأكبر، ثم ينسخ بقية العناصر إلى قائمة طولها $n-1$. ولذلك يكون مجموع العمل

$$n+(n-1)+\cdots+1=O(n^2).$$

أما عمق العودية فهو $O(n)$، وكذلك الذاكرة الإضافية الفعالة هي $O(n)$، لأن كل مستوى يحتفظ في اللحظة نفسها بتبديل أقصر واحد فقط. وهذا أكثر من كافٍ لطول الكلمة المستهدفة في هذه المسألة.

حواشٍ ومراجع

صفحة المسألة: https://projecteuler.net/problem=868
خوارزمية Steinhaus-Johnson-Trotter: Wikipedia — Steinhaus-Johnson-Trotter algorithm
تبديل الجوار: Wikipedia — Adjacent transposition
التبديل: Wikipedia — تبديل
ترميز غراي: Wikipedia — رمز غراي