드 브루인 수열 계산기

기호 k가지로 만들 수 있는 길이 n의 조합 kⁿ가지가 모두, 그리고 한 번씩만 나타나는 순환 수열입니다. 길이는 정확히 kⁿ이며 고리이므로 끝에서 앞으로 감아 읽는 창까지 셉니다. k=2, n=3이면 00010111이 그런 수열입니다.

입력을 끊지 않고 마지막 네 자리만 보는 자물쇠라면 그렇습니다. 하나씩 끊어 넣으면 10,000가지 × 4번 = 40,000번이지만, 드 브루인 수열 10,000자리를 죽 누르고 앞 세 자리를 다시 붙이면 10,003번에 모든 조합이 지나갑니다. 다만 실제 도어락은 대개 확인 버튼이 있거나 몇 번 틀리면 잠기므로 그대로 통하지는 않습니다.

리라스–프레도릭센(FKM) 방법을 씁니다. n의 약수 길이인 린던 워드를 사전순으로 이어 붙이면 사전순으로 가장 앞선 드 브루인 수열이 된다는 정리에 기댄 방법이며, 재귀 한 번으로 kⁿ 글자를 만듭니다. 드 브루인 그래프의 오일러 회로를 찾아도 같은 답이 나옵니다.

드 브루인 그래프에서 모든 꼭짓점의 들어오는 변과 나가는 변의 개수가 k로 같기 때문입니다. 길이 n−1짜리 조합을 꼭짓점, 길이 n짜리 조합을 변으로 두면 이 그래프가 나오는데, 들어오고 나가는 개수가 같고 연결되어 있으면 오일러 회로가 반드시 있습니다. 그 회로를 따라 읽은 것이 곧 드 브루인 수열입니다.

(k!)^(k^(n−1)) ÷ kⁿ개입니다. k=2, n=3이면 2⁴÷8 = 2개뿐이지만 k=2, n=5면 2,048개로 금세 폭발합니다. 이 도구는 그중 사전순으로 가장 앞선 것 하나를 만듭니다.

카드 마술, 로봇의 위치 인식, DNA 조립, 회전 각도 인코더 같은 데 쓰입니다. 공통점은 「전체를 보지 않고 연속된 몇 칸만 봐도 지금 어디인지 알 수 있게」 만드는 것입니다. 모든 창이 한 번씩만 나오므로 창 하나가 곧 위치를 가리키기 때문입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.