본문 바로가기
영문 위키피디아 번역

(번역) Superpermutation

by 다움위키 2024. 4. 9.
Original article: w:Superpermutation

 

조합론적(combinatorial) 수학(mathematics)에서, n 기호에 대한 초월순열은 n 기호의 각 순열(permutation)을 부분문자열(substring)로 포함하는 문자열(string)입니다. 자명한(trivial) 초월순열은 단순히 함께 나열된 모든 각 순열로 구성될 수 있지만, 초월순열은 역시 중첩이 허용되기 때문에 (n = 1의 자명한 경우를 제외하고) 더 짧게 될 수 있습니다. 예를 들어, n = 2의 경우에서, 초월순열 1221는 모든 가능한 순열, 12와 21을 포함하지만, 더 짧은 문자열, 121는 역시 두 순열을 모두 포함합니다.

1 ≤ n ≤ 5에 대해, n 기호에 대한 가장 작은 초월순열은 길이 1! + 2! + … + n! (OEIS에서 수열 A180632)을 가집니다. 처음 넷의 가장 작은 초월순열은 각각 길이 1, 3, 9, 및 33을 가지며, 문자열 1, 121, 123121321, 및 123412314231243121342132413214321을 형성합니다. 어쨌든, n = 5에 대해, 길이 153을 가지는 가장 작은 여러 초월순열이 있습니다. 하나의 그러한 초월순열은 아래에 나와 있지만, 같은 길이의 또 다른 것이 문자열의 후반부 (굵은 2 뒤에 있음)에서 4와 5를 모두 전환함으로써 얻어질 수 있습니다:

  • 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

n > 5의 경우에 대해, 가장 작은 초월순열은 아직 입증되지도 않았고 그것들을 찾는 패턴도 없지만, 그것들에 대한 아래쪽과 위쪽 경계는 발견되어 왔습니다.

Finding superpermutations

차수 \(n\)의 초월순열을 생성하는 가장 공통적인 알고리듬 중 하나는 재귀 알고리듬입니다. 먼저, 차수 \(n-1\)의 초월순열은 그것들이 초월순열에 나타난 방법의 순서에서 개별 순열로 나뉩니다. 그들 순열의 각각은 그런-다음 두 복사본 사이에 n번째 기호를 추가된 자신의 복사본 옆에 배치됩니다. 마지막으로, 각각의 결과 구조가 서로 옆에 배치되고 인접한 모든 동일한 기호가 병합됩니다.

예를 들어, 차수 3의 초월순열은 2 기호를 갖는 것으로부터 생성될 수 있습니다; 초월순열 121에서 시작하고 그것을 순열 12와 21로 나누면, 순열이 복사되고 12312와 21321으로 배치됩니다. 그것들이 함께 배치되어 1231221321이 생성되고, 중간에 동일한 인접 2가 병합되어 123121321이 생성되며, 이것은 실제로 차수 3의 초월순열입니다. 이 알고리듬은 5보다 작거나 같은 모든 n에 대해 가장 짧은 가능한 초월순열을 생성하지만, n이 그 이상으로 증가함에 따라 가장 짧은 가능한 것보다 점점 더 길어집니다.

초월순열을 찾는 또 다른 방법은 각 순열이 꼭짓점(vertex)이고 모든 각 순열이 가장자리에 의해 연결된 그래프(graph)를 생성하는 데 존재합니다. 각 가장자리는 그것과 결합된 가중(weight)을 가집니다; 가중은 한 순열의 끝에 더해져서 (시작에서 문자의 같은 숫자를 버려서) 다른 순열을 생성할 수 있는 문자 수를 확인하여 계산됩니다. 예를 들어, 123에서 312까지의 가장자리는 123 + 12 = 12312 = 312이므로 가중치 2를 가집니다. 생성된 그래프를 통한 임의의 해밀턴 경로(hamiltonian path)는 초월순열이고, 가장 작은 가중을 갖는 경로를 찾는 문제는 여행하는 세일즈맨 문제(traveling salesman problem)의 형식이 됩니다. 길이 \(1! + 2! + \ldots + n!\)보다 작은 초월순열의 첫 번째 예제는 로빈 휴스턴(Robin Houston)에 의한 이 방법에 대한 컴퓨터 검색을 사용하여 찾아졌습니다.

Lower and upper bounds

6개 이상의 기호에 대한 가장 작은 초월순열을 찾는 알고리듬은 아직 해결되지 않은 상태입니다. 어쨌든, 몇 가지 증명이 시간이 지남에 따라 문제의 강력한 위쪽과 아래쪽 경계(upper and lower bounds)를 점차적으로 강화해 왔습니다.

Lower bounds, or the Haruhi problem

2011년 9월, 4chan의 과학 & 수학 ("/sci/") 게시판에 익명 게시물은 n 기호(n ≥ 2)에 대한 가장 작은 초월순열은 적어도 길이 n! + (n−1)! + (n−2)! + n − 3임을 입증했습니다. 일본 애니메이션 시리즈 The Melancholy of Haruhi Suzumiya에 대한 참조에서, 그 문제는 이미지 보드에 "하루히 문제"로 표시되었습니다: 만약 여러분이 모든 각 가능한 순서에서 시리즈의 첫 번째 시즌의 14 에피소드를 보기를 원하면, 여러분이 시청해야 할 에피소드 중 가장 짧은 문자열은 무엇일까요? 이 아래쪽 경계에 대해 증명은 수학자이자 컴퓨터 과학자 로빈 휴스턴이 그것에 대한 트윗한 후 2018년 10월에 일반 대중의 관심을 끌었습니다. 2018년 10월 25일, 로빈 휴스턴, 제이 팬톤, 및 빈스 배터는 On-Line Encyclopedia of Integer Sequences (OEIS)에서 이 증명의 세련된 버전을 게시했습니다. "Anonymous 4chan poster"로 공인된, 이 증명의 출판된 버전은 Engen and Vatter (2019)에 나타납니다. 특히 "하루히 문제" (14개 기호에 대한 경우)에 대해, 아래쪽 경계는 현재 적어도 93,884,313,611이고 위쪽 경계는 많아야 93,924,230,411입니다.

Upper bounds

2018년 10월 20일, 대칭 그룹(symmetric group)의 케일리 그래프(Cayley graph)를 통해 해밀턴 경로(Hamiltonian path)를 구성하기 위해 아론 윌리엄스(Aaron Williams)에 의한 구성을 적응함으로써, 그레그 이건(Greg Egan)은 길이 n! + (n−1)! + (n−2)! + (n−3)! + n − 3의 초월순열을 생성하는 알고리듬을 고안했습니다. 2018년까지, 이것들은 n ≥ 7에 대해 알려진 가장 작은 초월순열이었습니다. 어쨌든, 2019년 2월 1일, 보그단 코안다(Bogdan Coanda)는 길이 5907, (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1의 n=7에 대해 초월순열을 찾았다고 발표했으며, 이것이 새로운 기록입니다. 2019년 2월 27일, 로빈 휴스턴에 의해 개발된 아이디어를 사용하여, 이건은 길이가 5906의 n = 7에 대한 초월순열을 생성했습니다. 유사한 더 짧은 초순열이 역시 n > 7의 값에 대해 존재하는지 여부는 열린 문제로 남아있습니다. n = 7에 대한 현재 최상의 아래쪽 경계 (위 섹션 참조)은 여전히 5884입니다.

Further reading

References

 

External links

 

관련글

티스토리툴바