순열 알고리즘: C 프로그래밍에서의 구현

참고: 

https://swlock.blogspot.com/2016/03/permutation-algorithm.html#google_vignette

순열 (Permutation) 알고리즘 생성 방법 algorithm

순열과 조합은 모두 집합의 원소들을 사용해 나열하거나 선택하는 방법을 설명하는 수학적 개념이지만 명확한 차이가 있다. 

https://minusi.tistory.com/entry/%EC%88%9C%EC%97%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Permutation-Algorithm

순열과 조합의 차이 

1. 순열 (Permutation) _순서 상관 있음! 

 

순열은 집합의 원소들을 순서를 고려하여 나열한다. 예를 들어, 집합 {A, B, C}의 원소를 사용하여 만들 수 있는 모든 3자리 순열은 ABC, ACB, BAC, BCA, CAB, CBA와 같이 순서에 따라 다르게 나타난다. 순열에서는 같은 원소들을 사용하더라도 순서가 다르면 다른 경우로 취급한다.

수식: 
𝑛개의 서로 다른 원소에서  𝑟개를 선택하여 나열하는 순열의 수는 

2. 조합 (Combination) _ 순서 상관 없음! 

조합은 집합의 원소들 중 일부를 선택할 때 순서를 고려하지 않는 것이다. 예를 들어, 집합 {A, B, C}에서 2개의 원소를 선택하는 조합은 AB, AC, BC만을 고려하며, BA, CA, CB는 AB, AC, BC와 같은 조합으로 간주된다. 조합에서는 원소의 선택된 집합이 중요하고, 선택된 원소들의 순서는 고려되지 않는다.

수식: 
𝑛 개의 서로 다른 원소에서  𝑟개를 순서에 상관 없이 선택하는 조합의 수는 

 

 

예시를 통한 설명

집합 {1, 2, 3}에서 2개의 원소가 있을 때 

• 순열: 12, 21, 13, 31, 23, 32 (순서가 다르면 다른 경우로 간주)
• 조합: 12, 13, 23 (순서에 상관 없이 두 원소의 조합만 고려)

순열 생성 알고리즘

순열은 주어진 집합의 원소를 나열하는 모든 가능한 방법이다. 예를 들어, {1, 2, 3}의 순열은 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 등을 포함한다. 

순열 생성 알고리즘은 두 가지 주요 기법을 사용한다: 재귀 호출과 백트래킹.

재귀 호출을 사용하면 각 원소를 한 위치에 고정시킨 채로 다음 원소의 위치를 재귀적으로 결정한다. 백트래킹은 모든 경우의 수를 탐색한 후, 이전의 상태로 돌아가 다른 가능성을 탐색하게 한다. 이 과정은 트리 구조의 모든 경로를 탐색하는 것과 유사하다.

순열 알고리즘 문제 

• 문제 : 문자열의 모든 순열 찾기.
• 설명: 주어진 문자열의 모든 순열을 출력하는 프로그램을 작성하세요.  문자열은 알파벳 소문자만 포함되며, 문자열의 길이는 1이상 6이하입니다. 
• 입력 예시: 'abc'
• 출력 예시: 

abc
acb
bac
bca
cab
cba

• 요구 사항
  • 입력으로 주어진 문자열의 모든 순열을 사전순으로 출력해야 합니다.
  • 각 순열은 새로운 줄에 출력되어야 합니다.
• 구현 팁
  • 순열을 생성하기 위해 재귀 함수를 사용하세요.
  • 문자의 위치를 교환하는 swap 함수를 구현하여 재귀적으로 문자 위치를 바꿔보세요.
  • 순열 생성 과정에서, 현재 인덱스와 교환할 각 인덱스를 순회하면서 모든 가능한 교환을 시도하세요.
  • 모든 순열을 생성한 후에는 문자열을 원래 상태로 복구하여 다음 순열 생성에 영향을 주지 않도록 합니다.
• 정답

#include <stdio.h>
#include <string.h>

// 문자 위치를 교환하는 함수
void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

// 순열 생성 및 출력 함수
void permute(char *a, int l, int r) {
    if (l == r) {
        printf("%s\n", a);  // 순열 출력                                                       
        
    } else {
        for (int i = l; i <= r; i++) {  // i = 0~2까지
            swap((a + l), (a + i));  // 현재 인덱스 l과 i의 위치 교환
            permute(a, l + 1, r);  // l 다음 위치에서 다시 순열 생
            swap((a + l), (a + i));  // ㅣ== r 일 때만 수행됨.  백트래킹을 위해 원래 위치로 복원
        }
    }
}                                                                                                                                                                                                                                           
int main() {
    char str[] = "abc";
    int n = strlen(str);
    permute(str, 0, n-1);  // 순열 생성 함수 호출
    return 0;
}

# 출력 
abc
acb
bac
bca
cba
cab

 

해당 코드가 어렵다면 간단히 이렇게 생각하면 된다. 

백트래킹을 하기 때문에 각 i 마다 시작 문자열은 "abc" 이다. 

 

i=0일때 

swap((0),(0)) = abc

swap((1),(0)) = bac

swap((2),(0)) = cab

 

i=1일때 

swap((0),(1)) = bac

swap((1),(1)) = bac

swap((2),(1))= bca

 

i=2일때 

swap((0),(2)) = cba

swap((1),(2)) = cab

swap((2),(2)) = cab