C# 순열

 n>=1개의 원소를 가진 집합이 주어졌을 때 이 집합의 모든 가능한 순열을 출력해보자. 예를들어 주어진 집합이 {a,b,c}라면 순열의 집합은

{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)이다. n개의 주어진 원소에 대해 n!개의 서로 다른 순열이 있다는 것은 쉽게 알 수 있다.

네개의 원소 (a,b,c,d)로 된 집합을 살펴보면 간단한 알고리즘을 얻을 수 있을 것이다. 해답은 다음과 같이 출력해 보면 얻을 수 있다.

 

 (1) a로 시작하는 (b,c,d)의 모든 순열

 (2) b로 시작하는 (a,c,d)의 모든 순열

 (3) c로 시작하는 (a,b,d)의 모든 순열

 (4) d로 시작하는 (a,b,c)의 모든 순열

 

 '~로 시작하는 ~의 모든 순열'이라는 표현이 바로 순환의 실마리이다. 이것은 n-1개의 원소에 동작하는 알고리즘이 있다면, n개의 원소를 가진 집합에 대한

문제도 해결 할 수 있다는 것을 의미한다. 이러한 생각으로 프로그램을 만들어 낼 수 있고, 이 함수는 Perm(a,0)이라는 식으로 호출된다.

 

 순환이 유용한 또 다른 예는, 알고리즘이 다루는 자료 구조가 순환적으로 정의되어 있는 경우이다.

 

C# 코드

namespace 순열
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] datas = new char[] { 'a', 'b','c' };

            Perm(datas, 0);

            Console.ReadKey();
        }

        /// <summary>
        /// 순열을 출력한다.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="k"></param>
        private static void Perm(char[] a, int k)
        {
            if (k == a.Length - 1)//순열을 출력
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("{0} ", a[i]);
                }
                Console.WriteLine();
            }
            else
            {
                for (int i = k; i < a.Length; i++)
                {
                    //a[k]와 a[i]를 교환
                    char temp = a[k];
                    a[k] = a[i];
                    a[i] = temp;

                    Perm(a, k + 1); //a[k+1],…,a[n-1]에 대한 모든 순열
                    //원래 상태로 되돌리기 위해 a[k]와 a[i]를 다시 교환
                    temp = a[k];
                    a[k] = a[i];
                    a[i] = temp;
                }
            }
        }
    }
}

 

순열.zip

 

참고 : C++ 자료구조론 - 이석호