การเรียงลำดับแบบแพนเค้ก
การเรียงลำดับแบบแพนเค้ก (Pancake sorting) เป็นการเรียงลำดับสำหรับปัญหาทางคณิตศาสตร์ การเรียงแถวอย่างเป็นระเบียบของแพนเค้กในการสั่งซื้อโดยการเรียงตามขนาด โดยแผ่นที่ใหญ่สุดจะอยู่ข้างล่าง แผ่นเล็กสุดอยู่ข้างบน เมื่อไม้พายสามารถแทรกที่จุดใดๆในกองนั้นและใช้ในการพลิกแพนเค้กทั้งหมด จำนวนแพนเค้กจึงจำเป็นสำหรับการกำหนดจำนวนขั้นต่ำในการกล่าวถึงปัญหานี้ ผู้ที่กล่าวถึงรูปแบบการเรียงนี้เป็นคนแรก คือ American geometer Jacob E. Goodman. ซึ่งแตกต่างจากขั้นตอนวิธีการเรียงลำดับแบบดั้งเดิม ดังนั้น การเรียงลำดับแบบแพนเค้ก จึงเป็นการเรียงลำดับตามการกลับรายการให้น้อยที่สุด ตัวแปรของปัญหา คือ แพนเค้กที่ถูกเผาไหม้ ซึ่งแต่ละแผ่นของแพนเค้กจะมีด้านที่ถูกเผาไหม้ และแพนเค้กทั้งหมดต้องวางทับกันโดยมีด้านที่เผาไหม้อยู่ด้านล่าง
ปัญหาการเรียงแบบแพนเค้กในสตริง[แก้]
ลำดับที่มีการผกผันในการเปลี่ยนแปลงตำแหน่ง เช่น "สตริง" เป็นลำดับที่เป็นสัญลักษณ์ในการทำซ้ำได้ และในการทำซ้ำนี้ อาจจะลดจำนวนการพลิกตำแหน่งที่จำเป็นในการจัดเรียง Chitturi and Sudborough (2010) and Hurkens et al.(2007) แสดงให้เห็นว่า ความซับซ้อนของการเปลี่ยนสตริงที่เข้ากันได้กับอีกจำนวนหนึ่งที่มีจำนวนน้อยที่สุดของการผกผันตำแหน่ง คือ NP-complete พวกเขายังให้ขอบเขตที่เหมือนกัน Hurkens et al ให้ใช้อัลกอริทึมที่แน่นอนในการจัดเรียงไบนารีและการค้นหาแบบไตรภาค สตริง Chitturi (2011) ได้พิสูจน์ว่า ความซับซ้อนของการเปลี่ยนแปลงสตริงที่เข้ากันได้กับจำนวนที่น้อยที่สุดในการผกผันตำแหน่ง - ปัญหาแพนเค้กที่ถูกเผาไหม้บนสตริงเป็น NP-complete
ขั้นตอนการแก้ปัญหา[1][แก้]
1.ต้องเริ่มต้นสั่งแพนเค้กจากเล็กที่สุด (ด้านบน) ถึงใหญ่ที่สุด (ด้านล่าง) จึงจะสามารถจัดเรียงตามลำดับได้
2.สามารถทำการพลิกได้ทั้งกอง
3.เมื่อต้องการพลิกแพนเค้กที่ด้านล่างสุดของสแต็ค ต้องพลิกไปที่ด้านบนสุด (จากนั้นพลิกกลับไปที่ด้านล่าง)
4.หากต้องการสั่งซื้อแพนเค้กแต่ละแพนเค้กจะต้องพลิกขึ้นไปด้านบนและพลิกไปยังตำแหน่งสุดท้าย
กราฟแพนเค้ก[แก้]
กราฟแพนเค้ก n คือกราฟที่มีจุดยอดของสัญลักษณของ n สัญลักษณ์ตั้งแต่ 1 ถึง n และขอบของมันจะได้รับระหว่างการแทนที่ด้วยคำนำหน้า เป็นกราฟปกติที่มี n! vertices ระดับของ n-1 ปัญหาการจัดเรียงแพนเค้กและปัญหาเพื่อให้ได้เส้นผ่านศูนย์กลางของแพนเค้กกราฟมีค่าเท่ากัน
กราฟแพนเค้กของมิติ n, Pn สามารถสร้างขึ้นได้จาก n สำเนาของ Pn-1 โดยการกำหนดองค์ประกอบที่แตกต่างจากชุด {1, 2, ... , n} เป็นส่วนต่อท้ายของแต่ละสำเนา
เส้นรอบวง : g(Pn) = 6, if n > 2.
เนื่องจากกราฟแพนเค้กมีคุณสมบัติที่น่าสนใจหลายอย่างเช่น โครงสร้างสมมาตรและการเรียกซ้ำขนาดเล็กและเส้นผ่าศูนย์กลางเมื่อเทียบกับขนาดของกราฟความสนใจเป็นจำนวนมากสำหรับโมเดลเครือข่ายการเชื่อมต่อแบบคู่ขนานสำหรับคอมพิวเตอร์แบบขนาน เมื่อเราพิจารณาแพนเค้กกราฟเป็นแบบจำลองของเครือข่ายการเชื่อมต่อเส้นผ่าศูนย์กลางของกราฟเป็นตัวชี้วัดที่แสดงถึงความล่าช้าในการสื่อสาร
ลำดับจำนวนเต็มที่เกี่ยวข้อง[แก้]
จำนวนสแต็คของความสูงที่ต้องการ n ที่ต้องการ flips k ที่ไม่เหมือนใคร
| 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 | 7046318 | 40309555 | 184992275 | 639783475 | 1525125357 | 2183056566 | 1458653648 | 186874852 | 2001 |
ลำดับจาก The Online Encyclopedia of Integer Sequences of Neil Sloane:
OEIS A058986 - จำนวนพลิกสูงสุด
OEIS A067607 - จำนวนสแต็คที่ต้องการจำนวนพลิกสูงสุด (ด้านบน)
OEIS A078941 - จำนวน flips สูงสุดสำหรับ stack "burnt"
OEIS A078942 - จำนวน flips สำหรับเรียงลำดับ "burnt-side-on-top"
OEIS A092113 - รูปสามเหลี่ยมด้านบนอ่านตามแถว