파이썬에서 순열을 구하는 몇 가지 방법

A~Z까지 알파벳으로 이뤄진 5글자 단어를 모두 검색해서 뭔가를 한다거나, 아들 이름 지을 때 성을 제외한 2글자에서 가능한 모든 조합을 하고 싶은 것 같은 경우가 있습니다. 여러 다양한 상황에서 전혀 주먹구구식 알고리즘이 안 나오고 그냥 NP-complete 문제를 위한 정공법으로 전수조사를 해야할 때면 순열을 만드는 것이 가장 간단한 경우가 많겠죠. 순열 만드는 것이 간단하면서도 뭐가 좋을지 고민을 좀 하게 만드는데, 그래서 파이썬에서 순열을 만들 때 쓸만한 방법을 대충 생각나는 것을 모아 봤습니다. ^_^

우선, 일반적으로 나오는 C언어 입문서에서처럼 다 풀어쓰기를 하면 보통 이런 식으로 구현될 것입니다.

뭔가 한 눈에 확 들어오는 간단함은 있지만, 반복 수가 변하는 경우에는 루프가 늘어나고, 별로 코드도 중복이 가득해 보이는 것이 그다지 멋있지 않습니다. 그래도, 일단 좀 더 파이썬 코드처럼 보이게 하기 위해 줄여 보면,

이제 1줄로 줄기는 했지만, 내부적으로는 구조는 1번과 다를 것이 없습니다. 반복횟수가 바뀌면 여전히 루프가 늘어납니다.
그래서, 루프를 1개로 줄이고, 보통 많이 쓰이는 나누기 나머지 나누기 나머지 방법을 쓰면 이렇게 약간 일반화를 할 수도 있겠죠.

루프는 1개로 줄었지만, 여전히 3개로 제한되어 있기는 마찬가지입니다. 이번에는 alpha에 매핑하는 부분도 일반화를~

자 이제 코드도 줄고 depth만 바꾸면 길이가 마음대로 바뀝니다~ 그렇지만, 약간 계산 오버헤드가 늘기는 했겠죠. -ㅇ-;

순열이 완전히 다 필요한 경우가 아니라, 일부가 필요한 경우이거나, 순열에서 쓰는 원소의 메모리 크기가 엄청 커서 복잡한 경우 등 여러 독특한 경우에는 순열에서 만들어지는 놈을 필요할 때 계산하는 것이 유용할 수도 있습니다.

자, 이번엔 접근법을 약간 바꿔서 숫자를 안 쓰는 방법을 생각해 봅시다. 빈 것에서 시작해서, 모든 경우를 한 번씩 추가한 것을 원하는 횟수만큼 계속 더해주는 방식으로 하면 되겠죠.

알고리즘의 계산 복잡도는 약간 안 좋아졌지만 — O(M^N)에서 O(M^N+2)로.. — 짧은 순열에 대해서는 그다지 차이는 안 날 것 같고, 코드도 그런대로 알아보기 쉬워졌습니다~ ^_^

이번엔 또 접근법을 좀 바꿔서, 행운을 믿는 사람이라면 순전히 랜덤 함수에 기대어 빨리 끝나기만 기다릴 수도 있겠습니다;;

전체 순열이 필요할 때 이걸 실제로 쓰게 되지는 않겠지만, 순열이 굉장히 커서, 전체를 메모리에 담고 있을 수 없을 때, 순간 순간 생성하되 랜덤한 순서가 필요할 때는 이것도 쓸모가 있겠죠;;; (억지로 짜낸 용례 -ㅇ-)

정말 심심할 때는 추후 고객의 업그레이드 유도를 위한 “바쁘게 돌아가는 인터넷 속의 쉼터”(TM)로 이렇게 만들어 볼 수도 있겠습니다;;

아하하;;;

자.. 이제 파이썬에서 순열을 구하는 여러가지 방법을 알아 보았는데요, 어느 한 방법이 꼭 좋다기보다는, 상황마다 고려해야할 것이 많이 있겠죠. 예를 들면,

• 순열이 무지 길고 크고 루프가 오래 돌아간다 –> 순열을 생성하는 놈을 제너레이터로 만들어서 한꺼번에 메모리를 왕창 안 먹고 있게 한다.
• 분산처리를 해야한다 –> 단일 숫자 인덱스를 기반으로 한 순열이 아무래도 쪼개기가 좋겠죠.
• 항상 2개가 쌍일 뿐이다 –> 그냥 1번처럼 for루프 2개 돌려도~
• 순열에 랜덤하게 왔다갔다 접근할 필요는 있는데, 메모리는 적게 쓰고 싶다 –> 5번 같이 순간순간 짠~하고 만들어주는 녀석을 쓰세요~
• KS X 1001 글자들 같이, 순열은 순열인데 종종 코드 곳곳이 비어있다! –> 파이썬의 리스트 컴프리헨션 뒤에 if 붙이는 문법은 정말 멋집니다~ -.-b
• 누구나 금방 알아볼 수 있는 코드로 만들고 싶다 –> 몇개 안 되면 좀 촌스러워도 1번처럼 짜거나, 순열 만드는 놈을 제너레이터로 빼서 이름을 잘 지으세요~