6 순열과 조합의 구현 - 순열편

이전포스트

순열과조합

순열과 조합의 구현

반복을 허용하는 순열은 저희가 했던 브루트 포스 와 같습니다. 

브루트포스 보러가기

즉, 4자로 이루어진 비밀번호가 있는데 소문자 알파벳으로 이루어져있음 그 경우의 수가 26^4이죠.
반복을 허용하는 순열의 경우는 이와 같습니다.

자, 근데 이제 어떤 중요한 정보를 얻었다고 합시다.

비밀번호의 알파벳들이 겹치지 않는다는 정보요. 그렇다면 26^4 -> 26*25*24*23 으로 경우의수가 줄어듭니다. 그렇담 순열대로 알고리즘을 생성해내는게 더 효율적이겠죠.

근데....

순열 알고리즘은 어떤거죠?

생각보다 어렵지 않습니다. 순열을 생성해내는 것은 사전식으로 정렬 하는것과 똑같습니다. 어떤식으로 정렬을 해야할까요

a, b, c, d 의 다음순열은 a, b, d, c 입니다. 자 차례로 순열을 적어보겠습니다. 4! 이니까 24개겠네요 와!

편의상 숫자로 해볼게요

1234
1243
1324
1342
1423
1432

2134
2143
2314
2341
2413
2431

3124 ...

그만... 그만.

그래 그만..

위에서 보신게 오름차순의 순열생성입니다.

어쩃든 순열을 생성할 때는 이렇게 룰을 따라서 오름차순으로 생성하던가 내림차순으로 작성하면 편리한데요.

기본적인 룰은 다음과 같습니다.

1, 2, 3, 4 의 그 다음 원소는 무엇일까요? 1, 2, 4, 3

그 다음 원소는 어떻게 찾았을까요?  어... 음,,, 3과 4를 바꿔요?

예 맞습니다.

1, 2, 4, 3의 그다음 원소는 무엇일까요? 1, 3, 2, 4

그 다음 원소는 어떻게 찾았을까요? 어... 음... 모르겠어요

아마.. 3과 2를 바꾸고요.. 그럼 1 3 4 2 인데... 음... 2 와 4를 바꿔요? 

네 맞습니다

1 3 2 4 의 다음 원소는 무엇일까요? 1, 3, 4, 2

그 다음 원소는 어떻게 찾았을까요? 어... 음,, 2와 4를 바꿔요?

에 맞습니다

뭐야 왜 1 2 3 4 와 1 3 2 4 의 다음 원소는 단 한번 swap을 수행하는데

1 2 4 3 의 다음원소를 찾는데는 두번이나 바꾸죠?......

... 안돼!, 모르면 확실하게 알때까지 계속해서 스스로에게 질문을해야지!..남들에게 묻거나..

좀 더 일반적으로 순열을 생성하는 걸 볼거에요. 이건 어떤 문자열이나 숫자들을 사전식으로 생성하는 것과 같아요.

시작은요, a1< a2< ... a[n-1] < a[n] 의 성질에서요  a[1] >a[2]> ... a[n-1] > a[n]의 성질으로 도착하는 것과같아요

위에 보는 그림이 모든 순열에서 처음순열과 맨 끝순열이지요. 첫 원소(순열)은 다음을 만족합니다.

1항부터 n항까지 모두 오름차순이죠

마지막 원소(순열)은 다음을 만족합니다. n항부터 1항까지 모두 오름차순이죠

 이제 그 사이의 순열들을 생성해낼건데요.다음을 확인해보죠.

넘 길었죵????? 요약본 갑니다..!

아래는 코드작성후 수행해본 결과물입니다.

함수로 만들어서 오름차순으로 정렬할 수 있을ㄸ ㅐ 까지 반복할 수 있게했습니다.

소스보기

설명한 예제의 순열 코딩 보러가기

오름차순 순열 생성 함수 보러가기

내림차수 순열 생성 함수 보러가기

순열만 해도 너무 길었네여...

담 포스트는 조합편으로할게요

순열과 조합의 구편 - 조합편 바로가기