# Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough copies of the graph where n=3 with additions of 4 in certain places (where, and how is this defined?). But these copies aren't exact, and I can't find any detail on Wikipedia except for that it is indeed recursively defined. I'm asking with a view possibly to be able to generate a graph algorithmically for n>=4 recursively.

Here is a graph for n=4 (so there are 4! / 24 possible configurations of pancakes, and thus 24 nodes in the graph). Here it is for n=4, on this Wikipedia article: https://en.wikipedia.org/wiki/Pancake_graph.

See this Wikipedia article for more on Pancake Sorting - https://en.wikipedia.org/wiki/Pancake_sorting.

• Please edit your question to provide more context and define your terms/notation. I don't know what Pn is supposed to represent; can you edit your question to make it self-contained? – D.W. Sep 24 '18 at 0:17
• Have added new links to the post. – Schmetterling Sep 24 '18 at 19:58

From Wikipedia:

The pancake graph $$P_n$$ or $$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.

$$P_n$$ can be constructed from $$n$$ copies of $$P_{n-1}$$. We can construct $$P_4$$ from $$P_3$$, which looks like:

We start by making 4 copies of $$P_3$$ and numbering them 1 through $$n$$. Let's look at one particular copy and call it copy $$i$$. For each node in that instance of $$P_{n-1}$$, replace $$i$$ with $$n$$ and then append $$i$$ to the end of each sequence. For the $$n$$th copy, we don't have to do any replacing and can simply append $$n$$ to the end.

For example, for the 2nd copy of $$P_3$$ we'll first replace all the 2s with 4s and then append 2 to the end:

We now have a graph with nodes for all of the permutations of the elements from 1 to 4, and we have edges between sequences that can be transformed into one another by flipping a proper prefix. Edges from $$P_{n-1}$$ are still valid in $$P_n$$ because the only thing we've done is relabel and append a suffix.

Now go through each node and add a new edge going to the node corresponding to flipping the entire sequence. For example, (4,3,1,2) gets connected to (2,1,3,4), (1,2,3,4) gets connected to (4,3,2,1), etc.

The final graph for $$P_4$$ as shown in the Wikipedia article linked in the question looks like:

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. ... I'm asking with a view possibly to be able to generate a graph algorithmically for n>=4 recursively.

A webpage providing source code for pancake sorting in over 50 different languages is here: "Sorting algorithms/Pancake sort" at the Rosetta Code website.

See the paper: "Some relations on prefix reversal generators of the symmetric and hyperoctahedral group" (Jun 7 2018), by Saúl A. Blanco and Charles Buehrle:

Page 1: "The best upper and lower bound known today for the general case appeared in [5] and [12], respectively. Combined, one has that

$$15 \left \lfloor \frac{n}{14} \right \rfloor \le f(n) \le \frac{18n}{11} + O(1).$$

Computing the pancake number for a given n is a complicated task. To our knowledge, the exact value of f(n) is only known for 1 ≤ n ≤ 19 (see [2, 6, 7, 12, 18]). In fact, determining the minimum number needed to sort a stack of pancakes is an NP-hard problem [4], though 2-approximation algorithms exists [10].

[2] Shogo Asai, Yuusuke Kounoike, Yuji Shinano, and Keiichi Kaneko. Computing the Diameter of 17-Pancake Graph Using a PC Cluster, pages 1114–1124. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.

[4] Laurent Bulteau, Guillaume Fertin, and Irena Rusu. Pancake flipping is hard. J. Comput. System Sci., 81(8):1556–1574, 2015.

[5] B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, and W. Voit. An (18/11)$$n$$ upper bound for sorting by prefix reversals. Theoret. Comput. Sci., 410(36):3372–3390, 2009.

[6] Josef Cibulka. On average and highest number of flips in pancake sorting. Theoret. Comput. Sci., 412(8-10):822–834, 2011.

[7] David S. Cohen and Manuel Blum. On the problem of sorting burnt pancakes. Discrete Appl. Math., 61(2):105–120, 1995.

[10] Johannes Fischer and Simon W. Ginzinger. A 2-Approximation Algorithm for Sorting by Prefix Reversals, pages 415–425. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.

[12] Mohammad H. Heydari and I. Hal Sudborough. On the diameter of the pancake network. J. Algorithms, 25(1):67–94, 1997.

[18] Y. Kounoike, K. Kaneko, and Y. Shinano. Computing the diameters of 14- and 15-pancake graphs. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), Dec 2005.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

// pancake sort template (calls predicate to determine order)
template <typename BidIt, typename Pred>
void pancake_sort(BidIt first, BidIt last, Pred order)
{
if (std::distance(first, last) < 2) return; // no sort needed

for (; first != last; --last)
{
BidIt mid = std::max_element(first, last, order);
if (mid == last - 1)
{
continue; // no flips needed
}
if (first != mid)
{
std::reverse(first, mid + 1); // flip element to front
}
std::reverse(first, last); // flip front to final position
}
}

// pancake sort template (ascending order)
template <typename BidIt>
void pancake_sort(BidIt first, BidIt last)
{
pancake_sort(first, last, std::less<typename std::iterator_traits<BidIt>::value_type>());
}

int main()
{
std::vector<int> data;
for (int i = 0; i < 20; ++i)
{
data.push_back(i); // generate test data
}
std::random_shuffle(data.begin(), data.end()); // scramble data

std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";

pancake_sort(data.begin(), data.end()); // ascending pancake sort

std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}


Output:

4 10 11 15 14 16 17 1 6 9 3 7 19 2 0 12 5 18 13 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19