재귀 함수를 이용한 순열(Permutation) 알고리즘

1 2 3 같은 수의 총 순열 가짓수는 몇 가지인지 알고 싶을때 이용할 수 있다.

이 코드는 중복 순열은 지원하지 않는다.(ex : 1 2 2 같은 경우)

 
#include <iostream>
 
#define swap(a,b,temp) temp=a; a=b; b=temp;
 
using namespace std;
 
int cnt = 0;
  
void permutations(int *a, const int k, const int m) // k 는 시작점
// a[k],...,a[m]에 대한 모든 순열을 생성
{
  int i;            
  int temp;
 
       
  if(k == m) //순열을 출력
  {
    for(i = 0 ; i <= m ; i ++)
    { printf("%d ",a[i]);}
    printf("\n");
    cnt++; // 총 몇가지 경우의 수인지 확인 
  }
 
  else // a[k] a[m]에 있는 여러 순열을 순환적으로 생성
  {
    for(i = k ; i <= m ; i++)  
    {
      swap(a[k],a[i],temp); // a[k]와 a[i]를 교환
      permutations(a,k+1,m); // a[k+1],...a[m]에 대한 모든 순열
                             // 원래 상태로 되돌리기 위해 a[k]와 a[i]를 다시 교환
      swap(a[k],a[i],temp); 
    }
    
  }
}
 
int main()
{
    int n;
    int arr[100];
    
    cout << "순열에 이용할 자리 수를 입력하시오 : ";
    cin >> n; // 몇 가지의 수를 이용할지 
    
    cout << "수를 입력하여 주십시오. ex) 3자리 수이면 1 2 3" << endl;
    // 1 1 2 같은 중복되는 수는 지원하지 않는다. 
    for(int i = 0 ; i < n ; i ++) cin >> arr[i];
                                  
    cout << endl;
    permutations(arr,0,n-1); // 0~n-1 까지의 수는 총 n가지이다. 
    printf("총 가짓 수 : %d",cnt); 
}
 

간단하게 생각해보자

abcde가 있을 때 permutation이 되기 위해 서로가 한칸씩 밀려나가야 한다.

처음으로 자기자신과 swap을 하는 과정을 거치게 되고 그다음에는 현재 인덱스 다음 인덱스와 swap을 해야하는 과정이 필요하다.

그 과정을 아래와 같이 나타낼 수 있다.

#include <iostream>
#include <cstdio>
 
#define N 5
#define swap(a,b){char t = a; a = b; b = t;}
using namespace std;
 
void permutation(int index, char *input)
{
    if(index == N)
    {
        cout << input << endl;
        return;
    }
 
    for (int i = index; i < N; i++)
    {
        swap(input[index], input[i]);
        permutation(index + 1, input);
        swap(input[index], input[i]);
    }
}
int main()
{
    char str[6] = "abcde";
    permutation(0, str);
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>