C 언어로 순열 생성 프로그램의 구현 예와 설명

C 언어로 재귀 순열 생성 프로그램의 구현 예

#include <stdio.h>
#include <stdlib.h>

void    permutations(int *P, int *used, int total, int N)
{
    int     i;
    int     n;

    i = 1; //as permutation does not contain 0
    while (i <= total)
    {
        if (!used[i]) //if i is unused in the current permutation
        {
            used[i] = 1; //mark i as "used"
            P[N] = i;
            if (N == 1) //print when one permutation is complete 
            {
                n = total;
                while (n)
                {
                    printf("%d ", P[n]);
                    n--;
                }
                printf("\n");
            }
            else // set num for P[N - 1]
                permutations(P, used, total, N - 1);
            used[i] = 0; //set i as "unused"
        }
        i++;
    }
}

int     main()
{
    int     N;
    int     *P;
    int     *used;

    printf("total num : ");
    scanf("%d\n", &N);

    P = (int *)malloc(sizeof(int) * (N + 1));
    used = (int *)calloc((N + 1), sizeof(int));

    permutations(P, used, N, N);

    free(P);
    free(used);
    return (0);
}

　main 함수의 거동

배열을 생성하는 함수 used 에 앞서 확보한 배열의 malloc 와 permutations .P used 와 N
(주의) 2와 3의 때 . 에서 배열을 사용하고 있기 때문입니다.

(추기)N 의 배열이 0으로 초기화되지 않았기 때문에 P 대신 used 를 사용해서는 조언을 받았습니다. 감사합니다! free 의 배열은 N + 1 를 사용해 확보하도록(듯이) 재기입했습니다.

permutations 함수의 거동

이 함수는 재기적으로 호출되어 순열을 생성합니다.

이미지로서는 이하의 이미지와 같이 됩니다.


전체의 흐름으로서는
1. 우선 재귀의 최하층인 P[1] 까지 진행해, 그 시점에서 완성된 used[1] 가 표시된다
2. 사용되고 있던 used 가 해방되어 malloc 의 층으로 돌아온다 ( calloc 에서는 used 때문에 calloc3. 이 시점에서 N = 1 가 될 때까지 P 루프에 들어 있기 때문에, 우선 i 와 N = 2 의 값이 바뀐 것이 다음에 표시된다.
4. 사용된 N = 1 가 해제되고 i = total 레이어로 돌아가기( while5. 이 시점에서 i = total 루프가 끝날 때까지 while 의 값이 다른 순열을 표시

라는 흐름으로 재귀되어 순열이 생성됩니다.