Project Euler Problem 868

Solution

Answer: 3832914911887589

This problem is a ranking problem for the permutation order generated by the bell-ringing rule. The key is to recognize that the procedure is exactly the Steinhaus–Johnson–Trotter (SJT) permutation order (also known as “plain changes”).

We are asked for the number of swaps needed to reach a given permutation from the initial alphabetical ordering. Since every step performs exactly one adjacent swap, the number of swaps equals the 0-based index of the target permutation in the SJT ordering.

1. Mathematical analysis

Let $R(P)$ be the number of swaps required to reach permutation $P$.

We want:

$$R(\texttt{NOWPICKBELFRYMATHS})$$

starting from the letters in alphabetical order.

Recursive structure of SJT order

Suppose we have $n$ letters, and let the largest letter be $L$.

The SJT generation for $n$ letters is built recursively from the order for $n-1$ letters:

Take each permutation of the smaller $n-1$ letters.
Insert $L$ into all possible positions.
The insertion direction alternates:

If the smaller permutation has even index, move $L$ from right to left.

If the smaller permutation has odd index, move $L$ from left to right.

Example for $ABC$:

From permutations of $AB$:

$AB$ (index 0, even): insert $C$ right→left

$$ABC,\ ACB,\ CAB$$

$BA$ (index 1, odd): insert $C$ left→right

$$CBA,\ BCA,\ BAC$$

Exactly as in the problem statement.

Deriving the recurrence

Let:

$n$ = number of letters
$L$ = largest letter
$p$ = position of $L$ (0-indexed from the left)
$r$ = rank of the permutation after removing $L$

Then:

if $r$ is even, $L$ travels right→left, so the block offset is

$$(n-1)-p$$

if $r$ is odd, $L$ travels left→right, so the block offset is

$$p$$

Thus:

$$R(P)=n\cdot r + b$$

where

$$b= \begin{cases} (n-1)-p & \text{if } r \text{ even}\[4pt] p & \text{if } r \text{ odd} \end{cases}$$

This gives an $O(n^2)$ recursive ranking algorithm.

2. Python implementation

def sjt_rank(word):
    """
    Return the 0-based index of `word`
    in Steinhaus-Johnson-Trotter order.
    """

    def rank_recursive(letters):
        n = len(letters)

        # Base case
        if n <= 1:
            return 0

        # Largest letter
        largest = max(letters)

        # Position of largest letter
        pos = letters.index(largest)

        # Remove largest letter
        reduced = [x for x in letters if x != largest]

        # Rank of reduced permutation
        r = rank_recursive(reduced)

        # Offset within this block
        if r % 2 == 0:
            offset = (n - 1) - pos
        else:
            offset = pos

        return n * r + offset

    return rank_recursive(list(word))

# Verify examples
print(sjt_rank("CBA"))      # 3
print(sjt_rank("BELFRY"))   # 59

# Compute Project Euler answer
target = "NOWPICKBELFRYMATHS"
print(sjt_rank(target))

3. Code walkthrough

Base case

if n <= 1:
    return 0

A single letter requires no swaps.

Find the largest letter

largest = max(letters)
pos = letters.index(largest)

SJT recursion depends on the position of the current largest letter.

Reduce the problem

reduced = [x for x in letters if x != largest]
r = rank_recursive(reduced)

Remove the largest letter and recursively compute the rank of the remaining permutation.

Determine movement direction

if r % 2 == 0:
    offset = (n - 1) - pos
else:
    offset = pos

Even subrank → largest letter sweeps right→left.

Odd subrank → largest letter sweeps left→right.

Combine block number and offset

return n * r + offset

Each recursive block contains exactly $n$ permutations.

4. Verification

Small examples:

$ABC \to CBA$

Sequence:

$$ABC \to ACB \to CAB \to CBA$$

So answer is $3$, matching the code.

For BELFRY, the code gives:

$$59$$

matching the problem statement exactly.

For:

$$\texttt{NOWPICKBELFRYMATHS}$$

the computation gives:

$$3832914911887589$$

This magnitude is reasonable: there are

$$18! \approx 6.4\times 10^{15}$$

possible permutations, so a rank of $3.8\times10^{15}$ is plausible and within range.

Answer: 3832914911887589