본문으로 건너뛰기
黯羽轻扬매일 조금씩

순열 알고리즘 분석 (자체 고안 방법/일반적인 방법/사전식 순서법)

무료2015-03-17#Math#全排列算法

순열 알고리즘을 하나하나 분석합니다. 고심 끝에 드디어 이해하게 된 세 가지 순열 알고리즘과 상세한 설명을 제공합니다.

문제 재정의:

순열(Full Permutation) 알고리즘이란 주어진 수열에 대해 가능한 모든 서로 다른(n!가지) 배열을 출력하는 것을 말합니다. 예를 들어:

주어진 수열 {1, 2, 3}에는 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 6가지 순열이 있습니다.

쉽게 작성할 수 있을 것 같고, 수열이 길어져도 시간 문제일 뿐 결국 종이에 하나하나 나열할 수는 있습니다. 하지만 프로그램으로 구현하려면 (얼핏 간단해 보여도) 어떻게 시작해야 할지 막막할 수 있습니다. 아래에 순열을 구하는 세 가지 서로 다른 방법을 소개합니다:

1. 자체 고안 방법

여기서 말하는 '자체 고안 방법'이란 알고리즘의 효율성이나 기타 요소를 고려하지 않고, 오로지 문제 해결을 위해 스스로 구상한 실행 가능한 방법입니다 (최선은 아닐 수 있지만 문제는 해결합니다).

먼저, 우리가 위의 6개 수열을 어떻게 썼는지 생각해 봅시다.

  1. 첫 번째 자리에 올 원소를 결정합니다. 1, 2, 3의 세 가지 가능성이 있습니다.
  2. 두 번째 자리에 올 원소를 결정합니다(1을 예로 들면). 2, 3의 두 가지 가능성이 있습니다.
  3. 세 번째 자리에 올 원소를 결정합니다(2를 예로 들면). 3 한 가지 가능성만 남습니다. 이때 하나의 수열 {1, 2, 3}을 얻게 됩니다.

함께 생각을 정리하여 프로그램으로 어떻게 구현할지 고민해 봅시다. 길이가 n인 수열에 대해 컴퓨터가 해야 할 일은 다음과 같습니다:

  • 1. i번째 자리에 올 원소를 결정합니다. (n + 1 - i)가지 가능성이 있으며, 각 가능성을 차례로 선택하여 i번째 원소로 삼고 현재까지 결정된 수열(길이 i)을 저장합니다.
  • 2. (i+1)번째 자리에 올 원소를 결정합니다. (n + 1 - i - i)가지 가능성이 있으며, 각 가능성을 차례로 선택하여 i + 1번째 원소로 삼고 현재까지 결정된 수열(길이 i + 1)을 저장합니다.
  • ...
  • n. n번째 자리에 올 원소를 결정합니다. 한 가지 가능성만 남으며, 이를 n번째 원소로 삼고 결정된 수열을 출력합니다.

명백히 이는 재귀적인 방법입니다. Java 코드는 다음과 같습니다:

public class FullPermutation {
	static int count = 0;
	//递归实现全排列
	//程序思路是：依次确定第一位到最后一位，与人的一般思维方式一致
	public static void main(String[] args) {
		String str = "13234";
		str = check(str);//去除重复元素
		fullPermutate(0, "", str);
		System.out.print(count);
	}
	//@param index 本次调用确定第index位
	//@param path 已经确定顺序的串
	//@param string 待全排列的串
	static void fullPermutate(int index, String path, String string)
	{
		String restStr = strSub(string, path);
		if(index == string.length())
		{
			System.out.println(path + restStr);
			count++;//
			return;
		}
		else
		{
			for(int i = 0;i < string.length() - index;i++)
				fullPermutate(index + 1, path + restStr.charAt(i), string);
		}
	}
	//@param full 完整的串
	//@param part 部分子串
	//@return rest 返回full与part的差集
	static String strSub(String full, String part)
	{
		String rest = "";
		for(int i = 0;i < full.length();i++)
		{
			String c = full.charAt(i) + "";
			if(!part.contains(c))
				rest += c;
		}
		return rest;
	}
	//@param str 待检查的串
	//@return 返回不含重复元素的串
	static String check(String str)
	{
		for(int i = 0;i < str.length() - 1;i++)
		{
			String firstPart = str.substring(0, i + 1);
			String restPart = str.substring(i + 1);
			str = firstPart + restPart.replace(str.charAt(i) + "", "");
		}
		return str;
	}
}

P.S. 위의 코드에서 매개변수의 중복 원소를 제거하는 이유는 프로그램의 견고성(Robustness)을 높이기 위함입니다. 고전적인 순열 문제는 중복 원소가 없는 수열을 대상으로 하며, 중복 원소가 포함된 수열은 나중에 따로 논의하겠습니다.

2. 일반적인 알고리즘 (가장 흔하고 고전적인 순열 알고리즘)

핵심 아이디어는 교환입니다. 구체적으로 길이가 n인 수열의 모든 순열을 얻으려면 다음과 같이 할 수 있습니다:

  1. 현재 위치의 원소를 그 뒤에 있는 모든 원소와 차례로 교환합니다.
  2. 다음 위치에 대해 동일한 처리를 반복하며, 현재 위치가 마지막 위치가 될 때까지 진행한 후 수열을 출력합니다.

(주의할 점: 우리의 아이디어는 '교환'입니다. 즉, 원본 데이터를 직접 수정하는 것이므로 교환한 후에는 반드시 다시 원래대로 되돌려 놓아야 합니다. 그렇지 않으면 원본 데이터가 변형되어 오류가 발생하게 됩니다.)

위의 설명이 여전히 어렵다면 이 문장을 기억하세요: 핵심 아이디어는 '뒤에 있는 모든 사람이 나와 한 번씩 자리를 바꾸는 것'입니다 (당신은 포인터가 되어 앞에서부터 뒤로 한 칸씩 이동합니다...). C 코드는 다음과 같습니다: (출처: http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html)

#include <stdio.h>  
int n = 0;  
void swap(int *a, int *b) 
{     
    int m;
    m = *a;
    *a = *b;
    *b = m;
}  
void perm(int list[], int k, int m) 
{
    int i;     
    if(k > m)     
    {          
        for(i = 0; i <= m; i++)             
            printf("%d ", list[i]);         
        printf("\n");         
        n++;     
    }     
    else     
    {         
        for(i = k; i <= m; i++)         
        {             
            swap(&list[k], &list[i]);             
            perm(list, k + 1, m);             
            swap(&list[k], &list[i]);         
        }     
    } 
} 
int main() 
{     
    int list[] = {1, 2, 3, 4, 5};     
    perm(list, 0, 4);     
    printf("total:%d\n", n);     
    return 0; 
}

원문에도 약간의 설명이 있지만, 여전히 이해가 안 된다면 실행 경로(Trace)를 출력해 보는 것이 도움이 됩니다. 아니면 종이에 직접 그려보며 몇 번 반복해서 보면 이해가 갈 것입니다. 코드만 바로 보면 이해하기 쉽지 않습니다.

3. 사전식 순서법

사실 이 글의 서두에서 든 예시에서도 사전식 순서를 사용했습니다. 사람이 순열이나 비슷한 것을 쓸 때 무의식적으로 사전식 순서를 사용하게 되는데, 이는 순열을 빠뜨리지 않기 위해서입니다.

따라서 사전식 순서로도 모든 순열을 구현할 수 있습니다. 주어진 수열 {3, 1, 2}에 대해 구체적인 단계를 생각해 봅시다:

  1. 주어진 수열을 오름차순으로 정렬하여 가장 작은 사전식 순서 {1, 2, 3}을 얻습니다.
  2. 정렬된 수열에서 다음 사전식 순서를 구해 {1, 3, 2}를 얻습니다.
  3. 현재 수열의 다음 사전식 순서가 없다면(즉, 현재 수열이 {3, 2, 1}처럼 최대 사전식 순서라면) 종료합니다.

사전식 순서법의 핵심은 '다음 사전식 순서'를 구하는 것입니다. 여기서 '다음'이라는 단어는 두 가지 의미를 가집니다:

  1. 해당 수열이 사전에서 현재 수열 뒤에 위치해야 합니다.
  2. 해당 수열이 사전에서 현재 수열과 가장 가까워야 합니다.

사전식 순서는 엄격한 수학적 정의가 있으며, 정의에 따라 수열의 다음 사전식 순서를 구할 수 있습니다. 구체적인 방법은 여기서 자세히 다루지 않겠습니다 (아래 코드에 상세한 설명이 포함되어 있습니다). Java 코드는 다음과 같습니다:

public class DictionaryOrder {
	//按字典序输出全排列
	//按照字典序可以得到已知序列的下一个序列，可以用于不需要得到所有全排列的场合（例如数据加密）
	public static void main(String[] args) {
		int arr[] = new int[]{4, 3, 1, 2};
//		boolean exist = nextPermutation(arr);
//		if(exist)
//		{
//			for(int value : arr)
//				System.out.print(value);
//			System.out.println();
//		}
//		else
//			System.out.println("当前序列已经是最大字典序列");
		//对给定序列排序（升序）
		sort(arr);
		for(int value : arr)
			System.out.print(value);
		System.out.println();
		//求全排列并输出
		int count = 1;//第一个已经在上面输出了
		while(nextPermutation(arr))
		{
			for(int value : arr)
				System.out.print(value);
			System.out.println();
			count++;
		}
		System.out.println("共 " + count + " 个");
	}
	//@param arr 当前序列
	//@return 字典序中的下一个序列，没找到则返回false
	public static boolean nextPermutation(int[] arr)
	{
		int pos1 = 0, pos2 = 0;
		//1.从右向左找出满足arr[i] < arr[i + 1]的i
		//（就是找出相邻位中满足前者小于后者关系的前者的位置）
		boolean find = false;
		for(int i = arr.length - 2;i >= 0;i--)
			if(arr[i] < arr[i + 1])
			{
				pos1 = i;
				find = true;
				break;
			}
		if(!find)//若没找到，说明当前序列已经是最大字典序了
			return false;
		//2.从pos1向后找出最小的满足arr[i] >= arr[pos1]的i
		//（就是找出pos1后面不小于arr[pos1]的最小值的位置）
		int min = arr[pos1];
		for(int i = pos1 + 1;i < arr.length;i++)
		{
			if(arr[i] >= arr[pos1])
			{
				min = arr[i];
				pos2 = i;
			}
		}
		//3.交换pos1与pos2位置上的值
		int temp = arr[pos1];
		arr[pos1] = arr[pos2];
		arr[pos2] = temp;
		//4.对pos1后面的所有值做逆序处理（转置）
		int i = pos1 + 1;
		int j = arr.length - 1;
		for(;i < j;i++, j--)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		return true;
	}
	//对给定数组做升序排序（冒泡法）
	//@param arr 待排序数组
	public static void sort(int[] arr)
	{
		for(int i = 0;i < arr.length - 2;i++)
			for(int j = 0;j < arr.length - i - 1;j++)
				if(arr[j] > arr[j + 1])
				{
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
	}
}

알고리즘의 세부 사항은 여기까지입니다. 아래에서는 몇 가지 부가적인 문제를 논의해 보겠습니다:

1. 주어진 수열에 중복 원소가 존재하는 경우

고전적인 순열 문제는 이 문제를 다루지 않지만, 실제 응용에서는 마주칠 수 있습니다. 두 가지 선택지가 있습니다:

a. 원본 데이터(주어진 수열)를 처리하여 중복 원소 중 하나만 남기거나, 중복 원소를 다른 것으로 대체합니다. 예를 들어 {1, 1, 2, 3, 2}에 대해 대체표(a=1, b=2)를 만들어 원본을 {1, a, 2, 3, b}로 처리하면 중복 원소를 제거할 수 있습니다.

b. 알고리즘을 수정하여 중복 원소를 감지하고 그에 맞게 처리합니다. 이는 데이터의 구체적인 특징에 맞춰 처리해야 합니다.

2. 알고리즘 효율성 문제

복잡한 문제에서 순열을 사용해야 한다면 알고리즘 효율성을 고려하지 않을 수 없습니다. 위에 제시된 알고리즘 중 앞의 두 가지는 시간 복잡도가 동일하며, n개 층의 재귀와 각 층에서 n-i + 1번의 루프를 가집니다.

세 번째 알고리즘의 시간 복잡도는 주로 정렬에 집중되어 있습니다. 만약 주어진 수열이 이미 정렬되어 있다면 세 번째 알고리즘이 단연 최고입니다.

이 외에도 참신한 순열 알고리즘이 있으니 관심 있다면 시도해 보시기 바랍니다. 원문 링크: http://supershll.blog.163.com/blog/static/37070436201171005758332/

댓글

아직 댓글이 없습니다

댓글 작성