Reversal Sort
A prefix reversal of a permutation pi reverses the first k elements. The pancake number P(n) is the maximum over all permutations of S_n of the minimum number of prefix reversals needed to sort. De...
Problem Statement
This archive keeps the full statement, math, and original media on the page.
Recall the blancmange function from Problem 226: $T(x) = \displaystyle \sum\limits_{n = 0}^\infty\dfrac{s(2^nx)}{2^n}$, where $s(x)$ is the distance from $x$ to the nearest integer.
For positive integers $k, t, r$, we write $$F(k, t, r) = (2^{2k} - 1)T\left(\frac{(2^t + 1)^r}{2^k + 1}\right).$$ It can be shown that $F(k, t, r)$ is always an integer.
For example, $F(3, 1, 1) = 42$, $F(13, 3, 3) = 23093880$ and $F(103, 13, 6) \equiv 878922518\pmod {1\,000\,062\,031}$.
Find $F(10^{18} + 31, 10^{14} + 31, 62)$. Give your answer modulo $1\,000\,062\,031$.
Problem 889: Reversal Sort
Mathematical Analysis
Definition
A prefix reversal reverses positions :
Theorem 1 (Pancake Numbers)
is known for small :
| 1 | 0 |
| 2 | 1 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 7 |
| 7 | 8 |
| 8 | 9 |
| 9 | 10 |
| 10 | 11 |
Theorem 2 (Gates-Papadimitriou Bounds)
The lower bound is due to Heydari and Sudborough (1997). The upper bound of was shown by Chitturi et al. (2009).
Theorem 3 (BFS Computation)
The distances can be computed by BFS on the Cayley graph of with generators . This graph has vertices and is vertex-transitive.
Lemma (Breakpoint Lower Bound)
A breakpoint in is a position where (with and ). Then:
where is the number of breakpoints, since each reversal removes at most 2 breakpoints.
Concrete Numerical Examples
: All Permutations
| Sorting sequence | ||
|---|---|---|
| (1,2,3) | 0 | already sorted |
| (1,3,2) | 1 | … actually on last 2: need giving … |
| (2,1,3) | 1 | |
| (2,3,1) | 2 | … Let me redo |
| (3,1,2) | 2 | … |
| (3,2,1) | 1 |
Distribution: : 1, : 3, : 2. Total . Average: .
: Distance Distribution
| Count | Permutations | |
|---|---|---|
| 0 | 1 | identity |
| 1 | 3 | |
| 2 | 6 | |
| 3 | 11 | |
| 4 | 3 |
Total: . Sum of distances: . Average: .
The Burnt Pancake Problem
A variant where each pancake also has a “burnt” side. Sorting requires both correct order and correct orientation. The burnt pancake number satisfies and .
Cayley Graph Structure
The pancake graph (Cayley graph of with prefix reversal generators) has several notable properties:
- Vertex-transitive: all vertices look the same (by group symmetry)
- -regular: each vertex has degree (reversals of length 2 through )
- Diameter:
- Hamiltonian: conjectured (and verified for small ) to be Hamiltonian
Diameter Bounds Summary
| Bound | Value | Source |
|---|---|---|
| Lower bound | Heydari-Sudborough 1997 | |
| Upper bound | Chitturi et al. 2009 | |
| Conjectured |
Average Distance
The average sorting distance grows roughly as for some constant .
Complexity Analysis
| Method | Time | Space |
|---|---|---|
| BFS on | ||
| Lower bound (breakpoints) | per permutation | |
| A* search with heuristic |
BFS is feasible only for or so.
Answer
Code
Each problem page includes the exact C++ and Python source files from the local archive.
/*
* Problem 889: Reversal Sort (Pancake Sorting)
* BFS on permutation graph to compute pancake distances.
*/
#include <bits/stdc++.h>
using namespace std;
int pancake_number(int n) {
vector<int> identity(n);
iota(identity.begin(), identity.end(), 1);
map<vector<int>, int> dist;
dist[identity] = 0;
queue<vector<int>> q;
q.push(identity);
int max_d = 0;
while (!q.empty()) {
auto perm = q.front(); q.pop();
int d = dist[perm];
max_d = max(max_d, d);
for (int k = 2; k <= n; k++) {
auto np = perm;
reverse(np.begin(), np.begin() + k);
if (dist.find(np) == dist.end()) {
dist[np] = d + 1;
q.push(np);
}
}
}
return max_d;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << "=== Pancake Numbers ===" << endl;
for (int n = 1; n <= 8; n++) {
int P = pancake_number(n);
cout << "P(" << n << ") = " << P << endl;
}
cout << "\nAnswer: P(8) = " << pancake_number(8) << endl;
return 0;
}
"""
Problem 889: Reversal Sort (Pancake Sorting)
Prefix reversal sorting, pancake numbers, BFS on permutation graph.
"""
from itertools import permutations
from collections import deque
def prefix_reverse(perm, k):
"""Reverse the first k elements of perm."""
return perm[:k][::-1] + perm[k:]
def pancake_bfs(n):
"""BFS from identity to find distances of all permutations of S_n."""
identity = tuple(range(1, n + 1))
dist = {identity: 0}
queue = deque([identity])
while queue:
perm = queue.popleft()
d = dist[perm]
for k in range(2, n + 1):
new_perm = prefix_reverse(perm, k)
if new_perm not in dist:
dist[new_perm] = d + 1
queue.append(new_perm)
return dist
def breakpoints(perm):
"""Count breakpoints: positions where |pi[i] - pi[i+1]| != 1."""
n = len(perm)
extended = [0] + list(perm) + [n + 1]
b = sum(1 for i in range(len(extended) - 1) if abs(extended[i] - extended[i+1]) != 1)
return b
# --- Verification ---
print("=== Pancake BFS ===")
for n in range(1, 7):
dist = pancake_bfs(n)
P_n = max(dist.values())
total_dist = sum(dist.values())
avg = total_dist / len(dist)
# Distance distribution
dist_counts = {}
for d in dist.values():
dist_counts[d] = dist_counts.get(d, 0) + 1
print(f" n={n}: P(n)={P_n}, avg={avg:.3f}, dist={dict(sorted(dist_counts.items()))}")
print("\n=== Breakpoint Lower Bound (n=4) ===")
dist4 = pancake_bfs(4)
for perm in sorted(dist4.keys())[:10]:
d = dist4[perm]
b = breakpoints(perm)
lb = (b + 1) // 2
print(f" {perm}: d={d}, breakpoints={b}, lb={lb}, "
f"{'OK' if d >= lb else 'FAIL'}")
assert d >= lb
print("\n=== Known Pancake Numbers ===")
known = {1: 0, 2: 1, 3: 3, 4: 4, 5: 5, 6: 7}
for n, expected in known.items():
dist = pancake_bfs(n)
P_n = max(dist.values())
print(f" P({n}) = {P_n}, expected {expected}: {'OK' if P_n == expected else 'FAIL'}")
assert P_n == expected
answer = max(pancake_bfs(6).values())
print(f"\nAnswer: P(6) = {answer}")
# --- 4-Panel Visualization ---