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

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

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

계속해서 순열에 대해서 알아보겠습니다.
앞에서 full search에대해서 아래 그림을 그렸습니다.

위 그림중에 순열이 가능한 부분을 표시해 보자면 아래와 같습니다. 아래는 첫번째로 선택이 되는 항목입니다. 순열이란 주어진 data={1,2,3,4} 에서 원소를 뽑아서 나열하는데 중복이 안되도록 하나씩 뽑는겁니다. 물론 순서가 있고요.. R=3일때 3개를 뽑아보자면 {1,2,3} 이 될겁니다. {1,1,1},{1,1,2}.. 이런건 중복되기 때문에 뽑을수가 없습니다.

그럼 이전 소스를 다시가져와서 고민해 보도록 하겠습니다.
void full(int depth)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
return;
}
for(i=1;i<=N;i++){
selected[depth]=i;
full(depth+1);
}
}

위 그림을 자세히 살펴보면 앞에서 이미 선택한 부분에 대해서는 선택을 안하도록 하면 됩니다. 그렇게 하기위해서는 선택했는지 flag가 필요하고 flag를 보고 선택을 하면 될겁니다.

void full(int depth)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
return;
}
for(i=1;i<=N;i++){
if(flag[i]==1)continue;
flag[i]=1;
selected[depth]=i;
full(depth+1);
}
}
아주 훌륭합니다.
이렇게하면 결과가 아라와 같이 나옵니다.

1 2	1 2 3 1 2 4

왜냐하면 한번 선택된 flag를 제거해주는 곳이 없습니다.
그래서 selected 변수에서도 언급했지만 선택하고나서 다음 재귀를 호출한뒤 복귀시에는 flag를 꺼줘야합니다.
void full(int depth)
{
int i;
if( R==depth){
// 모두 선택 되었음 출력하기
return;
}
for(i=1;i<=N;i++){
if(flag[i]==1)continue;
flag[i]=1;
selected[depth]=i;
full(depth+1);
flag[i]=0;
}
}

아래는 전체 코드 입니다.

순열 중복 없음
C, pasted 1 second ago:

#include <stdio.h>

#define N 4
#define R 3

int selected[R];
int flag[N+1];

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++){
    if(flag[i]==1)continue;
    flag[i]=1;
    selected[depth]=i;
    full(depth+1);
    flag[i]=0;
  }
}

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

Output:

여기에서 중복에 대한 고민을 한번 더 해보면 좋겠습니다.
1,1,1 도 되고 1,1,2 도되고 2,1,1,도 될테고 음 이렇게 해보면 중복 순열은 결국 아래 그림이 됩니다.
지금까지 모든 node를 탐색했던 full search가 됩니다.
코드는 이미 만들어 뒀던 내용입니다.

중복을 허용하는 순열 소스

C, pasted just now:

#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:

SW정리

2016년 11월 13일 일요일

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

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

댓글 1개: