Siêu hoán vị

Trong toán học tổ hợp, siêu hoán vị trên n dấu là xâu mà mọi hoán vị của n dấu đó đều là xâu con của xâu đó. Mặc dù xâu siêu hoán vị tầm thường có thể tìm thấy ngay bằng cách nối tất cả các hoán vị lại với nhau, ta có thể tìm thấy các siêu hoán vị có độ dài nhỏ hơn (ngoại trừ trường hợp n = 1) vì các hoán vị được phép chèn lên nhau. Ví dụ chẳng hạn, trong trường hợp n = 2, siêu hoán vị 1221 chứa mọi hoán vị cần có (12 và 21), nhưng mà xâu ngắn hơn 121 cũng chứa đủ hai hoán vị đó.

Hiện đã được chứng minh rằng cho 1 ≤ n ≤ 5, siêu hoán vị cho n dấu có độ dài 1! + 2! + ... + n! (dãy số A180632 trong bảng OEIS). Bốn siêu hoán vị cho 1, 2, 3 và 4 dấu có độ dài tương ứng là 1, 3, 9, và 33, và các xâu tương ứng là 1, 121, 123121321, và 123412314231243121342132413214321. Tuy nhiên, đối với n = 5, có nhiều xâu hoán vị nhỏ nhất có độ dài 153. Một trong các số đó được biểu diễn ở dưới đây, một xâu khác có cùng độ dài có thể thu được từ xâu này bằng cách đổi tất cả các vị trí của tất cả của bốn và năm ở nửa sau của xâu (đằng sau số 2 in đậm):^[1]

123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

Đối với n > 5, siêu hoán vị nhỏ nhất chưa được tìm thấy và cũng chưa có cách để nhận dạng và tìm chúng, nhưng đã có các cận trên và cận dưới cho độ dài các xâu đó.

Tìm siêu hoán vị

Sơ đồ hình thành siêu hoán vị của 3 dấu từ siêu hoán vị có hai dấu.

Một trong những thuật toán hay dùng để tìm siêu hoán vị có $n$ dấu là thuật toán đệ quy. Đầu tiên, siêu hoán vị có cấp $n-1$ được tách thành các hoán vị theo thứ tự xuất hiện trong siêu hoán vị. Sau đó, mỗi hoán vị này sau đó được đặt ngay cạnh bản sao của chúng cùng với ký hiệu thứ n đứng giữa.Cuối cùng, các xâu thu được được xếp cạnh nhau và các dấu giống nhau và cạnh nhau thì sẽ hợp về còn một.^[2]

Lấy ví dụ, siêu hoán vị cấp 3 có thể được tạo từ siêu hoán vị có 2 dấu; bắt đầu từ siêu hoán vị 121 và tách nó thành hai hoán vị 12 và 21, các hoán vị được sao lại và thêm vào thành 12312 và 21321. Sau đó đặt chúng cùng nhau thu được 1231221321, Các dấu 2 đứng giữa hợp lại với nhau thành siêu hoán vị 123121321 có 3 dấu. Thuật toán này cho phép tìm siêu hoán vị ngắn nhất cho mọi n nhỏ hơn hoặc bẳng 5, tuy nhiên kết quả sẽ càng trở nên dài hơn siêu hoán vị ngắn nhất khi n lớn dần.^[2]

Cách khác để tìm siêu hoán vị là dựa trên xây đồ thị mà mỗi hoán vị là một đỉnh, và các hoán vị được nối với nhau bằng các cạnh có trọng số. Trọng số của mỗi cạnh được tính bằng cách đếm số dấu có thể thêm vào cuối hoán vị (và bỏ cùng số lượng đó ở đầu hoán vị) để thành hoán vị kia.^[2] Lấy ví dụ, cạnh từ 123 đến 312 có trọng số 2 vì 123 + 12 = 12312 = 312. Bất kỳ đường đi Hamilton qua đồ thị này đều là siêu hoán vị, và bài toán tìm đường đi có trọng số ngắn nhất trở thành bài toán người đi du lịch. Siêu hoán vị đầu tiên có độ dài nhỏ hơn $1!+2!+\ldots +n!$ được tìm thấy trên máy tính theo phương pháp này là của Robin Houston.^[3]

Cận dưới và cận trên

Thuật toán tìm siêu hoán vị nhỏ nhất cho xâu có nhiều hơn hoặc bằng 6 dấu hiện vẫn chưa được tìm thấy.^[4] Tuy nhiên, có nhiều bài chứng minh gần đây đã thu hẹp lại cận trên và cận dưới của bài toán.^[5]

Cận dưới, hay bài toán Haruhi

Vào tháng 9 năm 2011, một người dùng ẩn danh trên board Science & Math ("/sci/") của 4chan đã chứng minh được rằng siêu hoán vị nhỏ nhất trên n dấu (với n ≥ 2) có độ dài ít nhất n! + (n−1)! + (n−2)! + n − 3.^[4] Lấy cảm hứng từ bộ anime Haruhi Suzumiya của Nhật Bản, bài toán trên diễn đàn được gọi là "bài toán Haruhi":^[6] nếu bạn muốn xem hết 14 tập của mùa đầu tiên của bộ trong mọi thứ tự có thể, thì xâu ngắn nhất của các tập mà bạn cần xem là gì?^[7] Bài chứng minh cho cận dưới này nhận được chú ý của cộng đồng vào tháng 10 năm 2018, sau khi nhà toán học và khoa học máy tính Robin Houston đã tweet về nó.^[4] Vào ngày 25 tháng 10 năm 2018, Robin Houston, Jay Pantone, và Vince Vatter đã tải bản chứng minh đã được sửa lên bảng tra cứu dãy số nguyên trực tuyến (OEIS).^[7]^[8] Phiên bản được xuất bản có ghi danh "người dùng nặc danh 4chan" và xuất hiện trong bài viết của Engen và Vatter (2019).^[9] Riêng "bài toán Haruhi" (trường hợp có 14 dấu), cận dưới và cận trên hiện tại tương ứng là 93,884,313,611 và 93,924,230,411.^[4] Điều này có nghĩa là để xem hết 14 tập đầu tiên trong mọi thứ tự có thể sẽ mất khoảng 4 triệu năm.

Cận trên

Vào ngày 20 tháng 10 năm 2018, sử dụng cách xây dựng của Aaron Williams cho các đường đi Hamilton qua đồ thị Cayley của nhóm đối xứng,^[10] tác giả khoa học viễn tưởng và là nhà toán học Greg Egan đã đưa thuật toán có thể sinh ra siêu hoán vị có độ dài n! + (n−1)! + (n−2)! + (n−3)! + n − 3.^[2] Tính đến hết năm 2018, đây là các siêu hoán vị duy nhất được biết đến và tìm thấy cho n ≥ 7. Tuy nhiên, vào ngày 2 tháng 1 năm 2019, Bogdan Coanda đã công bố tìm được siêu hoán vị cho n=7 có độ dài 5907, hay (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, lập kỷ lục mới cho giá trị cận.^[2] Vào 27 tháng 2 năm 2019, sử dụng các ý tưởng được phát triển bởi Robin Houston, Egan đã tìm ra siêu hoán vị cho n = 7 có độ dài 5906.^[2] Câu hỏi rằng liệu có siêu hoán vị nào nhỏ hơn tồn tại cho n > 7 vẫn là câu hỏi mở. Cận dưới lớn nhất cho n = 7 vẫn là 5884.

Xem thêm

Siêu mẫu hoán vị, hoán vị chứa tất cả các hoán vị của n dấu là mẫu hoán vị
Dãy De Bruijn, bài toán tương tự với dãy cyclic

Đọc thêm

Ashlock, Daniel A.; Tillotson, Jenett (1993), “Construction of small superpermutations and minimal injective superstrings”, Congressus Numerantium, 93: 91–98, Zbl 0801.05004
Anonymous 4chan Poster; Houston, Robin; Pantone, Jay; Vatter, Vince (25 tháng 10 năm 2018). “A lower bound on the length of the shortest superpattern” (PDF). On-Line Encyclopedia of Integer Sequences.

Tham khảo

^ Johnston, Nathaniel (28 tháng 7 năm 2013). “Non-uniqueness of minimal superpermutations”. Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016/j.disc.2013.03.024. S2CID 12018639. Zbl 1368.05004. Truy cập ngày 16 tháng 3 năm 2014.
^ ^a ^b ^c ^d ^e ^f Egan, Greg (20 tháng 10 năm 2018). “Superpermutations”. gregegan.net. Truy cập ngày 15 tháng 1 năm 2020.
^ Houston, Robin (21 August 2014). "Tackling the Minimal Superpermutation Problem". arΧiv:1408.5108 [math.CO].
^ ^a ^b ^c ^d Griggs, Mary Beth (24 tháng 10 năm 2018). “An anonymous 4chan post could help solve a 25-year-old math mystery”. The Verge.
^ Houston, Robin (21 tháng 8 năm 2014). “Tackling the Minimal Superpermutation Problem”. arXiv:1408.5108 [cs, math].
^ Anon, - San (17 tháng 9 năm 2011). “Permutations Thread III ニア愛”. Warosu.
^ ^a ^b Klarreich, Erica (5 tháng 11 năm 2018). “Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem”. Quanta Magazine (bằng tiếng Anh). Truy cập ngày 21 tháng 6 năm 2020.
^ Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (25 tháng 10 năm 2018). “A lower bound on the length of the shortest superpattern” (PDF). OEIS. Truy cập ngày 27 tháng 10 năm 2018.
^ Engen, Michael; Vatter, Vincent (2021), “Containing all permutations”, American Mathematical Monthly, 128 (1): 4–24, doi:10.1080/00029890.2021.1835384
^ Aaron, Williams (2013). "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arΧiv:1307.2549v3 [math.CO].