순열(Permutation) 구하기

수학에서, 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 다시 말해, 순열은 숫자 배열의 순서를 뒤섞는 연산이다.

 

예를 들어 1,2,3 세 숫자 순열은 

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

다음과 같이 나열된다. 

이러한 순열의 특징 중 하나는 특정 기준점 다음의 오름차순 정렬에서 기준점 다음으로 오는 가장 작은 숫자와 위치를 교환한 후 내림 차순 정렬로 바뀐다. 이러한 특징을 살려, 순열들을 차례로 구하여 값을 구할 수 있다.

1. A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다
2. j ≥ i 이면서 A[j] > A[i-1] 를 만족하는 가장 큰 j를 찾는다
3. A[i-1]과 A[j]를 swap 한다
4. A[i]부터 순열을 뒤집는다

1. 다음 순열 구하기

문제 참고 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

풀이

#include <iostream>
#define SWAP(x,y,t) (t=x, x=y, y=t)
using namespace std;

bool next_permutation(int * arr, int n);

int main() {
	// 변수선언
	int n,temp;
	int * arr;
	
	// 입력받기
	cin >> n;

	// 할당
	arr = (int*)malloc(sizeof(int) * n);

	// 입력받기
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	// 순열 만들기
	if (next_permutation(arr, n))
		for (int i = 0; i < n; i++)
			cout << arr[i] << " ";

	else
		cout << -1;
}

// 다음 순열 함수 구하기
bool next_permutation(int * arr, int n) {
	int i = n - 1;
	int temp;

	// 내림차순인 동안 내려오기
	while (i > 0 && arr[i - 1] >= arr[i]) i -= 1;

	// 마지막 순열일 경우 
	if (i <= 0)
		return false;

	// 구분점 찾기
	int j = n - 1;
	while (arr[j] <= arr[i - 1]) j -= 1;

	//교환
	SWAP(arr[j], arr[i - 1], temp);
	
	// 위치 교환
	j = n - 1;
	while (i < j) {
		SWAP(arr[i], arr[j], temp);
		i += 1; j -= 1;
	}

	return true;
}

 

2. 이전 순열 구하기

문제 참고 : https://www.acmicpc.net/problem/10973

10973번: 이전 순열

 

풀이

#include <iostream>
#define SWAP(x,y,t) (t=x,x=y,y=t)
using namespace std;

bool prev_permutation(int * arr, int n);

int main() {
	// 변수선언
	int n, temp;
	int * arr;

	// 입력받고 할당
	cin >> n;
	arr = (int*)malloc(sizeof(int)*n);

	// 입력받기
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	// 이전 순열 구하기
	if (prev_permutation(arr, n))
		for (int i = 0; i < n; i++)
			cout << arr[i] << " ";
	
	// 없으면
	else
		cout << -1;

	// 해제
	free(arr);
	return 0;
}

bool prev_permutation(int * arr, int n) {
	// 기준점 찾기(오름차순일 동안 내려오기)
	int i = n - 1;
	while (i > 0 && arr[i - 1] <= arr[i]) i -= 1;

	// 종료조건
	if (i <= 0) return false;

	// 기준점 찾기2(더 작은거 가져오기)
	int j = n - 1, temp;
	while (arr[j] >= arr[i - 1]) j -= 1;

	// 교환
	SWAP(arr[i - 1], arr[j], temp);

	// 나머지 위치 교환
	j = n - 1;
	while (i < j) {
		SWAP(arr[i], arr[j], temp);
		i += 1; j -= 1;
	}

	return true;
}

cf) 모든 순열 찾기

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = i + 1;
	}

	do {
		for (int i = 0; i < n; i++)
			cout << a[i] << ' ';
		cout << endl;
	} while (next_permutation(a.begin(), a.end()));
	return 0;
}

#include <iostream>
#define SWAP(x,y,t) (t=x,x=y,y=t)
using namespace std;

bool next_permutation(int * arr, int n);

int main() {
	// 변수선언
	int n, temp;
	int * arr;

	// 입력받고 할당
	cin >> n;
	arr = (int*)malloc(sizeof(int)*n);

	// 입력받기
	for (int i = 0; i < n; i++)
		arr[i] = i+1;

	// 다음 순열 구하기
	do {
		for (int i = 0; i < n; i++)
			cout << arr[i] << " ";
		cout << endl; // 줄바꿈
	} while (next_permutation(arr, n));
	

	// 해제
	free(arr);
	return 0;
}

bool next_permutation(int * arr, int n) {
	// 기준점 찾기(내림차순일 동안 내려오기)
	int i = n - 1;
	while (i > 0 && arr[i - 1] >= arr[i]) i -= 1;

	// 종료조건
	if (i <= 0) return false;

	// 기준점 찾기2(더 큰거 가져오기)
	int j = n - 1, temp;
	while (arr[j] <= arr[i - 1]) j -= 1;

	// 교환
	SWAP(arr[i - 1], arr[j], temp);

	// 나머지 위치 교환
	j = n - 1;
	while (i < j) {
		SWAP(arr[i], arr[j], temp);
		i += 1; j -= 1;
	}

	return true;
}

3. 차이를 최대로 

문제 참고 : https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	// 변수선언
	int n, max=0;
	cin >> n; // 입력받기
	vector<int> a(n);
	vector<int> b(n);

	// 입력받기
	for (int i = 0; i < n; i++)
		cin >> a[i];

	// 정렬
	sort(a.begin(), a.end());

	// 메인 알고리즘
	do {
		int sum = 0;
		for (int i = 0; i < n - 1; i++)
			sum += (abs(a[i] - a[i + 1]));
		// 더크면 기록
		if (max <= sum) {
			max = sum;
			b = a;
		}
	} while (next_permutation(a.begin(), a.end()));

	// 출력
	cout << max;
} 

 

4. 외판원 순회(TSP) 2

문제 참고 : https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

풀이 

참고로 문제를 처음 풀 때 연결되어있지않은 다리를 고려하지 않아서 고생을 했다.

0으로 나오는 부분은 연결이 되어있지 않은 것이므로 해당 방법은 갈 수 없는 것으로 고려해야 한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	// 변수선언
	int n, min = 0;
	int arr[20][20];
	cin >> n;
	vector<int> a(n);

	// 입력받기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			min += arr[i][j];
		}
	}
	for (int i = 0; i < n; i++)
		a[i] = i+1;

	// 순열로 찾기
	do {
		int sum = 0;
		bool ok = true;

		// 0 일경우 이어져 있지 않음
		for (int i = 0; i < n - 1; i++){
			if (arr[a[i]][a[i + 1]] == 0)
				ok = false;
			else
				sum += arr[a[i]][a[i + 1]]; // 비용 더하기
		}
		if (ok && arr[a[n - 1]][a[0]] != 0) {
			sum += arr[a[n - 1]][a[0]]; // 마지막 비용 더하기
			if (sum < min) min = sum; //값비교
		}

	} while (next_permutation(a.begin()+1, a.end()));

	// 출력
	cout << min;
	return 0;
}