SW정리: 중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (full search 부터 이해)

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (full search 부터 이해)

앞에서 아래와 같이 정리했었습니다.

N=3 {1,2,3} 존재시 R=2
순열은 N개의 항목에서 R개를 선택할때 순서를 가지면서 나열하는 방법입니다.
{1,2},{1,3},{2,1},{2,3},{3,1},{3,2}

중복 순열은 R개 선택시 중복이 가능하다는 의미입니다.
{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}

조합은 N개의 항목에서 R개를 선택할때 순서를 갖지지 않은면서 나열하는 방법입니다.
{1,2},{1,3},{2,3}

중복 조합은 R개 선택시 중복이 가능하다는 의미입니다.
{1,1},{1,2},{1,3},{2,2},{2,3},{3,3}

일단 전체 탐색을 하는 내용을 그림으로 정리해 보겠습니다.

그림이 커져서 오른쪽 절반 정도는 그림을 생략하였습니다.
이 그림의 의미는 4개의 data가 주어질때 3개를 선택하는 방법에 대한 내용입니다. 순열로 할지 조합을 할지 중복이 되게 할지는 아직 고민하지 않고 그린 그림입니다.
선택을 할때마다 depth가 증가하게 됩니다. R이 depth가 되면 선택된 항목을 출력하면 될겁니다.
아래는 2->3->1 3개를 선택하는 순서를 나타냅니다.

각각 선택해서 출력하는 알고리즘 입니다. 즉 처음에는 1-1-1, 그리고 1-1-2, 1-1-3, 1-1-3, 1-1-4, 1-2-1 ... 이런식으로 출력이되어야 합니다.
이걸 코드로 구현해 보도록 하겠습니다.

그래서 첫번째 depth 0 에서는 1, 2, 3, 4 른 순차적으로 선택한 후 다음 depth로 넘기는 과정이 필요합니다.
코드를 대충 만들어 보면 아래와 같습니다.
full()
{
int i;
for(i=1;i<=N;i++){
selected[]=i;
full(depth+1);
}
}
그다음 고민해볼것은 선택되는것을 어디엔가 저장해야할텐데요 그걸 selected 배열에 넣었습니다. 순차적으로 뒤에 추가해주면 됩니다.
그림에서 잘보면 depth가 증가될때마다 하나씩 선택되고 있기 때문에 선택되는 갯수는 depth의 수와 일치합니다.
따라서 선택 하는 코드는 selected[]=i; => selected[depth]=i; 로 해주면 됩니다.
그리고 전체적으로 얼마나 depth가 진행되고 있는지 depth를 인자로 넘겨받아야 할 겁니다.
지금까지 코드를 만들어 보면 아래와 같습니다.
full(int depth)
{
int i;
for(i=1;i<=N;i++){
selected[depth]=i;
full(depth+1);
}
}

full(depth+1); 함수 호출 후 복귀했을때 다른 값을 선택해야 합니다. 즉 이 의미는 아래와 같이 복귀하게되면 더이상 이전에 선택했던것을 취소해야한다는 의미입니다.
아래과 같이 구현해야합니다.
selected[depth]=i;
full(depth+1);
selected[depth]=-1;
하지만 아래 그림을 보면 다시 해당 depth로 돌아왔을때 새로 선택하는 index가 depth에 의해 결정되므로 이전 선택했던 depth를 취소할 필요는 없습니다. 즉 selected[depth]=-1; 이건 다음번 loop를 진행할때 selected[depth]=i; 이 코드에 의해서 필요없는 코드라는 의미입니다.

마지막으로 종료하는 코드를 넣어야 합니다.
재귀 종료 조건은 여기에서는 3개 선택될때까지, R=3 즉 R==depth 가 되면 모두 선택하고나서 다시 재귀를 들어왔다는 의미입니다. depth 가 0일때 하나를 선택하게되고 R=depth-1 일때 모두 선택이 되고 다음번 depth가 되는 재귀함수를 들어올때 모두 선택이 완료되게 됩니다.

void full(int depth)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
for(i=0;i<N;i++){
printf("%d ",selected[i]);
}
printf("\n");
return;
}
for(i=1;i<=N;i++){
selected[depth]=i;
full(depth+1);
}
}

아래는 완성된 코드입니다.

C, pasted 1 second ago:

#include <stdio.h>

#define N 4
#define R 3

int selected[R];

void full(int depth)
{
  int i;
  if( R==depth){
    // 모두 선택 되었음 출력하기
    for(i=0;i<R;i++){
      printf("%d ",selected[i]);
    }
    printf("\n");
    return;
  }
  for(i=1;i<=N;i++){
    selected[depth]=i;
    full(depth+1);
  }
}

int main()
{
  full(0);
  return 0;
}

Output:

순열 만들기
http://swlock.blogspot.com/2016/11/permutation-combination-algorithm_13.html
조합 만들기
http://swlock.blogspot.com/2016/11/permutation-combination-algorithm_45.html

SW정리

2016년 11월 13일 일요일

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (full search 부터 이해)

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (full search 부터 이해)

댓글 없음:

댓글 쓰기