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

앞에서 순열과 조합에 대해서 정리해보았습니다.

아래 코드는 중복을 허용할때와 하지않을때 코드를 모두 정리하였습니다.

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}

하지만 아래 코드가 일반적으로 책에서 많이 나오는 방식입니다. 따라서 자세한 하지 않겠습니다.

다음에는 아래 코드 보다 이해하기 쉬운 코드를 만들어서 공유하도록 하겠습니다.

C, pasted just now:

#include <stdio.h>

#define NN 5

int array[] = {0, 1, 2, 3, 4};
int r = 3; //추출할 개수   
int N = NN;
int out[NN];
int count = 0;

void swap(int i, int start) {
 int temp = out[i];
 out[i] = out[start];
 out[start] = temp;
}

void permutation(int start, int end) {
 int i;
 if(start == end) {
  for(i = 0; i < end; i++) {
   printf("%d ",out[i]);
  }
  printf("\n");
  count++;
  return;
 }
  
 for(i = start; i < N; i++) {
  swap(i, start);
  permutation(start+1, end);
  swap(i, start);
 }
  
}

void dpermutation(int start, int end) {
 int i;
 if(start == end) {
  for(i = 0; i < end; i++) {
   printf("%d ",out[i]);
  }
  printf("\n");
  count++;
  return;
 }
  
 for(i = 0; i < N; i++) {
  out[start] = array[i];
  dpermutation(start+1, end);
 }
}
 
 
void combination(int start, int end, int index) {
 int i;
 if(end==0) {
  for(i = 0; i < start; i++) {
   printf("%d ",out[i]);
  }
  printf("\n");
  count++;
 }else if (index == N) {
  return;
 } else {
  out[start] = array[index];
  combination(start+1, end-1, index+1); // 여기 다름
  combination(start, end, index+1);
 }
  
}
  
void dcombination(int start, int end, int index) {
 int i;
 if (end == 0) {
  for(i = 0; i < start; i++) { 
   printf("%d ",out[i]);
  }
  printf("\n");
  count++;
 } else if (index == N) {
  return;
 } else {
  out[start] = array[index];
  dcombination(start+1, end-1, index); // 여기 다름
  dcombination(start, end, index+1);
 }  
}
  
  
void main() 
{
 int i;
 //중복 조합
 count = 0;
 dcombination(0, r, 0);
 printf("1:%d\n\n",count);

 //조합
 count = 0;
 combination(0, r, 0);
 printf("2:%d\n\n",count);

 //중복 순열
 count = 0;
 dpermutation(0, r);
 printf("3:%d\n\n",count);

 //순열
 //순열시 출력에 초기값 필요함
 for(i = 0; i < N; i++) {
  out[i] = array[i];
 }
 count = 0;
 permutation(0, r);
 printf("4:%d\n\n",count);

}

Output:

SW정리

2016년 11월 12일 토요일

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

댓글 없음:

댓글 쓰기