[DS] Permutation (순열)

# 순열

- 어떤 원소 n개를 나열할 때 순서가 다르면 다른 순열로 간주함

(1) 집합 {'a', 'b', 'c'}에 대하여 찾을 수 있는 모든 순열

  > P = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)}

  > 3P3 = 3 * 2 * 1 = 3! = 6

(2) 집합 {'a', 'b', 'c', 'd'}의 순열

  > 4! = 24

  > 24개의 순열은 4개의 그룹으로 나뉘어질 수 있음

a)	(a, Perm(b, c, d))
b)	(b, Perm(a, c, d))
c)	(c, Perm(a, b, d))
d)	(d, Perm(a, b, c))

> 하나의 원소를 고정하고 그 뒤에 원소의 수만 다른 순열을 나타내는 함수를 호출함

  > ex) Perm(b, c, d)도 위와 같은 방법으로 3개의 그룹으로 표현됨

a)	(b, Perm(c, d))
b)	(c, Perm(a, d))
c)	(d, Perm(a, b))

  > 따라서 순열은 재귀 호출을 이용해 해결할 수 있음

  > 종결 조건: Perm이 하나의 원소를 가리킬 때

 

 

 

# 순열 구현

- char list = {'a', 'b', 'c', 'd'} ;

 

- i: 범위의 시작 index

- n: 범위의 끝 index

- 실제 perm 함수의 인자는 배열의 시작, 끝인덱스(위치)을 가리키므로

   종결 조건은 시작과 끝 위치가 같을 때임

 

[코드 1]

#include <stdio.h>

void perm(char list[], int i, int n);
void swap(char *a, char *b);
int start, end;
char list[]={'a','b','c','d'};

int main(){
    printf("list[]={'a','b','c','d'}\n");
    printf("input two values for start and end position:");
    scanf("%d %d",&start,&end);
    perm(list,start,end);

}

void swap(char* a, char* b) { // a와 b를 바꿈
    char temp = *a;
    *a = *b;
    *b = temp;
}

void perm(char list[], int i, int n) { // i는 시작 위치, n은 마지막 위치
    int j;
    if (i == n) { // 순열을 출력
        for (j = 0; j <= n; j++) {
            printf("%c ", list[j]);
        }
        printf("\n");
    }
    else {
        for (j = i; j <= n; j++) {
            swap(&list[i], &list[j]); // list[i]와 list[j]를 바꿈
            perm(list, i + 1, n);// list[i+1]부터 list[n]에 대한 모든 순열
            swap(&list[j], &list[i]); // 원래 상태로 되돌리기 위해 다시 바꿈
        }
    }
}

 

[실행결과 1]

 

[코드 2]

#include <stdio.h>
#define exchange(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void word(char* letter, int i, int n);

int start = 0, end = 3;

int main() {
	char letter[] = { 'A', 'B', 'C', 'D'};

	scanf("%d", &start);
	scanf("%d", &end);
	word(letter, start, end);

	return 0;
}

void word(char* letter, int i, int n) {
	int j, temp;
	if (i == n) {
		for (j = start; j <= n; j++) printf("%c", letter[j]);
		printf("\n");
	}
	else
		for (j = i; j <= n; j++) {
			exchange(letter[i], letter[j], temp);
			word(letter, i + 1, n);
			exchange(letter[i], letter[j], temp);
		}
}

> 코드 1과 다르게 exchange 매크로를 사용하여 swap함수 기능 구현

 

[실행결과 2]