การเรียงลำดับแบบแพนเค้ก

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

การเรียงลำดับแบบแพนเค้ก (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 - รูปสามเหลี่ยมด้านบนอ่านตามแถว

อ้างอิง[แก้]