SW정리: 순열 (Permutation) 알고리즘 생성 방법 algorithm

순열 : 서로 다른 n개 중 r 뽑아 나열하는 것(순서 있음)

n개중 n개를 뽑아 나열하는것은 n!이 된다.

{1,2,3} 와 같은 숫자들이 있다. 중복하지 않고 순서를 모두 끌어내는 방법을 생각해보자

1-2-3
1-3-2
2-1-3
2-3-1
3-1-2
3-2-1

결과를 잘보면 앞자리는 3가지(1,2,3) * 두번째 자리는 2가지(첫번째 자리 선택한것 제외하고 2개중에 선택) * 세번째 자리는 1가지가 된다.

따라서 3*2*1=6 6가지가 나오게 된다.

이것을 loop로 간단하게 만들어 보면 아래와 같다.

C, pasted 1 second ago:

#include <stdio.h>

int set[]={1,2,3};

#define N 3

main()
{
    int i,j,k;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            if(i==j) continue;
            for(k=0;k<N;k++){
                if(i==k) continue;
                if(j==k) continue;
                printf("%d-%d-%d\n",set[i],set[j],set[k]);
            }
        }
    }
    return 0;
}

Output:

1-2-3
1-3-2
2-1-3
2-3-1
3-1-2
3-2-1

위 코드의 단점은 N의 크기가 가변적일때 loop 크기가 가변이 될 수 없다는 문제가 있다.
아래는 4개의 item일때의 코드이다. loop가 하나 더 추가되었다. 헐.... N이 가변일때는 어떻게 해야 될까?

C, pasted just now:

#include <stdio.h>

int set[]={1,2,3,4};

#define N 4

main()
{
    int i,j,k,l;
    for(l=0;l<N;l++){
    for(i=0;i<N;i++){
        if(l==i) continue;
        for(j=0;j<N;j++){
            if(i==j) continue;
            if(l==j) continue;
            for(k=0;k<N;k++){
                if(i==k) continue;
                if(j==k) continue;
                if(l==k) continue;
                printf("%d-%d-%d-%d\n",set[l],set[i],set[j],set[k]);
            }
        }
    }
    }
    return 0;
}

Output:

1-2-3-4
1-2-4-3
1-3-2-4
1-3-4-2
1-4-2-3
1-4-3-2
2-1-3-4
2-1-4-3
2-3-1-4
2-3-4-1
2-4-1-3
2-4-3-1
3-1-2-4
3-1-4-2
3-2-1-4
3-2-4-1
3-4-1-2
3-4-2-1
4-1-2-3
4-1-3-2
4-2-1-3
4-2-3-1
4-3-1-2
4-3-2-1

그래서 다른 방법을 고민해야 한다.

{1,2} 인 경우 {1,2},{2,1} 각각의 자리를 교환 하면 됩니다.
{1,2,3} 인 경우 {1,2,3}에서 3이 추가되었다고 생각해서 3의 위치가 고정되면 {1,2}만 교환하면 3이 마지막자리인 경우 {1,2,3},{2,1,3} 2가지 경우가 나옵니다.
그리고, 1,3을 교환해서 {3,2,1}을 만든후 1이 고정되었다고 생각하면 {3,2} {2,3} 2가지 경우가 나옵니다. 이것을 그림으로 그려보면 아래와 같습니다.

결국 4자리 순열은 마지막 자리만 고정해서 3자리 순열을 호출하고 3자리 순열은 마지막 자리를 고정해서 다시 2자리 순열을 호출 하는 방식을 생각해볼 수 있습니다.

재귀로 구현

지금까지 설명된 내용을 수도 코드로 만들어 보았습니다.

Permutation(N)

if( N==1 )

print(data)

return

loop i,0->N-1

swap(i,N-1)

Permutation(N-1)

swap(i,N-1)

그리고 소스 코드입니다.
여기에서 중요한 내용은 swap을 두번 하는 내용입니다. 이렇게 되는 이유는 생성하는 data가 전역적이라서 Permutation 함수를 호출하고 나서 swap을 하여 원본 위치로 변경하기 위해서 그렇습니다.
swap(i,N-1)

Permutation(N-1)

swap(i,N-1)

C, pasted just now:

#include <stdio.h>

int data[]={1,2,3,4};

int swap(int i,int j)
{
    int temp;
    if(i==j) return 0;
    temp = data[i];
    data[i]=data[j];
    data[j]=temp;
    return 0;
}

int Permutation(int TotalN,int N)
{
    int i;

    if( N==1 ) {
        for(i=0;i<TotalN;i++){
            printf("%d ",data[i]);
        }
        printf("\n");
        return 0;
    }

    for(i=0;i<N;i++){
        swap(i,N-1);
        Permutation(TotalN,N-1);
        swap(i,N-1);
    }
}

main()
{
    int N=sizeof(data)/sizeof(int);
    Permutation(N,N);
    return 0;
}

Output:

------------------------------------------------
댓글이 있어서 내용 추가합니다.
아래는 swap을 이용하는 nPr 에 대한 내용입니다.

C++, pasted just now:

#include <stdio.h>

int data[]={1,2,3,4};
int R = 3;

int swap(int i,int j)
{
    int temp;
    if(i==j) return 0;
    temp = data[i];
    data[i]=data[j];
    data[j]=temp;
    return 0;
}

int Permutation(int n,int r,int depth)
{
    int i;

    if( r==depth ) {
        for(i=0;i<R;i++){
            printf("%d ",data[i]);
        }
        printf("\n");
        return 0;
    }

    for(i=depth;i<n;i++){
        swap(i,depth);
        Permutation(n,r,depth+1);
        swap(i,depth);
    }
    return 0;
}

int main()
{
    int N=sizeof(data)/sizeof(int);
    Permutation(N,R,0);
    return 0;
}

Output:

위 내용 보다는 아래 링크를 이해하는것이 좀 더 쉬운 방법입니다.
http://swlock.blogspot.kr/2016/11/permutation-combination-algorithm_13.html

SW정리

2016년 3월 1일 화요일

순열 (Permutation) 알고리즘 생성 방법 algorithm

재귀로 구현

댓글 3개: