26!

어떤 분이 A에서 Z까지 모든 알파벳 26자로 이루어진 모든 경우의 수를 출력하는 프로그램을 만들 수 없느냐고 문의해서 "안돼요"라고 답을 보냈다.

일단 26!은 1부터 26까지 모두 곱한 수이다. !은 굉장히 빨리 커지는 함수인데, 4!이나 5!정도를 생각하고서 26!을 상상했다면 그 어마어마한 규모에 놀랄수밖에 없다. 26!이 얼마나 큰지 생각해 보고 싶다면, 일단 1부터 26까지 사이에 있는 정수에는 10과 같거나 보다 큰 정수가 17개나 있다. 10을 17번만 곱해도 10경이다. 

스털링의 공식을 사용하면 대략의 크기를 추측해 볼 수 있는데, 아니면 그냥 구글에 검색하면 된다.

26! = 4 x 10^26

4뒤에 0을 26개 정도 붙여야 얼추 비슷한 값이 나온다는 뜻이다. 

일단 그정도의 경우의 수가 있는데, 이걸 저장하기 위해 필요한 하드디스크 용량은 얼마나 될까? 26글자로 이루어진 문자열이므로 대략 10을 28번정도 곱한 크기의 글자를 저장해야 하는데, 영어 1글자가 1바이트이므로 10^28바이트의 용량이 필요하다.

1 GB = 10^9 Byte

1 TB = 10^12 Byte

1 PB = 10^15 Byte

1 EB = 10^18 Byte

1 ZB = 10^21 Byte

1 YB = 10^24 Byte

대략 1만 욕토바이트 정도.

요새 1 TB하드디스크가 10만원 안쪽으로 살 수 있는데, 대량구매로 1 TB에 만원이라 치고, 그렇다고 쳐도 저장공간을 확보하기 위해서 필요한 예산은 1 해 원이다. 우리나라 한해 예산을 1천조원이라고 가정해도 그보다 10만배 더 큰 예산이다.

저정도의 용량을 채우려면 1페타플롭스 정도 되는 컴퓨터를 사용해도 백만년 정도 출력해야 가능하다.

자, 그건 그렇다 치고.

A부터 Z까지 알파벳으로 이루어진 모든 경우의 수를 출력하려면 이론적으로는 어떻게 하면 될까?

몇가지 알고리즘을 생각해 볼 수 있다. 

일단 밑바닥부터 생각한다면, 

A를 생각하고 여기에 B를 추가하면 AB와 BA가 있다. 그 두가지 경우에 대해 C를 추가하여 AB로부터 CAB, ACB, ABC를 만들고, BA로부터는 CBA, BCA, BAC를 만들어 낸다. 그렇게 만들어진 여섯가지 경우에 대해 D를 추가하고. 등등. 이런식으로 중간에 하나씩 끼워넣는 방법을 이용하여 만들어낼 수 있다.

두번째로, 순수하게 정말 permutation의 의미를 생각해서 만드는 방법인데, ABCD...XYZ까지 다 써놓고, 1번과 2번을 바꾼 것, 1번과 3번을 바꾼 것, ... 이렇게 해서 1번 바꿔서 만든 모든 문자열을 추가하고, 1번과 2번을 바꾸고 1번과 3번을 바꾸고, ... 이렇게 해서 2번 바꿔서 만든 모든 문자열을 추가하고, ...

이렇게 해서 모든 경우의 수를 출력시킬 수 있다.

세번째로, 대충 만들어도 된다고 하면 아무거나 ABCD...XYZ까지 다 써놓고, 26개의 난수를 생성하면서 그 위치에 있는 문자를 뽑아서 만들면 된다. 필요한만큼 만들고, 같은거 나오면 버리면 된다. 물론 난수가 제대로 생성되었다면 4*10^26개의 경우의 수 중에 겹치는 것이 나올 가능성은 거의 없다.

이렇게 세가지 정도의 알고리즘을 생각해 볼 수 있다. 물론 이 알고리즘들은 널리 알려져 있는 방법들이다. 실제로 구현된 코드는 구글에서 permutation과 원하는 프로그래밍 언어 이름으로 검색하면 매우 많이 나오기 때문에 생략한다.