0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Sep 24 '18 at 0:17
  • $\begingroup$ Have added new links to the post. $\endgroup$ – Schmetterling Sep 24 '18 at 19:58
0
$\begingroup$

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:

enter image description here

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:

enter image description here

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:

enter image description here

$\endgroup$
0
$\begingroup$

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.

The Rosetta Code C++ implementation is:

#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 

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.