요세푸스 순열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

전산학에서 요세푸스 순열(- 順列, Josephus permutation)은 다음과 같이 정의한다.

mn이 자연수이고, m < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 나가서 m번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 m번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 순서가 (m, n) 요세푸스 순열이다.

예를 들어 (3,7) 요세푸스 순열은 {3,6,2,7,5,1,4}이다.

요세푸스 순열을 구하는 O(n)의 시간복잡도를 가지는 알고리즘이 존재한다.

이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.