SW정리: 중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (combination 구현)

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (combination 구현)

이전글
http://swlock.blogspot.com/2016/11/permutation-combination-algorithm-full.html

계속해서 조합에 대해 알아보겠습니다.
출발은 full search에서부터 출발합니다.

여기에서 조합할때 선태되는 부분에 원을 그려보도록 하겠습니다.

중복이 안되어야하고 순서도 관계없으니 {1,2,3} {1,2,4} {1,3,4} {2,3,4} 더는 없는것 같습니다.
그림을 봐서는 어떤 규칙성을 찾기가 어려워 보입니다.

루프를 돌기 위한을 시작점의 숫자에서, 부모 depth 와 자식 depth와의 관계에서 보면 자식은 부모 +1 만큼 더해주는 위치에서 시작합니다. 왜냐하면 순열과 다르게 조합은 부모보다 같거나 작은 index의 경우 이미 검토가 끝났기 때문입니다. 이것을 코드로 구현해보면 다음과 같습니다.

void full(int depth,int index)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
return;
}
for(i=index;i<=N;i++){
selected[depth]=i;
full(depth+1,i+1);
}
}
주의할점은 재귀 호출시 여기 예제에서는 1부터 나오기 때문에 시작지점을 1로 호출했습니다. 아래 완성된 코드를 보면 됩니다.

C, pasted just now:

#include <stdio.h>

#define N 4
#define R 3

int selected[R];

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

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

Output:

그리고 좀 더 성능을 높이기 위해서는 여기에서는 2,3,4 까지 진입하게되는데 4는 진입할 필요가 없으므로 i<=N 조건을 추가로 변경이 가능하리라 봅니다.

이번에는 중복이 가능한 조합을 살펴보겠습니다.
중복 가능한 조합의 경우 그림에 표시를 해봤습니다. 빨간색

자식과 부모의 관계를 파란색으로 표시해봤습니다.
자식의 loop와 부모 loop의 index가 동일하게 하면 될것 같습니다.
소스에서 i+1 => i 로 변경하면 됩니다.
void full(int depth,int index)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
return;
}
for(i=index;i<=N;i++){
selected[depth]=i;
full(depth+1,i);
}
}

C, pasted 1 second ago:

#include <stdio.h>

#define N 4
#define R 3

int selected[R];

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

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

Output:

SW정리

2016년 11월 13일 일요일

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (combination 구현)

중복 순열 (Permutation) 조합(combination)알고리즘 생성 방법 algorithm (combination 구현)

댓글 4개: