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! .  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):

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ị 

Một trong những thuật toán hay dùng để tìm siêu hoán vị có  dấu là thuật toán đệ quy. Đầu tiên, siêu hoán vị có cấp  đượ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.

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.

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. 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  được tìm thấy trên máy tính theo phương pháp này là của Robin Houston.

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. 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.

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. 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": 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ì? 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ó. 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). 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 .
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. Đ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,  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.  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. 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. 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

Tham khảo

Liên kết ngoài
The Minimal Superpermutation Problem - Nathaniel Johnston's blog
 
 The 4chan post on /sci/, archived on warosu.org
 Tweet by Robin Houston, which brought attention to the 4chan post

Tổ hợp trên từ
Liệt kê tổ hợp
Hoán vị