Pancake sorting

<h2 id="the-pancake-problems">The pancake problems</h2>
<h3>The original pancake problem</h3>
The minimum number of flips required to sort any stack of n pancakes has been shown to lie between ⁠15/14⁠n and ⁠18/11⁠n (approximately 1.07n and 1.64n), but the exact value is not known.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The simplest pancake sorting algorithm performs at most 2n − 3 flips. In this algorithm, a kind of <a href="/facts/Selection_sort/uIsGffcr">selection sort</a>, we bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes.
In 1979, <a href="/facts/Bill_Gates/z16t4m7s">Bill Gates</a> and <a href="/facts/Christos_Papadimitriou/rXflR4or">Christos Papadimitriou</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> gave a lower bound of ⁠17/16⁠n (approximately 1.06n) flips and an upper bound of ⁠(5n+5)/3⁠. The upper bound was improved, thirty years later, to ⁠18/11⁠n by a team of researchers at the <a href="/facts/University_of_Texas_at_Dallas/5l8T49fo">University of Texas at Dallas</a>, led by Founders Professor Hal Sudborough.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, thereby answering a question that had been open for over three decades.

<h3>The burnt pancake problem</h3>
In a variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. It is a signed permutation, and if a pancake i is "burnt side up" a negative element i` is put in place of i in the permutation. In 2008, a group of undergraduates built a <a href="/facts/DNA_computing/NfNV4obg">bacterial computer</a> that can solve a simple example of the burnt pancake problem by programming <a href="/facts/Escherichia_coli/nR4Gvl56">E. coli</a> to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large <a href="/facts/Parallel_computing/nQzcpzQt">parallel computing</a> platform. The bacteria report when they have solved the problem by becoming antibiotic resistant.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="the-pancake-problem-on-strings">The pancake problem on strings</h2>
The discussion above presumes that each pancake is unique, that is, the sequence on which the prefix reversals are performed is a <a href="/facts/Permutation/JSw9ukmv">permutation</a>. However, "strings" are sequences in which a symbol can repeat, and this repetition may reduce the number of prefix reversals required to sort. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with the minimum number of prefix reversals is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> (2011) proved that the complexity of transforming a compatible signed string into another with the minimum number of signed prefix reversals—the burnt pancake problem on strings—is NP-complete.

<h2 id="history">History</h2>
The pancake sorting problem was first posed by <a href="/facts/Jacob_E._Goodman/3rda4H2v">Jacob E. Goodman</a>, writing under the pseudonym "Harry Dweighter" ("harried waiter").<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
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.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
The problem is notable as the topic of the only well-known mathematics paper by <a href="/facts/Microsoft/nGIDDXdx">Microsoft</a> founder <a href="/facts/Bill_Gates/z16t4m7s">Bill Gates</a> (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co-authored with <a href="/facts/Christos_Papadimitriou/rXflR4or">Christos Papadimitriou</a>. Published in 1979, it describes an efficient algorithm for pancake sorting.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> In addition, the most notable paper published by <a href="/facts/Futurama/72FSdj0B">Futurama</a> co-creator <a href="/facts/David_X._Cohen/dbgbDyDM">David X. Cohen</a> (as David S. Cohen), co-authored with <a href="/facts/Manuel_Blum/fl3GKhvh">Manuel Blum</a>, concerned the burnt pancake problem.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
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,<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> and also proven to be approximable in polynomial time to within the approximation factor 1.375.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h2 id="pancake-graphs">Pancake graphs</h2>

Main article: <a href="/facts/Pancake_graph/m5y5eDHP">Pancake graph</a>
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 <a href="/facts/Regular_graph/j9dSoLE6">regular graph</a> with n! vertices, its degree is n−1. The pancake sorting problem and the problem to obtain the <a href="/facts/Diameter_(graph_theory)/EmQFKvqa">diameter</a> of the pancake graph are equivalent.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>
The pancake graph of dimension n, Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.
Their <a href="/facts/Girth_(graph_theory)/rPwRGgxj">girth</a>:

g
 (
 
 P
 
 n
 
 
 )
 =
 6
 
 , if 
 
 n
 >
 2
 
 
 {\displaystyle g(P_{n})=6{\text{, if }}n>2}
 
.
The γ(Pn) <a href="/facts/Graph_embedding/IyBA3ttM">genus</a> of Pn is:<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

n
        !
        
          (
          
            
              
                n
                −
                4
              
              6
            
          
          )
        
        +
        1
        ≤
        γ
        (
        
          P
          
            n
          
        
        )
        ≤
        n
        !
        
          (
          
            
              
                n
                −
                3
              
              4
            
          
          )
        
        −
        
          
            n
            2
          
        
        +
        1
      
    
    {\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.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a><a class="footnote-ref" id="fnref:20" href="#fn:20">20</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> 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.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>
The pancake graphs are <a href="/facts/Cayley_graph/QxoxNnys">Cayley graphs</a> (thus are <a href="/facts/Vertex-transitive_graph/042b7rD7">vertex-transitive</a>) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively <a href="/facts/Dense_graph/xFC7b7s9">sparse</a> (compared to e.g. <a href="/facts/Hypercube_graph/pwfGEl9J">hypercubes</a>).<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>

<h2 id="algorithm">Algorithm</h2>
An example of the pancake sorting algorithm is given below in <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a>. The code is similar to <a href="/facts/Bubble_sort/Go9JnLk2">bubble sort</a> or <a href="/facts/Selection_sort/uIsGffcr">selection sort</a>. 

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:
        maxidx = max_index(arr, n)
        if maxidx != n - 1:
            if maxidx != 0:
                flip(arr, maxidx)
            flip(arr, n - 1)
        n -= 1

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

<h2 id="related-integer-sequences">Related integer sequences</h2>
Number of stacks of given height n that require unique flips k  to get sorted<table><tbody><tr><th rowspan="2">Heightn</th><th colspan="16">k</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>1</td><td>2</td><td>2</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>1</td><td>3</td><td>6</td><td>11</td><td>3</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>1</td><td>4</td><td>12</td><td>35</td><td>48</td><td>20</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>6</th><td>1</td><td>5</td><td>20</td><td>79</td><td>199</td><td>281</td><td>133</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>7</th><td>1</td><td>6</td><td>30</td><td>149</td><td>543</td><td>1357</td><td>1903</td><td>1016</td><td>35</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>8</th><td>1</td><td>7</td><td>42</td><td>251</td><td>1191</td><td>4281</td><td>10561</td><td>15011</td><td>8520</td><td>455</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>9</th><td>1</td><td>8</td><td>56</td><td>391</td><td>2278</td><td>10666</td><td>38015</td><td>93585</td><td>132697</td><td>79379</td><td>5804</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>10</th><td>1</td><td>9</td><td>72</td><td>575</td><td>3963</td><td>22825</td><td>106461</td><td>377863</td><td>919365</td><td>1309756</td><td>814678</td><td>73232</td><td></td><td></td><td></td><td></td></tr><tr><th>11</th><td>1</td><td>10</td><td>90</td><td>809</td><td>6429</td><td>43891</td><td>252737</td><td>1174766</td><td>4126515</td><td>9981073</td><td>14250471</td><td>9123648</td><td>956354</td><td>6</td><td></td><td></td></tr><tr><th>12</th><td>1</td><td>11</td><td>110</td><td>1099</td><td>9883</td><td>77937</td><td>533397</td><td>3064788</td><td>14141929</td><td>49337252</td><td>118420043</td><td>169332213</td><td>111050066</td><td>13032704</td><td>167</td><td></td></tr><tr><th>13</th><td>1</td><td>12</td><td>132</td><td>1451</td><td>14556</td><td>130096</td><td>1030505</td><td>7046318</td><td>40309555</td><td>184992275</td><td>639783475</td><td>1525125357</td><td>2183056566</td><td>1458653648</td><td>186874852</td><td>2001</td></tr></tbody></table>
Sequences from <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">The Online Encyclopedia of Integer Sequences</a>:

<ul><li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A058986 – maximum number of flips</li>
<li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A067607 – number of stacks requiring the maximum number of flips (above)</li>
<li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A078941 – maximum number of flips for a "burnt" stack</li>
<li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A078942 – the number of flips for a sorted "burnt-side-on-top" stack</li>
<li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A092113 – the above triangle, read by rows</li></ul>

<h2 id="further-reading">Further reading</h2>

<ul><li>Chitturi, B.; Sudborough, H. (2010). <a href="https://www.researchgate.net/publication/221051667">"Prefix Reversals on Strings"</a>. Proceedings of the International Conference on Bioinformatics & Computational Biology. 2: 591–598.</li>
<li>Chitturi, B. (2011). "A Note on Complexity of Genetic Mutations". Discrete Math. Algorithm. Appl. 3 (3): 269–287. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1142%2FS1793830911001206">10.1142/S1793830911001206</a>.</li>
<li>Heydari, M. H.; Sudborough, I. H. (1997). "On the Diameter of the Pancake Network". Journal of Algorithms. 25 (1): 67–94. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjagm.1997.0874">10.1006/jagm.1997.0874</a>.</li>
<li>Hurkens, C.; van Iersel, L.; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Prefix Reversals on Binary and Ternary Strings". SIAM Journal on Discrete Mathematics. 21 (3): 592–611. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/0602456">math/0602456</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F060664252">10.1137/060664252</a>.</li>
<li><a href="/facts/Colva_Roney-Dougal/kXd6SDy2">Roney-Dougal, C.</a>; Vatter, V. (March 2010). <a href="http://plus.maths.org/issue54/features/colvatter/">"Of Pancakes, Mice and Men"</a>. Plus Magazine. 54.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.cut-the-knot.org/SimpleGames/Flipper.shtml">Cut-the-Knot: Flipping pancakes puzzle</a>, including a Java applet for the pancake problem and some discussion.</li>
<li><a href="http://www.math.uiuc.edu/~west/openp/pancake.html">Douglas B. West's "The Pancake Problems"</a></li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/PancakeSorting.html">"Pancake Sorting"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Singh, Simon (November 14, 2013). "Flipping pancakes with mathematics". The Guardian. Retrieved March 25, 2014. <a href="/wiki/Simon_Singh" target="_blank">/wiki/Simon_Singh</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824. <a href="9780262062824" target="_blank">9780262062824</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal". Discrete Mathematics. 27: 47–57. doi:10.1016/0012-365X(79)90068-2. <a href="/wiki/Bill_Gates" target="_blank">/wiki/Bill_Gates</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Archived from the original on February 14, 2012. Retrieved November 10, 2008. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established. <a href="https://web.archive.org/web/20120214070902/http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen" target="_blank">https://web.archive.org/web/20120214070902/http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (August 31, 2009). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi:10.1016/j.tcs.2008.04.045. <a href="https://doi.org/10.1016%2Fj.tcs.2008.04.045" target="_blank">https://doi.org/10.1016%2Fj.tcs.2008.04.045</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv:1111.0434. doi:10.1016/j.jcss.2015.02.003. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L (2008). "Engineering bacteria to solve the Burnt Pancake Problem". Journal of Biological Engineering. 2: 8. doi:10.1186/1754-1611-2-8. PMC 2427008. PMID 18492232. <a href="/wiki/Laurie_Heyer" target="_blank">/wiki/Laurie_Heyer</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Chitturi, Bhadrachalam (2011). "A Note on Complexity of Genetic Mutations". Discrete Mathematics, Algorithms and Applications. 03 (3): 269–286. doi:10.1142/S1793830911001206. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Dweighter, Harry (1975), "Elementary Problem E2569", Amer. Math. Monthly, 82 (10): 1009–1010, doi:10.2307/2318260, JSTOR 2318260 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Gargano, L.; Vaccaro, U.; Vozella, A. (1993). "Fault tolerant routing in the star and pancake interconnection networks". Information Processing Letters. 45 (6): 315–320. CiteSeerX 10.1.1.35.9056. doi:10.1016/0020-0190(93)90043-9. MR 1216942.. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Kaneko, K.; Peng, S. (2006). "Disjoint paths routing in pancake graphs". Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). pp. 254–259. doi:10.1109/PDCAT.2006.56. ISBN 978-0-7695-2736-9. S2CID 18777751.. <a href="978-0-7695-2736-9" target="_blank">978-0-7695-2736-9</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal". Discrete Mathematics. 27: 47–57. doi:10.1016/0012-365X(79)90068-2. <a href="/wiki/Bill_Gates" target="_blank">/wiki/Bill_Gates</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Cohen, D.S.; Blum, M. (1995). "On the problem of sorting burnt pancakes". Discrete Applied Mathematics. 61 (2): 105. doi:10.1016/0166-218X(94)00009-3. <a href="/wiki/David_X._Cohen" target="_blank">/wiki/David_X._Cohen</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Kaplan, H.; Shamir, R.; Tarjan, R.E. (1997). "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals". Proc. 8th ACM-SIAM SODA: 178–87. <a href="/wiki/Robert_Tarjan" target="_blank">/wiki/Robert_Tarjan</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Berman, P.; Karpinski, M. (1999). "On Some Tighter Inapproximability Results". Proc. 26th ICALP (1999). Lecture Notes in Computer Science. 1644: 200–09. <a href="/wiki/Marek_Karpinski" target="_blank">/wiki/Marek_Karpinski</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Berman, P.; Karpinski, M.; Hannenhalli, S. (2002). "1.375-Approximation Algorithms for Sorting by Reversals". Proc. 10th ESA (2002). Lecture Notes in Computer Science. 2461: 200–10. <a href="/wiki/Marek_Karpinski" target="_blank">/wiki/Marek_Karpinski</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006). "Computing the diameter of 17-pancake graph using a PC cluster". In Nagel, Wolfgang E.; Walter, Wolfgang V.; Lehner, Wolfgang (eds.). Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4128. Springer. pp. 1114–1124. doi:10.1007/11823285_117. ISBN 978-3-540-37783-2. <a href="978-3-540-37783-2" target="_blank">978-3-540-37783-2</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292. <a href="http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf" target="_blank">http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. CiteSeerX 10.1.1.363.4949. doi:10.1002/net.3230230403. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Bass, D.W.; Sudborough, I.H. (March 2003). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX 10.1.1.27.7009. doi:10.1016/S0743-7315(03)00033-9. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Berthomé, P.; Ferreira, A.; Perennes, S. (December 1996). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681. doi:10.1109/71.553290. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings. <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Quinn, M.J. (1994). Parallel Computing: Theory and Practice (second ed.). McGraw-Hill. <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292. <a href="http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf" target="_blank">http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
</ol>

Pancake sorting open-in-new

Pancake sorting