초순열

수학 조합론에서 n개 기호의 초순열(Superpermutation)이란 n개의 기호에 대한 모든 순열을 서브스트링으로 포함하고 있는 문자열을 뜻한다. 자명한 초순열은 단순히 모든 순열을 그냥 일렬로 나열해 만들 수 있지만, 초순열의 경우 문자열의 중복이 허용되기 때문에 (n=1인 자명한 경우를 제외하면) 더 짧은 초순열이 존재할 수 있다. 예를 들어 n=2인 경우 가능한 모든 순열인 12와 21을 그대로 나열해 1221라는 초순열을 만들 수도 있지만, 더 짧은 121이라는 초순열도 12와 21을 모두 포함한다.

1 ≤ n ≤ 5일 경우 n개 기호를 가진 가장 짧은 초순열은 1! + 2! + … + n! 임이 밝혀져 있다. 처음 4번째까지의 가장 짧은 초순열은 각각 길이 1의 1, 길이 3의 121, 길이 9의 123121321, 길이 33의 123412314231243121342132413214321이다. 하지만 n = 5부터는 길이가 153인 가장 짧은 초순열이 여러 개 있다. 이 초순열 중 하나는 다음과 같으며 문자열 후반부(굵게 쓰인 2 이후)에 있는 4와 5를 모두 바꾸면 같은 길이의 또 다른 초순열을 얻을 수 있다.

12345123­41523412­53412354­12314523­14253142­35142315­42312453­12435124­31524312­54312134­52134251­34215342­13542132­45132415­32413524­13254132­14532143­52143251­432154321

n > 5인 경우 가장 짧은 초순열이 무엇인지 아직 증명되지 않았으며 이 문제를 스즈미야 하루히 문제라고 한다.

 초순열 찾기 
300px|섬네일|기호가 2개인 초순열로부터 기호가 3개인 초순열을 만드는 다이어그램

차 초순열을 생성하는 가장 보편적인 알고리즘은 재귀법이다. 먼저 차 초순열을 초순열에 나타난 순서대로 개별 순열로 분리한다. 그 다음 각 순열을 2개로 복사한 후 그 복사본 사이에 n번째 기호를 끼워넣는다. 마지막으로 새로 만들어진 각 순열을 인접한 같은 기호는 하나로 병합하는 방식으로 다시 일렬로 합친다.

예를 들어, 기호가 3개인 초순열은 기호가 2개인 초순열로부터 만들 수 있다. 우선 초순열 121을 순열 (12)와 (21) 2개로 나눈다. 그 후 각 순열을 (1212), (2121) 2개로 복사한 후 그 사이에 3을 끼워넣으면 (12312), (21321)이 된다. 이후 두 순열을 하나로 합치면 1231221321의 초순열이 되는데 가운데 2라는 중복된 숫자를 합치면 최종적으로 123121321이라는 순열이 나오며 이는 실제로 3개 기호를 가진 초순열이다. 이 알고리즘은 n이 5보다 작은 모든 경우에서 가장 짧은 초순열을 생성할 수 있지만 n이 그 이상으로 증가하면 가능한 가장 짧은 초순열보다 점점 더 긴 초순열이 나온다.

초순열을 찾는 또 다른 방법으로는 각 순열이 꼭짓점이고 모든 순열을 전부 선으로 연결하는 그래프를 만드는 문제로 변환하는 것이다. 각 선에는 가중치가 있는데 이 가중치는 한 순열의 끝에 얼마나 많은 문자를 추가해야 다른 순열을 만들 수 있는지(시작과 같은 중복된 수는 제거하고 계산) 확인하여 계산한다. 예를 들어, 123에서 312로 연결하는 선은 123 + 12 = 12312 = 312이므로 가중치 2를 가진다. 이렇게 만들어진 그래프를 모두 통과하는 해밀턴 경로가 초순열이며, 가장 작은 가중치를 가진 경로를 찾는 문제(=가장 작은 길이의 초순열을 찾는 문제)는 외판원 문제와 연결된다. 길이가 보다 짧은 초순열의 첫 예시는 로빈 휴스턴이 이 방법을 컴퓨터를 통해 계산하여 처음으로 발견했다.

 초순열의 하한 (하루히 문제) 
2011년 9월, 인터넷 포럼 4chan에서 과학과 수학 게시판("/sci/")에서 익명의 사용자가 n개 기호(n ≥ 2)를 가진 가장 작은 초순열의 길이는 최소 n! + (n−1)! + (n−2)! + n − 3라고 주장했다. 이 문제는 일본의 애니메이션 시리즈인 《스즈미야 하루히의 우울》 2006년 방영 작품이 시계열 순서로 방영된 것이 아닌, 비선형 서사로 방영되었다는 사실과 관련해 하루히 문제(The Haruhi Problem)라는 이름으로 알려졌다. 하루히 문제란 "시리즈 첫 시즌 14개 회차를 가능한 모든 순서로 시청하고 싶다면, 가장 짧은 에피소드로 시청하는 데 필요한 시간은 얼마인가?"이다. 이 하한에 대한 증명은 2018년 10월 수학자이자 컴퓨터 과학자인 로빈 휴스턴이 트위터에 올린 트윗을 통해 대중에게 관심을 끌었다. 2018년 10월 25일에는 로빈 휴스턴, 제이 팬튼, 빈스 배터가 증명의 더욱 개선된 판본을 온라인 정수열 사전(OEIS)에 게시했다. 증명 논문은 2021년 제1저자가 "익명의 4chan 유저"로 표기되어  논문으로 발표되었다.

특히 하루히 문제인 14개 기호의 경우 현재까지 밝혀진 하한과 상한은 각각 93,884,313,611회와 93,924,230,411회이다. 이는 가능한 모든 순서로 시리즈를 시청하러면 약 430만년이 걸림을 뜻한다.

 초순열의 상한 
2018년 10월 20일에는 대칭군의 케일리 그래프를 통해 해밀턴 경로를 그리는 애런 윌리엄스의 이론을 응용하여 SF 작가이자 수학자인 그레그 이건이 길이 n! + (n−1)! + (n−2)! + (n−3)! + n − 3의 초순열을 생성하는 알고리즘을 개발했다. 2018년까지 이 길이는 n ≥ 7에 대해서 알려진 가장 짧은 초순열이었다. 하지만 2019년 2월 1일 보드간 콴다가 n = 7에 대해서 길이 5907인 초순열을 발견하며 이 상한은 (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1로 변경되었다. 2019년 2월 17일 이건은 로빈 휴스턴이 발견한 아이디어를 사용해 n = 7에 대해서 길이 5906인 더 짧은 초순열을 발견했다. n > 7에 대해서도 이와 유사한 더 짧은 초순열이 존재하는지는 아직까지 증명되지 않은 미해결 문제이다. 현재 n = 7의 하한값은 5884이다.

 같이 보기 
 초패턴
 더브라윈 순서

 각주 

 참고 문헌 

 외부 링크 
 The Minimal Superpermutation Problem - Nathaniel Johnston's blog

 The original 4chan post on /sci/, archived on warosu.org
 Tweet by Robin Houston, which brought attention to the 4chan post
 Article about the problem of finding short superpermutations in Quanta Magazine

분류:열거조합론
분류:순열