알고리즘 순열 C언어로 구현하기

안녕하세요 오늘은 순열의 경우의수를 C언어로 구현해 보겠습니다

순열이란 서로다른 n개중 r개를 뽑아서 나열한 경우의 수를 의미합니다 (nPr)

예를들어 3P2이라면 경우의 수는 (1,2) (1,3) (2,3) (2,1) (3,1) (3,2)입니다..

구현방법 (예시3P2)

1) 재귀함수 구현 : 함수를 만들고 재귀함수로 사용합니다

2) DFS(Depth First search)사용

DFS(0)함수를 실행하면 DFS(1)가 실행되고 DFS(2)가 실행면 경우의 수를 출력해줍니다

재귀함수의 종료 조건은 2인걸 알 수 있습니다

3) 체크리스트 사용 : 1,2,3값들을 사용했으면 1로해줍니다. 중복을 막기 위해 사용합니다 위의 그림을 보면 빨강 네모는 중복입니다. 

코드

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <stdio.h>   int n[3] = {1,2,3}; int r = 2; int result[2]; int checklist[4];     void DFS(int L) {     int i;     if(L==r) //종료     {         for(i=0 ; i<r ; i++)             printf("%d ",result[i]);         printf("\n");     }     else     {         for( i =0; i< (sizeof(n)/4) ; i++)         {             if(checklist[i]==0)             {                 result[L] = n[i];                 checklist[i] = 1;                 DFS(L+1);                 checklist[i] = 0;             }                      }     }     }            int main(void) {     DFS(0); }

3~6번째줄 : 필요한 변수를 선언해줍니다

9번째줄 : 함수 선언입니다

12번째줄 : 함수의 출력 조건입니다.. 재귀함수를 호출하다가 DFS(2)가 되면 출력해줍니다

20번째줄 : n배열의 인덱스0,1,2값을 result에 넣어주는 for문입니다

22번째줄 : 체크리스트가 0인지 검사합니다

24번째줄 : result배열에 값을 넣습니다

25~27번째줄 : checklist에 값을 넣고 DFS함수를 호출합니다. 함수를 호출하고나서 checklist값을 0으로 초기화시킵니다.

36번째줄 : 함수를 호출합니다

DFS(0) -> 

DFS(1) -> 

DFS(2) DFS(2) DFS(2) ->

DFS(1) -> 

DFS(2) DFS(2) DFS(2) ->

DFS(1) -> 

DFS(2) DFS(2) DFS(2) ->

빨강색은 중복으로인해 출력이 안되는 부분입니다