[algorithm] generate all permutations of string

permutation and combination

• 순열과 조합 문제는 기본적으로 slot을 채우는 개념으로 접근해야 이해하기 편하다.

  • 예를 들면, n개의 숫자에서 r개 뽑아서 나열하는 경우의 수를 생각해보자.
  • r개의 slot이 있고, 각각의 slot에 n개의 가능한 선택이 있으므로, n * n * ... *n=n^r
    • 대표적 문제 : 8bit로 표현 가능한 숫자의 범위, 2^8
  • 그런데, 이와 같이 앞쪽 slot에서 채운 숫자를 다시 뽑을 수 있는 경우가 아니라 다른 숫자를 뽑아야만 한다면 어떨까?
    • 첫번째 slot에서는 n가지 선택 가능, 두번째 slot에서는 (n-1)가지 선택 가능... 이런 식이므로 n * (n-1) * (n-2) * ... * (n-(r-1))
    • 즉, n!/(n-r)!
  • 조합의 경우는 어떨까? 즉, n개에서 순서에 무관하게 r개를 뽑는 경우의 수는?
    • 순열의 결과물에서 slot size가 r이므로 r!개는 항상 그룹으로 묶일 수 있다. 즉, 이 사이즈로 나눌 수 있다는 말이다.
    • 따라서, n!/((n-r)! * r!)

• 문자열의 모든 permutation은 recursion을 이용해서 출력 할 수 있다. 설명

  • 이 방법의 time complexity : O(n * n!)
  • 왜냐하면, 모든 가능한 경우의 수 자체가 n!이고 개별 문자열 print에 n이 소모되기 때문이다.

• 사이즈가 n인 문자열에서 r개만큼 선택해서 나열하는 코드를 작성하려면 어떻게 해야할까?

  • 방법은 사이즈가 n인 문자열에서 n개를 선택해서 나열하는 코드(아래)와 비슷하다.
  • 다만 recursion의 depth가 r로 고정, 출력 문자열의 길이도 r로 고정

1 2 3
[1 2 3, 2 1 3, 3 2 1] <- 첫번째 slot에 가능한 3가지
[1 2 3, 1 3 2], [2 1 3, 2 3 1], [3 2 1, 3 1 2] <- 두번째 slot에 가능한 2가지
[1 2 3, 1 3 2], [2 1 3, 2 3 1], [3 2 1, 3 1 2] <- 세번째 slot에 가능한 1가지

만약 3개 중에 2개를 선택해서 나열한다면, 두번째 slot을 채우는 depth에서 종료.
또한 출력 문자열의 길이도 2로 제한.
time complexity는 O(r * n! / (n-r)!)

sample code

// nPn
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int* list, int idx, int pidx)
{
    int tmp;
    tmp = list[idx];
    list[idx] = list[pidx];
    list[pidx] = tmp;
}

void permute(int* list, int begin, int end)
{
    int i, j;

    if( begin == end ) {
        for( j = 0; j < end; j++ ) {
            fprintf(stdout, "%d ", list[j]);
        }
        fprintf(stdout, "\n");
    } else {
        for( i = begin; i < end; i++ ) {
            swap(list, begin, i);
            permute(list, begin+1, end);
            swap(list, begin, i);
        }
    }
}

int main(int argc, char** argv)
{
    int list[5] = {1,2,3,4,5};

    permute(list, 0, 5);

    return 0;
}

// nPr
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int* list, int idx, int pidx)
{
    int tmp;
    tmp = list[idx];
    list[idx] = list[pidx];
    list[pidx] = tmp;
}

void permute(int* list, int begin, int end, int r)
{
    int i, j;

    if( begin == r ) {
        for( j = 0; j < r ; j++ ) {
            fprintf(stdout, "%d ", list[j]);
        }
        fprintf(stdout, "\n");
    } else {
        for( i = begin; i < end; i++ ) {
            swap(list, begin, i);
            permute(list, begin+1, end, r);
            swap(list, begin, i);
        }
    }
}

int main(int argc, char** argv)
{
    int list[5] = {1,2,3,4,5};
    int n, r;

    n = 5;
    r = 3;

    // 5P3
    permute(list, 0, 5, 3);

    return 0;
}