순열

임의의 집합 data에 대해서 원소들의 모든 가능한 순열을 출력하라

 

data = {a,b,c,d} 

4! = 24개

 

a b c d

a b d c

a c b d

a d b c

. . . . 

 

a를 고정 - b,c,d의 모든 순열에 a를 앞에 추가하여 출력

b를 고정 - a,c,d의 모든 순열에 b를 앞에 추가하여 출력

. . . . 

a,b를 고정 - c,d의 모든 순열에 a,b를 앞에 추가하여 출력

. . . 

a,b,c를 고정 - d에 a,b,c를 앞에 추가하여 출력

 

void printPerm(a prefix string, a set S)
{
	if S is 0
    	print the pre fix string;
    else
    	for each element x in S
        	printPerm(the prefix string + x, S-{x});
}

S의 모든 순열들을 생성한 후 각각에 prefix String을 앞에 붙여서 출력한다.

 

int data[] = {'a','b','c','d'};
int n = 4;

void perm(int k) {
	if(k==n) {
    	print data[0...n-1];
        return;
    }
    
    for(int i=k; i<n; i++) {
    	swap(data, k, i);
        perm(data, k+1; n);
        swap(data, k, i);
        }
    }

perm이라는 함수의 미션은 매개변수 k를 받아서 data[a..k-1]prefix로 정하고 data[k..n]으로 만들수 있는 모든 순열을

프린트하되, 배열 data에 저장된 값들의 순서는 그대로 유지한다.

 

---

 

멱집합(순서무관)과 순열 나열(순서상관)의 응용

 

배낭문제 

-무게와 가격이 정해진 n개의 아이템과 용량이 w이 배낭이 있다.

배낭의 용량을 초과하지 않으면서 가격의 합이 최대가 되도록 아이템을 배낭에 넣으려면?

 

TSP

- 서울 대전 대구 부산 광주 강릉 속초 등의 n개의 도시들이 있을때

한 도시에서 출발하여 모든 도시들을 지나서 다시 집으로 돌아올때 방문 순서에따라

이동 거리가 달라지는데 길이가 가장 짧은 투어를 고르는 문제.