ซูเปอร์เพอร์มิวเทชัน

Q: ข้อมูลสำคัญเกี่ยวกับ ซูเปอร์เพอร์มิวเทชัน

ในคณิตศาสตร์เชิงการจัดเรียง (combinatorial mathematics ) ซูเปอร์เพอร์มูเทชัน (superpermutation)บนสัญลักษณ์n ตัว คือ สตริงที่ประกอบด้วยการเรียงสับเปลี่ยน ทุกแบบ ของ สัญลักษณ์ n ตัว.

Q: ขอบเขตล่าง หรือปัญหาฮารุฮิ

ในเดือนกันยายน พ.ศ. 2554 ผู้โพสต์นิรนามบน บอร์ด Science & Math (" /sci/ ") ของ 4chan ได้พิสูจน์ว่าซูเปอร์เพอร์มูเทชันที่เล็กที่สุดบน สัญลักษณ์ n ตัว ( n ≥ 2) มีความยาวอย่างน้อย n ! + ( n −1)! + ( n −2)!

ในคณิตศาสตร์เชิงการจัดเรียง (combinatorial mathematics ) ซูเปอร์เพอร์มูเทชัน (superpermutation)บนสัญลักษณ์n ตัว คือ สตริงที่ประกอบด้วยการเรียงสับเปลี่ยน ทุกแบบ ของ สัญลักษณ์ n ตัว เป็นสตริงย่อยในขณะที่ ซูเปอร์เพอร์มูเทชัน แบบง่ายๆ สามารถสร้างได้จากการนำการเรียงสับเปลี่ยนทุกแบบมาต่อกัน ซูเปอร์เพอร์มูเทชันยังสามารถสั้นกว่าได้ (ยกเว้นกรณีง่ายๆ ที่n = 1) เพราะอนุญาตให้มีการซ้อนทับกันได้ ตัวอย่างเช่น ในกรณีn = 2 ซูเปอร์เพอร์มูเทชัน 1221 ประกอบด้วยการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด (12 และ 21) แต่สตริงที่สั้นกว่า 121 ก็ประกอบด้วยการเรียงสับเปลี่ยนทั้งสองแบบเช่นกัน

ได้มีการแสดงให้เห็นแล้วว่าสำหรับ 1 ≤ n ≤ 5 การเรียงสับเปลี่ยนซูเปอร์เพอร์มูเทชันที่เล็กที่สุดบน สัญลักษณ์ nตัวมีความยาว 1! + 2! + … + n ! (ลำดับA180632ในOEIS ) ^{[ 1 ]} การเรียงสับเปลี่ยนซูเปอร์เพอร์มูเทชันที่เล็กที่สุดสี่รายการแรกมีความยาว 1, 3, 9 และ 33 ตามลำดับ ซึ่งก่อให้เกิดสตริง 1, 121, 123121321 และ 123412314231243121342132413214321 อย่างไรก็ตาม สำหรับn = 5 มีการเรียงสับเปลี่ยนซูเปอร์เพอร์มูเทชันที่เล็กที่สุดหลายรายการที่มีความยาว 153 การเรียงสับเปลี่ยนซูเปอร์เพอร์มูเทชันหนึ่งรายการแสดงไว้ด้านล่าง ในขณะที่อีกรายการหนึ่งที่มีความยาวเท่ากันสามารถหาได้โดยการสลับเลขสี่และเลขห้าทั้งหมดในครึ่งหลังของสตริง (หลังเลข2 ที่เป็นตัวหนา ): ^{[ 2 ]}

12345123 4152341253412354 1231452314253142 35142315 42312453 1243512431524312 5431 2 134 52134251 34215342 13542132 4513241532413524 1325413214532143 52143251 432154321

สำหรับกรณีที่n > 5 ยังไม่มีการพิสูจน์ซูเปอร์เพอร์มิวเทชันที่เล็กที่สุด หรือรูปแบบในการค้นหาซูเปอร์เพอร์มิวเทชันเหล่านั้น แต่ได้มีการค้นพบขอบเขตล่างและขอบเขตบนสำหรับซูเปอร์เพอร์มิวเทชันเหล่านั้นแล้ว

การค้นหาซูเปอร์เพอร์มูเทชัน

แผนภาพแสดงการสร้างซูเปอร์เพอร์มูเทชันที่มี 3 สัญลักษณ์ จากซูเปอร์เพอร์มูเทชันที่มี 2 สัญลักษณ์

หนึ่งในอัลกอริธึมที่ใช้กันทั่วไปในการสร้างซูเปอร์เพอร์มิวเทชันของลำดับ $n$ เป็นอัลกอริธึมแบบเรียกซ้ำ ขั้นแรกคือการเรียงสับเปลี่ยนลำดับชั้น $n-1$ จะถูกแยกออกเป็นลำดับการเรียงสับเปลี่ยนแต่ละแบบตามลำดับที่ปรากฏในซูเปอร์เพอร์มูเทชัน จากนั้นแต่ละลำดับการเรียงสับเปลี่ยนเหล่านั้นจะถูกวางไว้ข้างๆ สำเนาของตัวเองโดยมี การเพิ่มสัญลักษณ์ที่ nเข้าไประหว่างสำเนาทั้งสอง สุดท้าย โครงสร้างที่ได้แต่ละอันจะถูกวางไว้ข้างๆ กันและสัญลักษณ์ที่เหมือนกันที่อยู่ติดกันทั้งหมดจะถูกรวมเข้าด้วยกัน^{[ 3 ]}

ตัวอย่างเช่น สามารถสร้างซูเปอร์เพอร์มูเทชันลำดับที่ 3 ได้จากเพอร์มูเทชันที่มี 2 สัญลักษณ์ โดยเริ่มจากซูเปอร์เพอร์มูเทชัน 121 และแยกออกเป็นเพอร์มูเทชัน 12 และ 21 จากนั้นคัดลอกเพอร์มูเทชันและวางเป็น 12312 และ 21321 นำมาวางรวมกันเพื่อสร้าง 1231221321 และรวมเลข 2 ที่อยู่ติดกันตรงกลางเข้าด้วยกันเพื่อสร้าง 123121321 ซึ่งเป็นซูเปอร์เพอร์มูเทชันลำดับที่ 3 อย่างแท้จริง อัลกอริทึมนี้ส่งผลให้ได้ซูเปอร์เพอร์มูเทชันที่สั้นที่สุดที่เป็นไปได้สำหรับn ทั้งหมด ที่น้อยกว่าหรือเท่ากับ 5 แต่จะยาวขึ้นเรื่อยๆ กว่าซูเปอร์เพอร์มูเทชันที่สั้นที่สุดที่เป็นไปได้เมื่อnเพิ่มขึ้นเกินกว่านั้น^{[ 3 ]}

อีกวิธีหนึ่งในการหาซูเปอร์เพอร์มูเทชันคือการสร้างกราฟที่แต่ละเพอร์มูเทชันเป็นจุดยอดและทุกเพอร์มูเทชันเชื่อมต่อกันด้วยขอบ แต่ละขอบมีน้ำหนักที่เกี่ยวข้อง น้ำหนักคำนวณโดยดูว่าสามารถเพิ่มอักขระได้กี่ตัวที่ส่วนท้ายของเพอร์มูเทชันหนึ่ง (โดยตัดอักขระจำนวนเท่ากันออกจากจุดเริ่มต้น) เพื่อให้ได้เพอร์มูเทชันอื่น^{[ 3 ]}ตัวอย่างเช่น ขอบจาก 123 ไปยัง 312 มีน้ำหนัก 2 เพราะ 123 + 12 = 12312 = 312 เส้นทางแฮมิลโทเนียน ใดๆ ผ่านกราฟที่สร้างขึ้นเป็นซูเปอร์เพอร์มูเทชัน และปัญหาของการหาเส้นทางที่มีน้ำหนักน้อยที่สุดกลายเป็นรูปแบบหนึ่งของปัญหาพนักงานขายเดินทางตัวอย่างแรกของซูเปอร์เพอร์มูเทชันที่เล็กกว่าความยาว $1!+2!+\ldots +n!$ ค้นพบวิธีการนี้โดยใช้การค้นหาด้วยคอมพิวเตอร์โดย Robin Houston

ขอบเขตล่าง หรือปัญหาฮารุฮิ

ในเดือนกันยายน พ.ศ. 2554 ผู้โพสต์นิรนามบนบอร์ด Science & Math (" /sci/ ") ของ4chanได้พิสูจน์ว่าซูเปอร์เพอร์มูเทชันที่เล็กที่สุดบน สัญลักษณ์ n ตัว ( n ≥ 2) มีความยาวอย่างน้อยn ! + ( n −1)! + ( n −2)! + n − 3 ^[⁴^]โดยอ้างอิงถึงซีรีส์อนิเมะ ญี่ปุ่น เรื่อง The Melancholy of Haruhi Suzumiyaโดยเฉพาะอย่างยิ่งข้อเท็จจริงที่ว่าเดิมทีออกอากาศในรูปแบบการเล่าเรื่องที่ไม่เป็นเส้นตรงปัญหาดังกล่าวจึงถูกนำเสนอในกระดานภาพในชื่อ "ปัญหาฮารุฮิ": ^[⁵^]หากคุณต้องการดู 14 ตอนของซีซั่นแรกของซีรีส์ในลำดับที่เป็นไปได้ทั้งหมด ลำดับตอนที่สั้นที่สุดที่คุณต้องดูจะเป็นเท่าใด? ^[⁶^]การพิสูจน์ขอบเขตล่างนี้ได้รับความสนใจจากสาธารณชนในเดือนตุลาคม พ.ศ. 2561 หลังจากที่นักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ Robin Houston ทวีตเกี่ยวกับเรื่องนี้^[⁴^]เมื่อวันที่ 25 ตุลาคม 2018 Robin Houston, Jay Pantone และ Vince Vatter ได้โพสต์เวอร์ชันที่ปรับปรุงแล้วของบทพิสูจน์นี้ในสารานุกรมลำดับจำนวนเต็มออนไลน์ (OEIS) โดยระบุชื่อผู้เขียนคนแรกเป็น "ผู้โพสต์นิรนามจาก 4chan" ^[⁶^]^[¹^]

สำหรับ "ปัญหาฮารุฮิ" โดยเฉพาะ (กรณีที่มีสัญลักษณ์ 14 ตัว) ขอบเขตล่างและขอบเขตบนในปัจจุบันคือ 93,884,313,611 และ 93,924,230,411 ตามลำดับ^{[ 4 ]}ซึ่งหมายความว่าการดูซีรีส์ในทุกลำดับที่เป็นไปได้จะต้องใช้เวลาประมาณ 4.3 ล้านปี^{[ 7 ]}

ขอบเขตบน

เมื่อวันที่ 20 ตุลาคม 2018 โดยการดัดแปลงโครงสร้างโดย Aaron Williams สำหรับการสร้างเส้นทางแฮมิลโทเนียนผ่านกราฟ Cayleyของกลุ่มสมมาตร [ ⁸^] นักเขียนนิยายวิทยาศาสตร์และนักคณิตศาสตร์^Greg Eganได้คิดค้นอัลกอริทึมเพื่อสร้างซูเปอร์เพอร์มูเทชันที่มีความยาวn ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3 ^{[ 3 ]}จนถึงปี 2018 ซูเปอร์เพอร์มูเทชันเหล่านี้เป็นซูเปอร์เพอร์มูเทชันที่เล็กที่สุดที่รู้จักสำหรับn ≥ 7 อย่างไรก็ตาม เมื่อวันที่ 1 กุมภาพันธ์ 2019 Bogdan Coanda ประกาศว่าเขาพบซูเปอร์เพอร์มูเทชันสำหรับ n=7 ที่มีความยาว 5907 หรือ ( n ! + ( n −1 )! + ( n −2)! + ( n −3)! + n − 3) − 1 ซึ่งเป็นสถิติใหม่^{[ 3 ]}เมื่อวันที่ 27 กุมภาพันธ์ 2019 โดยใช้แนวคิดที่พัฒนาโดย Robin Houston Egan ได้สร้างซูเปอร์เพอร์มูเทชันสำหรับn = 7 ที่มีความยาว 5906 ^{[ 3 ]}ยังคงเป็นคำถามที่เปิดอยู่ว่าซูเปอร์เพอร์มูเทชันที่สั้นกว่าที่คล้ายกันนี้มีอยู่สำหรับค่าn > 7 หรือไม่ ขอบล่างที่ดีที่สุดในปัจจุบัน (ดูส่วนด้านบน) สำหรับn = 7 ยังคงเป็น 5884

ดูเพิ่มเติม

ซูเปอร์แพทเทิร์นคือการเรียงสับเปลี่ยนที่ประกอบด้วยการเรียงสับเปลี่ยนของสัญลักษณ์n ตัวใน รูปแบบแพทเทิร์นการเรียงสับเปลี่ยน
ลำดับเดอ บรูอิน (De Bruijn sequence)เป็นปัญหาที่คล้ายคลึงกันกับลำดับวัฏจักร (cyclic sequences)

อ่านเพิ่มเติม

Ashlock, Daniel A.; Tillotson, Jenett (1993), "การสร้างซูเปอร์เพอร์มูเทชันขนาดเล็กและซูเปอร์สตริงแบบฉีดขั้นต่ำ", Congressus Numerantium , 93 : 91– 98, Zbl 0801.05004
ผู้โพสต์นิรนามจาก 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25 ตุลาคม 2018). "ขอบเขตล่างของความยาวของซูเปอร์แพทเทิร์นที่สั้นที่สุด" (PDF) . สารานุกรมลำดับจำนวนเต็มออนไลน์ .

ลิงก์ภายนอก

ปัญหาการเรียงสับเปลี่ยนซูเปอร์ขั้นต่ำสุด - บล็อกของนาธาเนียล จอห์นสตัน
Grime, James (29 มกราคม 2018). "Superpermutations - Numberphile" (วิดีโอ) . YouTube . Brady Haran . สืบค้นเมื่อ1 กุมภาพันธ์ 2018 .
โพสต์ต้นฉบับจาก 4chan บน /sci/ซึ่งถูกเก็บถาวรไว้ใน warosu.org
ทวีตของ Robin Houston ที่ทำให้โพสต์บน 4chan ได้รับความสนใจ
บทความเกี่ยวกับปัญหาการค้นหาซูเปอร์เพอร์มูเทชันแบบสั้นในนิตยสาร Quanta

[ 2 ]

[ 3 ]

[

[ 7 ]

8