Pancake sorting

The pancake sorting problem was first posed by Jacob E. Goodman, writing under the pseudonym "Harry Dweighter" ("harried waiter").^[10]

Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.^[11][12]

The problem is notable as the topic of the only well-known mathematics paper by Microsoft founder Bill Gates (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co-authored with Christos Papadimitriou. Published in 1979, it describes an efficient algorithm for pancake sorting.^[3] In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen), co-authored with Manuel Blum, concerned the burnt pancake problem.^[13]

The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals,^[14] the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,^[15] and also proven to be approximable in polynomial time to within the approximation factor 1.375.^[16]

Pancake graphs

An n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. It is a regular graph with n! vertices, its degree is n−1. The pancake sorting problem and the problem to obtain the diameter of the pancake graph are equivalent.^[17]

The pancake graph of dimension n, P_n can be constructed recursively from n copies of P_n−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Their girth:

${\displaystyle g(P_{n})=6{\text{, if }}n>2}$.

The γ(P_n) genus of P_n is:^[18]

${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1}$

Since pancake graphs have many interesting properties such as symmetric and recursive structures, small degrees and diameters compared against the size of the graph, much attention is paid to them as a model of interconnection networks for parallel computers.^[19][20][21] When we regard the pancake graphs as the model of the interconnection networks, the diameter of the graph is a measure that represents the delay of communication.^[22][23]

The pancake graphs are Cayley graphs (thus are vertex-transitive) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively sparse (compared to e.g. hypercubes).^[18]

Algorithm

An example of the pancake sorting algorithm is given below in Python. The code is similar to bubble sort or selection sort.

def flip(arr, k: int) -> None:
    left = 0
    while left < k:
        arr[left], arr[k] = arr[k], arr[left]
        k -= 1
        left += 1

def max_index(arr, k: int) -> int:
    index = 0
    for i in range(k):
        if arr[i] > arr[index]:
            index = i
    return index

def pancake_sort(arr) -> None:
    n = len(arr)
    while n > 1:
        maxdex = max_index(arr, n)
        if maxdex != n - 1:
            if maxdex != 0:
                flip(arr, maxdex)
            flip(arr, n - 1)
        n -= 1

arreglo = [15, 8, 9, 1, 78, 30, 69, 4, 10]
pancake_sort(arreglo)
print(arreglo)

Related integer sequences

Number of stacks of given height n that require unique flips k  to get sorted

Height n	k
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	2	2	1
4	1	3	6	11	3
5	1	4	12	35	48	20
6	1	5	20	79	199	281	133	2
7	1	6	30	149	543	1357	1903	1016	35
8	1	7	42	251	1191	4281	10561	15011	8520	455
9	1	8	56	391	2278	10666	38015	93585	132697	79379	5804
10	1	9	72	575	3963	22825	106461	377863	919365	1309756	814678	73232
11	1	10	90	809	6429	43891	252737	1174766	4126515	9981073	14250471	9123648	956354	6
12	1	11	110	1099	9883	77937	533397	3064788	14141929	49337252	118420043	169332213	111050066	13032704	167
13	1	12	132	1451	14556	130096	1030505	7046321	40309555	184992275	639783475	1525125357	2183056566	1458653648	186874852	2001

Sequences from The Online Encyclopedia of Integer Sequences:

• OEIS: A058986 – maximum number of flips
• OEIS: A067607 – number of stacks requiring the maximum number of flips (above)
• OEIS: A078941 – maximum number of flips for a "burnt" stack
• OEIS: A078942 – the number of flips for a sorted "burnt-side-on-top" stack
• OEIS: A092113 – the above triangle, read by rows

References