Detailed mathematical approach

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

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