[자료구조] 순열(Permutation)개념 구현 C#

순열(Permutation)

순열이란 순서가 부여된 서로 다른 원소배열을 중복없이 순서에 맞게 나열하는 것이다.

예를들어 1,2,3 이란 배열을 순열한다면 아래처럼 된다.

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

순열을 구하는 기본적인 방법은 재귀를 통해 DEPTH의 위치와 각위치의 숫자를 스왑하여 재귀로 호출하고 다시 원복하는 것 이다. 재귀를 호출 할 때 DEPTH와 i가 같을 때는 원래위치도 순열 중 하나이기 때문에 그대로 진행한다. 

종료시에는 DEPTH와 구하려는 길이가 같은 시점에서 재귀를 종료하면 된다.

 

소스코드

        static void Main(string[] args)
        {
            int[] datas = new int[] { 1, 2, 3 };
            Permutation(datas, 0, 3);
        }
        static void Permutation(int[] arr, int depth)
        {
            if (depth == arr.Length - 1)//순열을 출력
            {
                for (int i = 0; i < arr.Length; i++)
                {
                    Console.Write("{0} ", arr[i]);
                }
                Console.WriteLine();
            }
            else
            {
                for (int i = depth; i < arr.Length; i++)
                {
                    //a[depth]와 a[i]를 교환
                    int temp = arr[depth];
                    arr[depth] = arr[i];
                    arr[i] = temp;

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